A robust sequential quadratic programming method

The sequential quadratic programming method developed by Wilson, Han and Powell may fail if the quadratic programming subproblems become infeasible, or if the associated sequence of search directions is unbounded. This paper considers techniques which circumvent these difficulties by modifying the structure of the constraint region in the quadratic programming subproblems. Furthermore, questions concerning the occurrence of an unbounded sequence of multipliers and problem feasibility are also addressed.Work supported in part by the National Science Foundation under Grant No. DMS-8602399 and by the Air Force Office of Scientific Research under Grant No. ISSA-860080.Work supported in part by the National Science Foundation under Grant No. DMS-8602419.     

Transcendental geometric programs

This paper treats a class of posynomial-like functions whose variables may appear also as exponents or in logarithms. It is shown that the resulting programs, called transcendental geometric programs, retain many useful properties of ordinary geometric programs, although the new class of problems need not have unique minima and cannot, in general, be transformed into convex programs. A duality theory, analogous to geometric programming duality, is formulated under somewhat more restrictive conditions. The dual constraints are not all linear, but the notion ofdegrees of difficulty is maintained in its geometric programming sense. One formulation of the dual program is shown to be a generalization of the chemical equilibrium problem where correction factors are added to account for nonideality. Some of the computational difficulties in solving transcendental programs are discussed briefly.This research was partially supported by the National Institute of Health Grant No. GM-14789; Office of Naval Research under Contract No. N00014-75-C-0276; National Science Foundation Grant No. MPS-71-03341 A03; and the US Atomic Energy Commission Contract No. AT(04-3)-326 PA #18.     

Solving geometric programs using GRG: Results and comparisons

This paper describes the performance of a general-purpose GRG code for nonlinear programming in solving geometric programs. The main conclusions drawn from the experiments reported are: (i) GRG competes well with special-purpose geometric programming codes in solving geometric programs; and (ii) standard time, as defined by Colville, is an inadequate means of compensating for different computing environments while comparing optimization algorithms.This research was partially supported by the Office of Naval Research under Contracts Nos. N00014-75-C-0267 and N00014-75-C-0865, the US Energy Research and Development Administration, Contract No. E(04-3)-326 PA-18, and the National Science Foundation, Grant No. DCR75-04544 at Stanford University; and by the Office of Naval Research under Contract No. N00014-75-C-0240, and the National Science Foundation, Grant No. SOC74-23808, at Case Western Reserve University.     

A quadratic programming algorithm

By using conjugate directions a method for solving convex quadratic programming problems is developed. The algorithm generates a sequence of feasible solutions and terminates after a finite number of iterations. Extensions of the algorithm for nonconvex and large structured quadratic programming problems are discussed.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041 and in part by the Natural Sciences and Engineering Research Council of Canada under Grant Nos. A 8189 and E 5582.     

Fenchel's duality theorem in generalized geometric programming

Fenchel's duality theorem is extended to generalized geometric programming with explicit constraints—an extension that also generalizes and strengthens Slater's version of the Kuhn-Tucker theorem.This research was sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant No. AFOSR-73-2516.     

Parallel orthogonal factorization null-space method for dynamic quadratic programming

An algorithm has been developed to solve quadratic programs that have a dynamic programming structure. It has been developed for use as part of a parallel trajectory optimization algorithm and aims to achieve significant speed without sacrificing numerical stability. the algorithm makes use of the dynamic programming problem structure and the domain decomposition approach. It parallelizes the orthogonal factorization null-space method of quadratic programming by developing a parallel orthogonal factorization and a parallel Cholesky factorization. Tests of the algorithm on a 32-node INTEL iPSC/2 hypercube demonstrate speedup factors as large as 10 in comparison to the fastest known equivalent serial algorithm.This research was supported in part by the National Aeronautics and Space Administration under Grant No. NAG-1-1009.     

An accelerated multiplier method for nonlinear programming

