Scalar labelings for homotopy paths

Two scalar labelings are introduced for obtaining approximate solutions to systems of nonlinear equations by simplicial approximation. Under reasonable assumptions the new scalar-labeling algorithms are shown to follow, in a limiting sense, homotopy paths which can also be tracked by piecewise linear vector labeling algorithms. Though the new algorithms eliminate the need to pivot on a system of linear equations, the question of relative computational efficiency is unresolved.The work of this author was supported in part by NSF Grant No. MCS-77-15509 and by ARO Grant No. DAAG-29-78-G-0160.The work of this author was supported in part by ONR Grant No. N00014-75-C-0495 and NSF Grant No. 81058.     

On Teichmüller’s proof of Teichmüller’s theorem

A simplified version of Teichmüllers proof (independent of the theory of Beltrami equations with measurable coefficients) of a proposition underlying his continuity argument for the existence part of his theorem on extremal quasiconformal mappings is given. This material is based upon work partially supported by the National Science Foundation under Grant No. NSF MCS-78-27119.     

On Teichmüller’s proof of Teichmüller’s theorem

A simplified version of Teichmüllers proof (independent of the theory of Beltrami equations with measurable coefficients) of a proposition underlying his continuity argument for the existence part of his theorem on extremal quasiconformal mappings is given. This material is based upon work partially supported by the National Science Foundation under Grant No. NSF MCS-78-27119.     

A dynamic solution concept for abstract games

Several solution concepts have been defined for abstract games. Some of these are the core, due to Gillies and Shapley, the Von Neumann-Morgenstern stable sets, and the subsolutions due to Roth. These solution concepts are rather static in nature. In this paper, we propose a new solution concept for abstract games, called the dynamic solution, that reflects the dynamic aspects of negotiation among the players. Some properties of the dynamic solution are studied. Also, the dynamic solution of abstract games arising fromn-person cooperative games in characteristic function form is investigated.This research was supported by the Office of Naval Research under Contract No. N00014-75-C-0678, by the National Science Foundation under Grants Nos. MPS-75-02024 and MCS-77-03984 at Cornell University, by the United States Army under Contract No. DAAG-29-75-C-0024, and by the National Science Foundation under Grant No. MCS-75-17385-A01 at the University of Wisconsin. The author is grateful to Professor W. F. Lucas under whose guidance the research was conducted.     

Distances between measures from 1-dimensional projections as implied by continuity of the inverse radon transform

Summary Distances between measures on IR ^d are determined from distances between their 1-dimensional projections. The method employed involves considering the 1-dimensional projections to be the Radon transform of the measures. Crucial to the main theorem is a continuity result for the inverse Radon transform. Focus is restricted to the Prohorov, dual bounded Lipschitz and d _k metrics which metrize weak convergence of probability measures. These metrics are related to each other and to the Sobolev norms. The d _k results extend from measures to generalized functions.Partially supported by NSF Grant No. MCS-81-01895Partially supported by NSF Grant No. MCS-82-01627 and support from the Mellon Foundation     

An LP-based successive overrelaxation method for linear complementarity problems

A sparsity preserving LP-based SOR method for solving classes of linear complementarity problems including the case where the given matrix is positive-semidefinite is proposed. The LP subproblems need be solved only approximately by a SOR method. Heuristic enhancement is discussed. Numerical results for a special class of problems are presented, which show that the heuristic enhancement is very effective and the resulting program can solve problems of more than 100 variables in a few seconds even on a personal computer.This research was sponsored by the Air Force Office of Scientific Research, Grant No. AFOSR-86-0124. Part of this material is based on work supported by the National Science Foundation under Grant No. MCS-82-00632.The author is grateful to Dr. R. De Leone for his helpful and constructive comments on this paper.     

Modifications and implementation of the ellipsoid algorithm for linear programming

We give some modifications of the ellipsoid algorithm for linear programming and describe a numerically stable implementation. We are concerned with practical problems where user-supplied bounds can usually be provided. Our implementation allows constraint dropping and updates bounds on the optimal value, and should be able to terminate with an indication of infeasibility or with a provably good feasible solution in a moderate number of iterations.The work of this author was supported in part by the U.S. Army Research Office under Grant DAAG29-77-G-0114 and the National Science Foundation under Grant MCS-8006065.The work of this author was supported in part by the National Science Foundation under Grant ECS-7921279.     

Existence of solutions of multi-valued Urysohn integral equations

We prove the existence of a solution of an integral inclusion of Urysohn type with delay. By imposing standard boundedness, convexity, and semicontinuity conditions on the set-valued mapping defining the integral inclusion, we show that the right-hand side of the relation constitutes a mapping defined on a suitable Banach space and satisfying the conditions of Kakutani's theorem for the existence of a fixed point of a set-valued mapping. By introducing the notion of generalized or chattering state solutions, we show how the convexity requirements may be relaxed.This work was supported by NSF Grant No. MCS-82-02033.     

Bifurcation and symmetry-breaking

Research supported in part by the NSF under Grant No. MCS-830123     

Idempotents in compact semigroups and Ramsey theory

