Superlinearly convergent algorithm for min-max problems

Algorithms for solving the problem of minimizing the maximum of a finite number of functions are proposed and analyzed. Quadratic approximations to the functions are employed in the determination of a search direction. Global convergence is proven and it is shown that a quadratic rate of convergence is obtained.This research was sponsored in part by National Science Foundation Grant ECS-81-21149, Air Force Office of Scientific Research Grant 83-0361, Office of Naval Research Contract N00014-83-K-0602, Semiconductor Research Corporation Contract SRC-82-11-008, State of California MICRO Program, and General Electric Company.     

Finite convergence of algorithms for nonlinear programs and variational inequalities

Algorithms for nonlinear programming and variational inequality problems are, in general, only guaranteed to converge in the limit to a Karush-Kuhn-Tucker point, in the case of nonlinear programs, or to a solution in the case of variational inequalities. In this paper, we derive sufficient conditions for nonlinear programs with convex feasible sets such that any convergent algorithm can be modified, by adding a convex subproblem with a linear objective function, to guarantee finite convergence in a generalized sense. When the feasible set is polyhedral, the subproblem is a linear program and finite convergence is obtained. Similar results are also developed for variational inequalities.The research of the first author was supported in part by the Office of Naval Research under Contract No. N00014-86-K-0173.The authors are indebted to Professors Olvi Mangasarian, Garth McCormick, Jong-Shi Pang, Hanif Sherali, and Hoang Tuy for helpful comments and suggestions and to two anonymous referees for constructive remarks and for bringing to their attention the results in Refs. 13 and 14.     

A generalization of the Frank—Wolfe theorem

The Frank—Wolfe theorem states that a quadratic function, bounded below on a nonempty polyhedral convex set, attains its infimum there. This paper gives sufficient conditions under which a function either attains its infimum on a nonempty polyhedral convex set or is unbounded below on some halfline of that set. Quadratic functions are shown to satisfy these sufficient conditions.Research and reproduction of this report were partially supported by the National Science Foundation Grant MCS76-81259; and the Office of Naval Research Contract N00014-75-C-0267.     

On the convergence of the coordinate descent method for convex differentiable minimization

The coordinate descent method enjoys a long history in convex differentiable minimization. Surprisingly, very little is known about the convergence of the iterates generated by this method. Convergence typically requires restrictive assumptions such as that the cost function has bounded level sets and is in some sense strictly convex. In a recent work, Luo and Tseng showed that the iterates are convergent for the symmetric monotone linear complementarity problem, for which the cost function is convex quadratic, but not necessarily strictly convex, and does not necessarily have bounded level sets. In this paper, we extend these results to problems for which the cost function is the composition of an affine mapping with a strictly convex function which is twice differentiable in its effective domain. In addition, we show that the convergence is at least linear. As a consequence of this result, we obtain, for the first time, that the dual iterates generated by a number of existing methods for matrix balancing and entropy optimization are linearly convergent.This work was partially supported by the U.S. Army Research Office, Contract No. DAAL03-86-K-0171, by the National Science Foundation, Grant No. ECS-8519058, and by the Science and Engineering Research Board of McMaster University.     

Descent methods for convex essentially smooth minimization

Consider the problem of minimizing a convex essentially smooth function over a polyhedral set. For the special case where the cost function is strictly convex, we propose a feasible descent method for this problem that chooses the descent directions from a finite set of vectors. When the polyhedral set is the nonnegative orthant or the entire space, this method reduces to a coordinate descent method which, when applied to certain dual of linearly constrained convex programs with strictly convex essentially smooth costs, contains as special cases a number of well-known dual methods for quadratic and entropy (either –logx orx logx) optimization. Moreover, convergence of these dual methods can be inferred from a general convergence result for the feasible descent method. When the cost function is not strictly convex, we propose an extension of the feasible descent method which makes descent along the elementary vectors of a certain subspace associated with the polyhedral set. The elementary vectors are not stored, but generated using the dual rectification algorithm of Rockafellar. By introducing an -complementary slackness mechanism, we show that this extended method terminates finitely with a solution whose cost is within an order of of the optimal cost. Because it uses the dual rectification algorithm, this method can exploit the combinatorial structure of the polyhedral set and is well suited for problems with a special (e.g., network) structure.This work was partially supported by the US Army Research Office Contract No. DAAL03-86-K-0171 and by the National Science Foundation Grant No. ECS-85-19058.     

Maximal domains of quasi-convexity and pseudo-convexity for quadratic functions

We study quasi-convex and pseudo-convex quadratic functions on solid convex sets. This generalizes Martos' results in [12] and [13] by using Koecher's results in [8].This research was supported by Hydro—Quebec; University of Montreal; Office of Naval Research, Contract N-00014-47-A0112-0011; National Science Foundation, Grant GP 25738.     

