Asymptotic efficiency of the Spearman estimator and characterizations of distributions

Summary The Spearman estimator is designed to be a nonparametric estimator for the expectation of a tolerance distribution. We characterize the one-parameter families of distributions (the parameter being the mean of the distribution) for which the Spearman estimator has asymptotic efficiency one. In particular, when the parameter indexes the location, the characterizing distribution is the logistic distribution. In any other case of efficiency one, the family of distributions is given by certain transformations of a logistic distribution. The author's research is supported by a Grant from the Office of Naval Research, Grant No. N00014-84-K-0184. Reproduction in whole or in part is permitted for any purpose of the U.S. Government. The author's research is supported by the Royal Norwegian Council for Scientific and Industrial Research.     

Newton interpolation at Leja points

The Newton form is a convenient representation for interpolation polynomials. Its sensitivity to perturbations depends on the distribution and ordering of the interpolation points. The present paper bounds the growth of the condition number of the Newton form when the interpolation points are Leja points for fairly general compact sets K in the complex plane. Because the Leja points are defined recursively, they are attractive to use with the Newton form. If K is an interval, then the Leja points are distributed roughly like Chebyshev points. Our investigation of the Newton form defined by interpolation at Leja points suggests an ordering scheme for arbitrary interpolation points.Research supported in part by NSF under Grant DMS-8704196 and by U.S. Air Force Grant AFSOR-87-0102.On leave from University of Kentucky, Department of Mathematics, Lexington, KY 40506, U.S.A.     

Algorithms for a class of nondifferentiable problems

A nonlinear programming problem with nondifferentiabilities is considered. The nondifferentiabilities are due to terms of the form min(f ₁(x),...,f _n(x)), which may enter nonlinearly in the cost and the constraints. Necessary and sufficient conditions are developed. Two algorithms for solving this problem are described, and their convergence is studied. A duality framework for interpretation of the algorithms is also developed.This work was supported in part by the National Science Foundation under Grant No. ENG-74-19332 and Grant No. ECS-79-19396, in part by the U.S. Air Force under Grant AFOSR-78-3633, and in part by the Joint Services Electronics Program (U.S. Army, U.S. Navy, and U.S. Air Force) under Contract N00014-79-C-0424.     

On Kolmogorov-Smirnov-type tests for symmetry

Summary For a set of independent but not necessarily identically distributed random variables, a simple Kolmogorov-Smirnov-type test is proposed for testing the hypothesis of symmetry (about a common and specified point). The exact and asymptotic (null hypothesis) distributions of some allied statistics are obtained, and the Bahadur-efficiency of the test is studied. Work of the second author was supported by the U.S. National Institutes of Health, Grant GM-12868.     

Existence,uniqueness and continuity of solutions of integral equations. An addendum

Summary This note corrects au error in the continuous dependence theorem of an earlier paper on the subject stated in the title. Here it is shows that the topology of one of the spaces of functions can be modified in order to obtain the desired continuity results. This research was support in part by the National Aeronautics Space Administration under Grant No. NGL-40-002-015, and in part by the U. S. Air Force under Grant No. AF-AFOSR-67-0693A. This research was supported in part by the National Science Foundation under Grant No. GP-3904 and GP-7041 and in part by the U.S. Army under Grant No. D1-31-124-ARO-D-265. Entrata in Redazione il 10 aprile 1970.     

Numerical solution of a long-term average control problem for singular stochastic processes

This paper analyzes numerically a long-term average stochastic control problem involving a controlled diffusion on a bounded region. The solution technique takes advantage of an infinite-dimensional linear programming formulation for the problem which relates the stationary measures to the generators of the diffusion. The restriction of the diffusion to an interval is accomplished through reflection at one end point and a jump operator acting singularly in time at the other end point. Different approximations of the linear program are obtained using finite differences for the differential operators (a Markov chain approximation to the diffusion) and using a finite element method to approximate the stationary density. The numerical results are compared with each other and with dynamic programming. This research has been supported in part by the U.S. National Security Agency under Grant Agreement Number H98230-05-1-0062. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation herein.     

