A simplified global convergence proof of the affine scaling algorithm

This paper presents a simplified and self-contained global convergence proof for the affine scaling algorithm applied to degenerate linear programming problems. Convergence of the sequence of dual estimates to the center of the optimal dual face is also proven. In addition, we give a sharp rate of convergence result for the sequence of objective function values. All these results are proved with respect to the long step version of the affine scaling algorithm in which we move a fraction , where (0,2/3), of the step to the boundary of the feasible region.This research was supported by the National Science Foundation (NSF) under Grant No. DDM-9109404 and the Overseas Research Scholars of the Ministry of Education, Science and Culture of Japan.     

A practical anti-cycling procedure for linearly constrained optimization

A procedure is described for preventing cycling in active-set methods for linearly constrained optimization, including the simplex method. The key ideas are a limited acceptance of infeasibilities in all variables, and maintenance of a working feasibility tolerance that increases over a long sequence of iterations. The additional work per iteration is nominal, and stalling cannot occur with exact arithmetic. The method appears to be reliable, based on computational results for the first 53 linear programming problems in theNetlib set.The material contained in this report is based upon research supported by the Air Force Office of Scientific Research Grant 87-01962; the U.S. Department of Energy Grant DE-FG03-87ER25030; National Science Foundation Grants CCR-8413211 and ECS-8715153; and the Office of Naval Research Contract N00014-87-K-0142.     

Energy functional depending on elastic strain and chemical composition

In this paper we deal with energy functionals depending on elastic strain and chemical composition and we obtain lower semicontinuity results, existence theorems and relaxation in the spacesH ^1,p(; ⁿ)×L ^q (; ^d) with respect to weak convergence. Our proofs use parametrized measures associated with weakly converging sequences.The research was partially supported by the National Science Foundation under Grants No. DMS-9000133 and DMS-9201215 and also by the Army Research Office and the National Science Foundation through the Center for Nonlinear Analysis.The research was partially supported by the National Science Foundation uncer Grants No. DMs 911572, the AFOSR 91 0301, the ARO DAAL03 92 G 003 and also by the ARO and the NSF through the Center for Nonlinear Analysis.The research was supported by DGICYT (Spain) through Programa de Perfeccionamiento y Movilidad del Personal Investigador and through grant PB90-0245, by the Army Research Office and the National Science Foundation through the Center for Nonlinear Analysis and also by the project EurHomogenization SC1-CT91-0732 of the European Comunity.     

Exponential inequalities for dependent random variables

This paper contains the Kolmogorov-Prokhorov exponential inequalities for dependent random variables, i.e., for-mixing,-mixing and-mixing. As an application, the law of iterated logarithm is established for stationary-mixing sequence under a nearly best assumption.Research supported by National Science Foundation Grant.     

The critical contact process seen from the right edge

Summary Durrett (1984) proved the existence of an invariant measure for the critical and supercritical contact process seen from the right edge. Galves and Presutti (1987) proved, in the supercritical case, that the invariant measure was unique, and convergence to it held starting in any semi-infinite initial state. We prove the same for the critical contact process. We also prove that the process starting with one particle, conditioned to survive until timet, converges to the unique invariant measure ast.Partially supported by the National Science FoundationPartially supported by the National Science Foundation, the National Security Agency, and the Army Research Office through the Mathematical Sciences Institute at Cornell University     

The Feynman-Kac formula with a Lebesgue-Stieltjes measure: An integral equation in the general case