Computable bounds on parametric solutions of convex problems

We present a new method for computing bounds on parametric solutions of convex problems. The approach is based on a uniform quadratic underestimation of the objective function and a simple technique for the calculation of bounds on the optimal value function.Research supported by Grant ECS-8619859, National Science Foundation and Contract N00017-86-K-0052, Office of Naval Research.     

On the convergence of the exponential multiplier method for convex programming

In this paper, we analyze the exponential method of multipliers for convex constrained minimization problems, which operates like the usual Augmented Lagrangian method, except that it uses an exponential penalty function in place of the usual quadratic. We also analyze a dual counterpart, the entropy minimization algorithm, which operates like the proximal minimization algorithm, except that it uses a logarithmic/entropy proximal term in place of a quadratic. We strengthen substantially the available convergence results for these methods, and we derive the convergence rate of these methods when applied to linear programs.Research supported by the National Science Foundation under Grant DDM-8903385, and the Army Research Office under Grant DAAL03-86-K-0171.     

Dual coordinate ascent methods for non-strictly convex minimization

We consider a dual method for solving non-strictly convex programs possessing a certain separable structure. This method may be viewed as a dual version of a block coordinate ascent method studied by Auslender [1, Section 6]. We show that the decomposition methods of Han [6, 7] and the method of multipliers may be viewed as special cases of this method. We also prove a convergence result for this method which can be applied to sharpen the available convergence results for Han's methods.The main part of this research was conducted while the author was with the Laboratory for Information and Decision Systems, M.I.T., Cambridge, with support by the U.S. Army Research Office, Contract No. DAAL03-86-K-0171 (Center for Intelligent Control Systems) and by the National Science Foundation under Grant ECS-8519058.     

Decomposition algorithm for convex differentiable minimization

In this paper, we propose a decomposition algorithm for convex differentiable minimization. This algorithm at each iteration solves a variational inequality problem obtained by adding to the gradient of the cost function a strongly proximal related function. A line search is then performed in the direction of the solution to this variational inequality (with respect to the original cost). If the constraint set is a Cartesian product ofm sets, the variational inequality decomposes intom coupled variational inequalities, which can be solved in either a Jacobi manner or a Gauss-Seidel manner. This algorithm also applies to the minimization of a strongly convex (possibly nondifferentiable) cost subject to linear constraints. As special cases, we obtain the GP-SOR algorithm of Mangasarian and De Leone, a diagonalization algorithm of Feijoo and Meyer, the coordinate descent method, and the dual gradient method. This algorithm is also closely related to a splitting algorithm of Gabay and a gradient projection algorithm of Goldstein and of Levitin-Poljak, and has interesting applications to separable convex programming and to solving traffic assignment problems.This work was partially supported by the US Army Research Office Contract No. DAAL03-86-K-0171 and by the National Science Foundation Grant No. ECS-85-19058. The author thanks the referees for their many helpful comments, particularly for suggesting the use of a general functionH instead of that given by (4).     

Properties of the optimal trajectories for coplanar,aeroassisted orbital transfer

We show that the sequences of function values constructed by two versions of a minimax algorithm converge linearly to the minimum values. Both versions use the Pshenichnyi-Pironneau-Polak search direction subprocedure; the first uses an exact line search to determine the stepsize, while the second one uses an Armijo-type stepsize rule. The proofs depend on a second-order sufficiency condition, but not on strict complementary slackness. Minimax problems in which each function appearing in the max is a composition of a twice continuously differentiable function with a linear function typically do not satisfy second-order sufficiency conditions. Nevertheless, we show that, on such minimax problems, the two algorithms do converge linearly when the outer functions are convex and strict complementary slackness holds at the solutions.The research reported herein was sponsored in part by the National Science Foundation Grant ECS-87-13334, the Air Force Office of Scientific Research Contract AFOSR-86-0116, the State of California MICRO Program Grant 532410-19900, and a Howard Hughes Doctoral Fellowship (Hughes Aircraft Company). The authors would like to thank the referees for their helpful suggestions.     

Existence of a σ finite invariant measure for a Markov process on a locally compact space

A σ finite invariant measure is found, for a Markov process, on a locally compact space, which maps continuous functions to continuous functions. The research reported in this document has been sponsored by the Air Force Office of Scientific Research under Grant AF EOAR 66-18, through the European Office of Aerospace Research (OAR) United States Air Force.     

Dual active sets and constrained optimization