This paper describes an accelerated multiplier method for solving the general nonlinear programming problem. The algorithm poses a sequence of unconstrained optimization problems. The unconstrained problems are solved using a rank-one recursive algorithm described in an earlier paper. Multiplier estimates are obtained by minimizing the error in the Kuhn-Tucker conditions using a quadratic programming algorithm. The convergence of the sequence of unconstrained problems is accelerated by using a Newton-Raphson extrapolation process. The numerical effectiveness of the algorithm is demonstrated on a relatively large set of test problems.This work was supported by the US Air Force under Contract No. F04701-74-C-0075.     

Composite geometric programming

Geometric programming is based on functions called posynomials, the terms of which are log-linear. This class of programs is extended from the composition of an exponential and a linear function to an exponential and a convex function. The resulting duality theory for composite geometric programs retains many of the qualities of geometric programming duality, while at the same time encompassing new areas of application. As an application, composite geometric programming is applied to exponential geometric programming. A pure dual is developed for the first time and used to solve a problem from the literature.This research was supported by the Air Force Office of Scientific Research, Grant No. AFOSR-83-0234.     

The inverse gravimetry problem: An application to the northern San Francisco craton granite

From the knowledge of the anomalies of the gravitational field, we reconstruct the mass density distribution in a large region of the state of Bahia (Brazil). This inverse gravimetry problem has been translated into a linear programming problem and solved using the simplex method. Both two-dimensional and three-dimensional models have been considered.This research was supported by the European Research Office of the US Army under Contract No. DAJA 45-86-C-0028 with the University of Rome-La Sapienza and by the Ministero Pubblica Istruzione under Contract (60%)-1987 with the University of Camerino.     

Bilinear programming and structured stochastic games

One-step algorithms are presented for two classes of structured stochastic games, namely, those with additive rewards and transitions and those which have switching controllers. Solutions to such classes of games under the average reward criterion can be derived from optimal solutions to appropriate bilinear programs. The validity of using bilinear programming as a solution method follows from two preliminary theorems, the first of which is a complete classification of undiscounted stochastic games with optimal stationary strategies. The second of these preliminary theorems relaxes the conditions of the classification theorem for certain classes of stochastic games and provides the basis for the bilinear programming results. Analogous results hold for the discounted stochastic games with the above special structures.This research was supported in part by the Air Force Office of Scientific Research and by the National Science Foundation under Grant No. ECS-850-3440.     

Rates of convergence for a method of centers algorithm

Convergence of a method of centers algorithm for solving nonlinear programming problems is considered. The algorithm is defined so that the subproblems that must be solved during its execution may be solved by finite-step procedures. Conditions are given under which the algorithm generates sequences of feasible points and constraint multiplier vectors that have accumulation points satisfying the Fritz John or the Kuhn-Tucker optimality conditions. Under stronger assumptions, linear convergence rates are established for the sequences of objective function, constraint function, feasible point, and multiplier values.This work was supported in part by the National Aeronautics and Space Administration, Predoctoral Traineeship No. NsG(T)-117, and by the National Science Foundation, Grants No. GP-25081 and No. GK-32710.The author wishes to thank Donald M. Topkis for his valuable criticism of an earlier version of this paper and a referee for his helpful comments.     

A convergence theory for a class of anti-jamming strategies

A convergence theory for a class of anti-jamming strategies for nonlinear programming algorithms is presented. This theory generalizes previous results in this area by Zoutendijk, Topkis and Veinott, Mangasarian, and others; it is applicable to algorithms in which the anti-jamming parameter is fixed at some positive value as well as to algorithms in which it tends to zero. In addition, under relatively weak hypotheses, convergence of the entire sequence of iterates is proved.This research was sponsored by the United States Army under Contract No. DA-31-124-ARO-D-462.     

A globally convergent method for nonlinear programming

Recently developed Newton and quasi-Newton methods for nonlinear programming possess only local convergence properties. Adopting the concept of the damped Newton method in unconstrained optimization, we propose a stepsize procedure to maintain the monotone decrease of an exact penalty function. In so doing, the convergence of the method is globalized.This research was supported in part by the National Science Foundation under Grant No. ENG-75-10486.     

A parameterized hessian quadratic programming problem