Let u(t) be the operator associated by path integration with the Feynman-Kac functional in which the time integration is performed with respect to an arbitrary Borel measure instead of ordinary Lebesgue measurel. We show that u(t), considered as a function of time t, satisfies a Volterra-Stieltjes integral equation, denoted by (*). We refer to this result as the Feynman-Kac formula with a Lebesgue-Stieltjes measure. Indeed, when n=l, we recover the classical Feynman-Kac formula since (*) then yields the heat (resp., Schrödinger) equation in the diffusion (resp., quantum mechanical) case. We stress that the measure is in general the sum of an absolutely continuous, a singular continuous and a (countably supported) discrete part. We also study various properties of (*) and of its solution. These results extend and use previous work of the author dealing with measures having finitely supported discrete part (Stud. Appl. Math.76 (1987), 93–132); they seem to be new in the diffusion (or imaginary time) as well as in the quantum mechanical (or real time) case.Research partially supported by the National Science Foundation under Grant DMS 8703138. This work was also supported in part by NSF Grant 8120790 at the Mathematical Sciences Research Institute in Berkeley, U.S.A., the CNPq and the Organization of Latin American States at theInstituto de Matemática Pura E Aplicada (IMPA) in Rio de Janeiro, Brazil, as well as theUniversité Pierre et Marie Curie (Paris VI) and the Université Paris Dauphine in Paris, France.     

An additive function on a ring of integers in the imaginary quadratic field Q(√d) with class-number one

LetB (a) be an additive function on a ring of integers in the quadratic number fieldQ(d) given byB (a) = _p|a *N (p) with a fixed > 0, where the asterisk means that the summation is over the non-associate prime divisorsp of an integera inQ(d), N(a) is the norm ofa. In this paper we obtain the asymptotic formula of _N(a)x *B (a) in the case where the class-number ofQ(d) is one.Project supported by the National Natural Science Foundation of China.     

A condition for absolute continuity of infinitely divisible distribution functions

Summary Throughout this paper the symbols r.v., d.f., ch.f., and i.d. will stand, respectively, for random variable, distribution function, characteristic function, and infinitely divisible.Let F(x) be an i.d.d.f. Hartman and Wintner [5] and Blum and Rosenblatt [1] have given a condition, necessary and sufficient, for F(x) to be a continuous d.f. In this note a sufficient condition for F(x) to be an absolutely continuous d.f. is given.Research supported by ONR Contract No. NONR-285(46).Research supported in part by a National Science Foundation fellowship.     

A combinatorial characterization of the Klein quadric

We give a combinatorial characterization of the Klein quadric in terms of its incidence structure of points and lines. As an application, we obtain a combinatorial proof of a result of Havlicek.In memoriam Giuseppe TalliniWork supported by National Research Project Strutture Geometriche, Combinatoria e loro applicazioni of the Italian Ministere dell'Università e della Ricerca Scientifica and by G.N.S.A.G.A. of C.N.R.      

Nonlinear programming and stationary equilibria in stochastic games

Stationary equilibria in discounted and limiting average finite state/action space stochastic games are shown to be equivalent to global optima of certain nonlinear programs. For zero sum limiting average games, this formulation reduces to a linear objective, nonlinear constraints program, which finds the best stationary strategies, even when-optimal stationary strategies do not exist, for arbitrarily small. The work of the first author was supported in part by the Air Force Office of Scientific Research, and by the National Science Foundation under Grant No ECS-8704954.The work of the third author was supported by The Netherlands Organization for Scientific Research NWO, project 10-64-10.     

Quantitative stability of variational systems: III.ε-approximate solutions

We prove that the-optimal solutions of convex optimization problems are Lipschitz continuous with respect to data perturbations when these are measured in terms of the epi-distance. A similar property is obtained for the distance between the level sets of extended real valued functions. We also show that these properties imply that the-subgradient mapping is Lipschitz continuous.Research supported in part by the National Science Foundation and the Air Force Office of Scientific Research.     

Explicit matchings in the middle levels of the Boolean lattice

New classes of explicit matchings for the bipartite graph (k) consisting of the middle two levels of the Boolean lattice on 2k+1 elements are constructed and counted. This research is part of an ongoing effort to show that (k) is Hamiltonian.Supported by Office of Naval Research contract N00014-85K-0494.Supported by National Science Foundation grant DMS-8041281.     

A combinatorial property of points and ellipsoids