Two dual methods for solving constrained optimization problems are presented: the Dual Active Set algorithm and an algorithm combining an unconstrained minimization scheme, an augmented Lagrangian and multiplier updates. A new preconditioner is introduced that has a significant impact on the speed of convergence.This research was supported by US Army Research Office Contract DAAL03-89-G-0082, and by National Science Foundation Grant DMS-9022899.     

A proximal-based decomposition method for convex minimization problems

This paper presents a decomposition method for solving convex minimization problems. At each iteration, the algorithm computes two proximal steps in the dual variables and one proximal step in the primal variables. We derive this algorithm from Rockafellar's proximal method of multipliers, which involves an augmented Lagrangian with an additional quadratic proximal term. The algorithm preserves the good features of the proximal method of multipliers, with the additional advantage that it leads to a decoupling of the constraints, and is thus suitable for parallel implementation. We allow for computing approximately the proximal minimization steps and we prove that under mild assumptions on the problem's data, the method is globally convergent and at a linear rate. The method is compared with alternating direction type methods and applied to the particular case of minimizing a convex function over a finite intersection of closed convex sets.Corresponding author. Partially supported by Air Force Office of Scientific Research Grant 91-0008 and National Science Foundation Grant DMS-9201297.     

Control of partially observed diffusions

The optimal control of a partially observed diffusion is discussed when the control parameter is present in both the drift and diffusion coefficients. Using a differentiation result of Blagovescenskii and Freidlin, and adapting techniques of Bensoussan, we obtain a stochastic minimum principle.This research was partially supported by NSERC Grant A7964, by the US Air Force Office of Scientific Research Contract AFOSR-86-0332, and by the US Army Research Office Contract DAAL03-87-K-0102.     

Algorithmic equivalence in quadratic programming,I: A least-distance programming problem

It is demonstrated that Wolfe's algorithm for finding the point of smallest Euclidean norm in a given convex polytope generates the same sequence of feasible points as does the van de Panne-Whinstonsymmetric algorithm applied to the associated quadratic programming problem. Furthermore, it is shown how the latter algorithm may be simplified for application to problems of this type.This work was supported by the National Science Foundation, Grant No. MCS-71-03341-AO4, and by the Office of Naval Research, Contract No. N00014-75-C-0267.     

An exact penalty function algorithm for optimal control problems with control and terminal equality constraints,part 1

The presence of control constraints, because they are nondifferentiable in the space of control functions, makes it difficult to cope with terminal equality constraints in optimal control problems. Gradient-projection algorithms, for example, cannot be employed easily. These difficulties are overcome in this paper by employing an exact penalty function to handle the cost and terminal equality constraints and using the control constraints to define the space of permissible search directions in the search-direction subalgorithm. The search-direction subalgorithm is, therefore, more complex than the usual linear program employed in feasible-directions algorithms. The subalgorithm approximately solves a convex optimal control problem to determine the search direction; in the implementable version of the algorithm, the accuracy of the approximation is automatically increased to ensure convergence.This work was supported by the United Kingdom Science Research Council, by the US Army Research Office, Contract No. DAAG-29-73-C-0025, and by the National Science Foundation, Grant No. ENG-73-08214-A01.     

Least-index resolution of degeneracy in quadratic programming

In this study, we combine least-index pivot selection rules with Keller's algorithm for quadratic programming to obtain a finite method for processing degenerate problems.Research and reproduction of this report were partially supported by National Science Foundation Grant MCS76-81259; and the Office of Naval Research Contract N00014-75-C-0267.     

On the computation of the optimal cost function for discrete time Markov models with partial observations

We consider several applications of two state, finite action, infinite horizon, discrete-time Markov decision processes with partial observations, for two special cases of observation quality, and show that in each of these cases the optimal cost function is piecewise linear. This in turn allows us to obtain either explicit formulas or simplified algorithms to compute the optimal cost function and the associated optimal control policy. Several examples are presented.Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-86-0029, in part by the National Science Foundation under Grant ECS-8617860, in part by the Advanced Technology Program of the State of Texas, and in part by the DoD Joint Services Electronics Program through the Air Force Office of Scientific Research (AFSC) Contract F49620-86-C-0045.     

Control of a hybrid conditionally linear Gaussian process

A control problem is considered where the coefficients of the linear dynamics are functions of a noisily observed Markov chain. The approximation introduced is to consider these coefficients as functions of the filtered estimate of the state of the chain; this gives rise to a finite-dimensional conditional Kalman filter. A minimum principle and a new equation for an adjoint process are obtained.This research was partially supported by NSERC under Grant A-7964, by the US Air Force Office of Scientific Research under Contract AFOSR-86-0332, and by the US Army Research Office under Contract DAAL03-87-0102.The authors obtained these results during a visit to UCSD by the first author in January 1990. This author wishes to thank Professor D. D. Sworder and his department for their hospitality.