Convergence of finite-difference techniques for a harmonic mixed boundary value problem

The paper deals with the convergence of finite-difference approximations for a harmonic mixed boundary value problem. In particular the case when the boundary contains a slit is considered.Work on this paper was supported in part by NSF Grant GP-8442 and U.S. Army Grant DA-ARO(D)-31-124-G1050 at The University of Texas at Austin.     

On a programming language for graph algorithms

An algorithmic language, GRAAL, is defined, as an extension of ALGOL 60 (Revised), for describing and implementing graph algorithms of the type arising in applications. It is based on a set algebraic model of graph theory which defines the graph structure in terms of user specified morphisms between certain set algebraic structures over the node and arc set. Several examples of graph algorithms written in GRAAL are included.This work was in part supported by Grant GJ-1067 from the U.S. National Science Foundation and Grant NGL-21-002-008 from the U.S. National Aeronautics and Space Administration.     

Area requirement and symmetry display of planar upward drawings

In this paper we investigate the problem of constructing planar straight-line drawings of acyclic digraphs such that all the edges flow in the same direction, e.g., from bottom to top. Our contribution is twofold. First we show the existence of a family of planar acyclic digraphs that require exponential area for any such drawing. Second, motivated by the preceding lower bound, we relax the straight-line constraint and allow bends along the edges. We present a linear-time algorithm that produces drawings of planarst-graphs with a small number of bends, asymptotically optimal area, and such that symmetries and isomorphisms of the digraph are displayed. If the digraph has no transitive edges, then the drawing obtained has no bends. Also, a variation of the algorithm produces drawings with exact minimum area.Research supported in part by Cadre Technologies Inc., by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM), by the National Science Foundation under Grant CCR-9007851, by the Office of Naval Research and the Defense Advanced Research Projects Agency under Contract N00014-83-K-0146 and ARPA order 6320, amendment 1, by the Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo of the Italian National Research Council, by the Texas Advanced Research Program under Grant No. 3972, and by the U.S. Army Research Office under Grant DAAL03-91-G-0035.     

A bound for the optimum relaxation factor for the successive overrelaxation method

Summary An upper bound on the optimum relaxation factor for use with the successive overrelaxation method is derived for a class of linear systems arising from the numerical solution by finite difference methods of a boundary value problem involving the self-adjoint differential equationWork on this paper was supported in part by the U. S. Army Research Office (Durham) through Grant DA-ARO(D)-31-124-G 1050 and by the National Science Foundation through Grant GP-8442 with The University of Texas at Austin.     

Application of the Poincaré-Bendixson theorem

Summary The Poincaré-Bendixson theorem is used to study the level curves of a positive definite function V(x, y), near the origin, and to obtain a short proof of the Brouwer fixed-point theorem in the plane. This will acknowledge the partial support of the authors by the National Science Foundation under Grant numbered GP 4057. This will acknowledge the partial support of the author by the U. S Army Research Office (Durham) under Grant numbered DA-ARO(D)-31-124-G-600.     

Control of Affine Nonlinear Systems with Nilpotent Structure in Singular Problems

The minimum singular functional control problem is analyzed for a class of multi-input affine nonlinear systems under the hypothesis that the associated Lie algebra is nilpotent. The optimal control corresponding to the first, second, and third order nilpotent operators is determined. We develop an algorithm for solving the singular problem that is applicable whether or not singular subarcs exist in the optimal control.This work was partial supported by the Romanian Aerospace Agency, Grant 31032.     

Using AI methodologies in mathematical modeling of production systems

This research was supported in part by Sandia National Laboratories Grant No. 56-4617. Sandia is managed by AT&;T Technologies for the U.S. Department of Energy.     

Limit theorems for sums of dependent random variables occurring in statistical mechanics