For eachd1 there is a constantc _d>0 such that any finite setXR ^d contains a subsetYX, |Y|[1/4d(d+3)]+1 having the following property: ifEY is an ellipsoid, then |E X|c _d |X|.On leave from the Mathematical Institute of the Hungarian Academy of Sciences, 1364 Budapest, P.O. Box 127, Hungary. Supported by a research fellowship from the Science and Engineering Research Council, U.K., and by Hungarian National Foundation for Scientific Research Grant No. 1812.     

Reinforcement problems for elliptic equations and variational inequalities

Summary Consider the Dirichlet problem for an elliptic equation in a domain , with coefficients having discontinuity on a surface . Suppose divides into _{1 2}(₂ the inner core), the thickness of ₁ is of order of magnitude , and the modulus of ellipticity in ₁ is of order magnitude ₁. The asymptotic behavior of the solution is studied as 0, ₁ 0, provided lim (/₁) exists. Other questions of this type are studied both for elliptic equations and for elliptic variational inequalities.The second author is partially supported by National Science Foundation Grant 7406375 A01. The third author is partially supported by National Science Foundation Grant MC575-21416 A01.     

Sharp regularity theory for second order hyperbolic equations of Neumann type

Summary We consider the mixed problem for a general, time independent, second order hyperbolic equation in the unknown u, with datum g L₂() in the Neumann B.C., with datum f L₂(Q) in the right hand side of the equation and, say, initial conditions u₀=u₁=0. We obtain sharp regularity results for u in Q and ù| in , by a pseudo-differential approach on the half-space.Research partially supported by the National Science Foundation under Grants DMS-83-016668 and DMS-87-96320.     

Submanifolds of complex space forms admitting an almost contact metric compound structure

Summary Real hypersurfaces of an almost Hermitian manifold naturally admit an almost contact metric structure and the (f, g, u, v, w, , , )-structure is defined on submanifolds of codimension 3 of an almost Hermitian manifold. We study the so-called semi-invariant submanifolds of a complex space form with almost contact metric compound structure which is a general notion of (f, g, u, v, w, , , )-structure.Dedicated to professor Eulyong Pak on his 60th birthdayThis research was partially supported by Korean Science and Engineering Foundation Grant.     

Some expansion formulae for Fox'sH-function of two variables involving associated Legendre functions

H- .     

Symbolic dynamics and nonlinear semiflows

Summary For a transverse homoclinic orbit of a mapping (not necessarily invertible) on a Banach space, it is shown that the mapping restricted to orbits near is equivalent to the shift automorphism on doubly infinite sequences on finitely many symbols. Implications of this result for the Poincaré map of semiflows are given.This work was supported by the Air Force Office of Scientific Research under Grant #81-0198, by the National Science Foundation under Grant #MCS-8205355 and by the Army Research Office under Grant ù DAAG-29-83-K-0029.     

Continuous Quotients for Lattice Actions on Compact Spaces

Let < SL _n ( ) be a subgroup of finite index, where n 5. Suppose acts continuously on a manifold M, where ₁(M) = ⁿ , preserving a measure that is positive on open sets. Further assume that the induced action on H ¹(M) is non-trivial. We show there exists a finite index subgroup < and a equivariant continuous map : M ⁿ that induces an isomorphism on fundamental group. We prove more general results providing continuous quotients in cases where ₁(M) surjects onto a finitely generated torsion free nilpotent group. We also give some new examples of manifolds with actions.     

Role of information in the stochastic zero-sum differential game

In this paper, a linear-quadratic Gaussian zero-sum differential game is studied. Maneuverability is defined to measure players' strength. It is shown that a more maneuverable player would prefer a more observable information system. An example is given to show that a more controllable player might not prefer more observable measurements in the stochastic environment.The research reported in this paper was made possible through support extended to the Division of Engineering and Applied Physics, Harvard University, by the US Office of Naval Research under the Joint Services Electronics Program by Contract No. N00014-75-c-0648 and by the National Science Foundation under Grant No. GK31511.