We prove a theorem about idempotents in compact semigroups. This theorem gives a new proof of van der Waerden’s theorem on arithmetic progressions as well as the Hales-Jewett theorem. It also gives an infinitary version of the Hales-Jewett theorem which includes results of T. J. Carlson and S. G. Simpson. Research supported by the National Science Foundation under Grant No. DMS86-05098.     

Almost disjoint abelian groups

Under various set-theoretic hypotheses we construct families of maximal possible size of almost free abelian groups which are pairwise almost disjoint, i.e. there is no non-free subgroup embeddable in two of them. We show that quotient-equivalent groups cannot be almost disjoint, but we show how to construct maximal size families of quotient-equivalent groups of cardinality ℵ₁, which are mutually non-embeddable. Dedicated to the memory of Abraham Robinson on the tenth anniversary of this death First and third authors acknowledge assistance from the US-Israel Binational Science Foundation, Grant No. 1110. First author partially supported by NSF Grant No. MCS-8003691. Second author acknowledges support from the National Science and Engineering Research Council of Canada, Grant No. U0075     

Convergence rates for intermediate problems

Convergence rate estimates are derived for a variant of Aronszajn-type intermediate problems that is both computationally feasible and known to be convergent for problems with nontrivial essential spectrum. Implementation of these derived bounds is discussed in general and illustrated on differential eigenvalue problems. Convergence rates are derived for the commonly used method of simple truncation.The work of the first author was partially supported by AFOSR Grant 84-0326. The work of the second author was partially supported by NSF Grant MCS-8301402     

A modified Newton's method for minimizing factorable functions

Many functions of several variables used in nonlinear programming are factorable, i.e., complicated compositions of transformed sums and products of functions of a single variable. The Hessian matrices of twice-differentiable factorable functions can easily be expressed as sums of outer products (dyads) of vectors. A modified Newton's method for minimizing unconstrained factorable functions which exploits this special form of the Hessian is developed. Computational experience with the method is presented.This material is based upon work supported by the National Science Foundation under Grant No. MCS-79-04106.The author would like to thank Professor G. P. McCormick, George Washington University, for several enlightening discussions on factorable programming and for his valuable comments which improved an earlier version of this paper.     

Positive dependence orderings

Summary This paper presents a systematic basis for studying orderings of bivariate distributions according to their degree of positive dependence. The general concept of a positive dependence ordering (PDO) is introduced and its properties discussed. Based on this concept, a new ordering of bivariate distributions according to their degree of total positivity of order two (TP₂) is presented, and is shown to be a PDO. Properties of this TP₂ ordering are derived and numerous applications are presented. The work of this author is supported by the National Science Foundation under Grant MCS-8301361. The work of this author is sponsored by the Air Force Office of Scientific Research, Air Force Systems Command under Contract F49629-82-K-001. Reproduction in whole of in part is permitted for any purpose of the United States Government.     

Duality for nonlinear multiple-criteria optimization problems

In this paper, we develop a duality theory for nonlinear multiple-criteria optimization problems. The theory associates to efficient points a matrix, rather than a vector, of dual variables. We introduce a saddle-point dual problem, study stability concepts and Kuhn-Tucker conditions, and provide an economic interpretation of the dual matrix. The results are compared to the classical approach of deriving duality, by applying nonlinear programming duality theory to a problem obtained by conveniently weighting the criteria. Possible directions for future research are discussed.This work was performed under Grant No. MCS-77-24654, National Science Foundation.The author is grateful to Professors S. C. Graves and T. L. Magnanti, and two anonymous referees for helpful comments on an earlier version of this paper.     

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.     

On the product formulas for <Emphasis Type="Italic">C</Emphasis>-semigroups

In this paper we obtain a Chernoff-type approximation theorem for C-semigroups, from which we derive the Trotter product formula and the Post-Widder inversion formula for C-semigroups. The first author was supported by the NSF of China (Grant No. 10501032) and the NSFC-RFBR Programm (Grant No. 108011120015), and the second author by the NSF of China (Grant No. 10671079).     

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.     

Subspace theorems for homogeneous polynomial forms

We prove a subspace theorem for homogeneous polynomial forms which generalizes Schmidt’s subspace theorem for linear forms. Further, we formalize the subspace theorem into a form which is just the counterpart of a second main theorem in Nevanlinna’s theorem, and also suggest a problem. The work of the first author was partially supported by NSFC of China: Project. No. 10371064. The second author was partially supported by a UGC Grant of Hong Kong: Project No. 604103.     

Heuristic reliability optimization by tabu search

A new heuristic algorithm, based on the tabu search methodology, is proposed for constrained redundancy optimization in series and in complex systems. It has the advantage of not being blocked as soon as a local optimum is found. Results given by the new method are compared with those of previous heuristics on a series of examples.We are grateful to R. Bulfin for making the code for reliability optimization of series systems he wrote with C.-Y. Liu available to us.Work of the first author was supported by NSERC Grant No. GP0105574, FCAR Grant No. 92EQ1048 and AFOSR Grant No. 90-0008 to Rutgers University.Work of the second author was partly supported by AFOSR Grant No. 90-0008 to Rutgers University while he was a graduate student.