Summary By the use of conditioning, we extend previously obtained results on the asymptotic behavior of partial sums for certain triangular arrays of dependent random variables, known as Curie-Weiss models. These models arise naturally in statistical mechanics. The relation of these results to multiple phases, metastable states, and other physical phenomena is explained.Alfred P. Sloan Research Fellow. Research supported in part by National Science Foundation Grant MPS 76-06644A01Alfred P. Sloan Research Fellow. Research supported in part by National Science Foundation Grant MCS 77-20683 and by U.S.-Israel Binational Science FoundationResearch supported in part by National Science Foundation Grant PHY77-02172     

The empirical behavior of sampling methods for stochastic programming

We investigate the quality of solutions obtained from sample-average approximations to two-stage stochastic linear programs with recourse. We use a recently developed software tool executing on a computational grid to solve many large instances of these problems, allowing us to obtain high-quality solutions and to verify optimality and near-optimality of the computed solutions in various ways. Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the National Science Foundation under Grant 9726385. Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the National Science Foundation under Grant DMS-0073770. Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the National Science Foundation under Grants 9726385 and 0082065.     

Newton's method for a class of nonsmooth functions

This paper presents and justifies a Newton iterative process for finding zeros of functions admitting a certain type of approximation. This class includes smooth functions as well as nonsmooth reformulations of variational inequalities. We prove for this method an analogue of the fundamental local convergence theorem of Kantorovich including optimal error bounds.The research reported here was sponsored by the National Science Foundation under Grants CCR-8801489 and CCR-9109345, by the Air Force Systems Command, USAF, under Grants AFOSR-88-0090 and F49620-93-1-0068, by the U. S. Army Research Office under Grant No. DAAL03-92-G-0408, and by the U. S. Army Space and Strategic Defense Command under Contract No. DASG60-91-C-0144. The U. S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.     

Complexes of rings

Homology group of complexes of finitely generated projective modules are shown to be torsion groups, and a simplified proof of the vanishing of the cohomology groupsn≧3 of inseparable extensions is given. This work has been sponsored by NSF Grant No. 1964 while the author was at Northwestern University and by Grant AF EOAR 63-70 of the European Office of Aerospace Research, U.S. Air Force.     

Solving combinatorial optimization problems using Karmarkar's algorithm

We describe a cutting plane algorithm for solving combinatorial optimization problems. The primal projective standard-form variant of Karmarkar's algorithm for linear programming is applied to the duals of a sequence of linear programming relaxations of the combinatorial optimization problem.Computational facilities provided by the Cornell Computational Optimization Project supported by NSF Grant DMS-8706133 and by the Cornell National Supercomputer Facility. The Cornell National Supercomputer Facility is a resource of the Center for Theory and Simulation in Science and Engineering at Cornell Unversity, which is funded in part by the National Science Foundation, New York State, and the IBM Corporation. The research of both authors was partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research partially supported by ONR Grant N00014-90-J-1714.Research partially supported by NSF Grant ECS-8602534 and by ONR Contract N00014-87-K-0212.     

The optimal control of diffusions

Using a differentiation result of Blagovescenskii and Freidlin calculations of Bensoussan are simplified and the adjoint process identified in a stochastic control problem in which the control enters both the drift and diffusion coefficients. A martingale representation result of Elliott and Kohlmann is then used to obtain the integrand in a stochastic integral, and explicit forward and backward equations satisfied by the adjoint process are derived.This research was partially supported by NSERC under Grant A7964, the U.S. Air Force Office of Scientific Research under Contract AFOSR-86-0332, and the U.S. Army Research Office under Contract DAAL03-87-K-0102.     

Product Ł ukasiewicz Logic

u logic plays a fundamental role among many-valued logics. However, the expressive power of this logic is restricted to piecewise linear functions. In this paper we enrich the language of u logic by adding a new connective which expresses multiplication. The resulting logic, P, is defined, developed, and put into the context of other well-known many-valued logics. We also deal with several extensions of this propositional logic. A predicate version of P logic is introduced and developed too.The work of the first author was supported by the Grant Agency of the Czech Republic under project GACR 201/02/1540, by the Grant Agency of the Czech Technical University in Prague under project CTU 0208613, and by Net CEEPUS SK-042.The work of the second author was supported by grant IAA1030004 of the Grant Agency of the Academy of Sciences of the Czech Republic.