We present a general active set algorithm for the solution of a convex quadratic programming problem having a parametrized Hessian matrix. The parametric Hessian matrix is a positive semidefinite Hessian matrix plus a real parameter multiplying a symmetric matrix of rank one or two. The algorithm solves the problem for all parameter values in the open interval upon which the parametric Hessian is positive semidefinite. The algorithm is general in that any of several existing quadratic programming algorithms can be extended in a straightforward manner for the solution of the parametric Hessian problem.This research was supported by the Natural Sciences and Engineering Research Council under Grant No. A8189 and under a Postgraduate Scholarship, by an Ontario Graduate Scholarship, and by the University of Windsor Research Board under Grant No. 9432.     

A parameterized hessian quadratic programming problem

We present a general active set algorithm for the solution of a convex quadratic programming problem having a parametrized Hessian matrix. The parametric Hessian matrix is a positive semidefinite Hessian matrix plus a real parameter multiplying a symmetric matrix of rank one or two. The algorithm solves the problem for all parameter values in the open interval upon which the parametric Hessian is positive semidefinite. The algorithm is general in that any of several existing quadratic programming algorithms can be extended in a straightforward manner for the solution of the parametric Hessian problem. This research was supported by the Natural Sciences and Engineering Research Council under Grant No. A8189 and under a Postgraduate Scholarship, by an Ontario Graduate Scholarship, and by the University of Windsor Research Board under Grant No. 9432.     

An outer approximations algorithm for computer-aided design problems

This paper presents an implementable algorithm of the outer approximations type for solving nonlinear programming problems with functional inequality constraints. The algorithm was motivated by engineering design problems in circuit tolerancing, multivariable control, and shock-resistant structures.This research was sponsored by the National Science Foundation, Grant No. ENG73-08214A01, and the National Science Foundation (RANN), Grant No. ENV76-04264.     

A comparison of computational strategies for geometric programs

Numerous algorithms for the solution of geometric programs have been reported in the literature. Nearly all are based on the use of conventional programming techniques specialized to exploit the characteristic structure of either the primal or the dual or a transformed primal problem. This paper attempts to elucidate, via computational comparisons, whether a primal, a dual, or a transformed primal solution approach is to be preferred.The authors wish to thank Captain P. A. Beck and Dr. R. S. Dembo for making available their codes. This research was supported in part under ONR Contract No. N00014-76-C-0551 with Purdue University.     

Characterization of optimality in convex programming without a constraint qualification

Necessary and sufficient conditions of optimality are given for convex programming problems with no constraint qualification. The optimality conditions are stated in terms of consistency or inconsistency of a family of systems of linear inequalities and cone relations.This research was supported by Project No. NR-047-021, ONR Contract No. N00014-67-A-0126-0009 with the Center for Cybernetics Studies, The University of Texas; by NSF Grant No. ENG-76-10260 at Northwestern University; and by the National Research Council of Canada.     

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.     

Implementing proximal point methods for linear programming

We describe the application of proximal point methods to the linear programming problem. Two basic methods are discussed. The first, which has been investigated by Mangasarian and others, is essentially the well-known method of multipliers. This approach gives rise at each iteration to a weakly convex quadratic program which may be solved inexactly using a point-SOR technique. The second approach is based on the proximal method of multipliers, originally proposed by Rockafellar, for which the quadratic program at each iteration is strongly convex. A number of techniques are used to solve this subproblem, the most promising of which appears to be a two-metric gradient-projection approach. Convergence results are given, and some numerical experience is reported.This research was supported by National Science Foundation, Grant Nos. ASC-87-14009 and DMS-86-19903, and by Air Force Office of Scientific Research, Grant No. AFOSR-ISSA-87-0092. Part of this work was performed at Argonne National Laboratory. Computation was partly performed at the Pittsburgh Supercomputer Center under NSF Grant No. DMS-88-0033P and at the Argonne Advanced Computing Research Facility, whose support is gratefully acknowledged. The author thanks Olvi Mangasarian and Renato DeLeone for helpful discussions, and Jorge Moré for his valuable advice on the algorithms discussed in Section 3. The contributions of a referee, who provided helpful comments on an earlier version of this paper, are also acknowledged.