An alternative method for a global analysis of quadratic programs in a finite number of steps

This paper considers the global analysis of general quadratic programs in a finite number of steps. A procedure is presented for recursively finding either the global minimum or a halfline of the constraint set along which the minimand is unbounded below.Research was partially supported by the U.S. Energy Research and Development Administration Contract EY-76-S-03-0326 PA #18; the Office of Naval Research Contracts N00014-75-C-0267 and N00014-75-C-0865; and the National Science Foundation Grants MCS76-20019 and MCS76-81259.     

A weighted gram-schmidt method for convex quadratic programming

Range-space methods for convex quadratic programming improve in efficiency as the number of constraints active at the solution decreases. In this paper we describe a range-space method based upon updating a weighted Gram-Schmidt factorization of the constraints in the active set. The updating methods described are applicable to both primal and dual quadratic programming algorithms that use an active-set strategy. Many quadratic programming problems include simple bounds on all the variables as well as general linear constraints. A feature of the proposed method is that it is able to exploit the structure of simple bound constraints. This allows the method to retain efficiency when the number ofgeneral constraints active at the solution is small. Furthermore, the efficiency of the method improves as the number of active bound constraints increases. This research was supported by the U.S. Department of Energy Contract DE-AC03-76SF00326, PA No. DE-AT03-76ER72018; National Science Foundation Grants MCS-7926009 and ECS-8012974; the Office of Naval Research Contract N00014-75-C-0267; and the U.S. Army Research Office Contract DAAG29-79-C-0110. The work of Nicholas Gould was supported by the Science and Engineering Research Council of Great Britain.     

On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method

Interest in linear programming has been intensified recently by Karmarkar’s publication in 1984 of an algorithm that is claimed to be much faster than the simplex method for practical problems. We review classical barrier-function methods for nonlinear programming based on applying a logarithmic transformation to inequality constraints. For the special case of linear programming, the transformed problem can be solved by a “projected Newton barrier” method. This method is shown to be equivalent to Karmarkar’s projective method for a particular choice of the barrier parameter. We then present details of a specific barrier algorithm and its practical implementation. Numerical results are given for several non-trivial test problems, and the implications for future developments in linear programming are discussed. The research of the Stanford authors was supported by the U.S. Department of Energy Contract DE-AA03-76SF00326, PA No. DE-AS03-76ER72018; National Science Foundation Grants DCR-8413211 and ECS-8312142; the Office of Naval Research Contract N00014-85-K-0343; and the U.S. Army Research Office Contract DAAG29-84-K-0156. The research of J.A. Tomlin was supported by Ketron, Inc. and the Office of Naval Research Contract N00014-85-C-0338.     

Low order polynomial bounds on the expected performance of local improvement algorithms

We present a general abstract model of local improvement, applicable to such diverse cases as principal pivoting methods for the linear complementarity problem and hill climbing in artificial intelligence. The model accurately predicts the behavior of the algorithms, and allows for a variety of probabilistic assumptions that permit degeneracy. Simulation indicates an approximately linear average number of iterations under a variety of probability assumptions. We derive theoretical bounds of 2en logn and en ² for different distributions, respectively, as well as polynomial bounds for a broad class of probability distributions. We conclude with a discussion of the applications of the model to LCP and linear programming.The author was supported by the New Faculty Research Development Program of the Georgia Institute of Technology. This work is based on the author's Ph.D. thesis, performed under George Dantzig at Stanford 1978–81, at the Systems Optimization Laboratory. While at Stanford, research was supported in part by Department of Energy Contract AM03-76SF00326, PA #DE-AT03-76ER72018; Office of Naval Research Contract N00014-75-C-0267; National Science Foundation Grants MCS76-81259, MCS-7926009 and ECS-8012974; and Army Research Office Contract DAA29-79-C-0110. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

Optimal approximation of sparse hessians and its equivalence to a graph coloring problem

We consider the problem of approximating the Hessian matrix of a smooth non-linear function using a minimum number of gradient evaluations, particularly in the case that the Hessian has a known, fixed sparsity pattern. We study the class of Direct Methods for this problem, and propose two new ways of classifying Direct Methods. Examples are given that show the relationships among optimal methods from each class. The problem of finding a non-overlapping direct cover is shown to be equivalent to a generalized graph coloring problem—the distance-2 graph coloring problem. A theorem is proved showing that the general distance-k graph coloring problem is NP-Complete for all fixedk≥2, and hence that the optimal non-overlapping direct cover problem is also NP-Complete. Some worst-case bounds on the performance of a simple coloring heuristic are given. An appendix proves a well-known folklore result, which gives lower bounds on the number of gradient evaluations needed in any possible approximation method. This research was partially supported by the Department of Energy Contract AM03-76SF00326. PA#DE-AT03-76ER72018; Army Research Office Contract DAA29-79-C-0110; Office of Naval Research Contract N00014-74-C-0267; National Science Foundation Grants MCS76-81259, MCS-79260099 and ECS-8012974.     

Large-scale linearly constrained optimization

An algorithm for solving large-scale nonlinear programs with linear constraints is presented. The method combines efficient sparse-matrix techniques as in the revised simplex method with stable quasi-Newton methods for handling the nonlinearities. A general-purpose production code (MINOS) is described, along with computational experience on a wide variety of problems.This research was supported by the U.S. Office of Naval Research (Contract N00014-75-C-0267), the National Science Foundation (Grants MCS71-03341 A04, DCR75-04544), the U.S. Energy Research and Development Administration (Contract E(04-3)-326 PA #18), the Victoria University of Wellington, New Zealand, and the Department of Scientific and Industrial Research Wellington, New Zealand.     

Critical point theorems for indefinite functionals

A variational principle of a minimax nature is developed and used to prove the existence of critical points for certain variational problems which are indefinite. The proofs are carried out directly in an infinite dimensional Hilbert space. Special cases of these problems previously had been tractable only by an elaborate finite dimensional approximation procedure. The main applications given here are to Hamiltonian systems of ordinary differential equations where the existence of time periodic solutions is established for several classes of Hamiltonians.Supported in part by the U.S. Army under Contract No. DAAG-29-75-C-0024 and by the Conseglio Nazionale delle Ricerche-Gruppo Nazionale Analisi Funzionale e ApplicazioneSupported in part by the J.S. Guggenheim Memorial Foundation, and by the Office of Naval Research under Contract No. N00014-76-C-0300. Reproduction in whole or in part is permitted for any purpose of the U.S. Government     

Properties of a representation of a basis for the null space

Given a rectangular matrixA(x) that depends on the independent variablesx, many constrained optimization methods involve computations withZ(x), a matrix whose columns form a basis for the null space ofA ^T(x). WhenA is evaluated at a given point, it is well known that a suitableZ (satisfyingA ^T Z = 0) can be obtained from standard matrix factorizations. However, Coleman and Sorensen have recently shown that standard orthogonal factorization methods may produce orthogonal bases that do not vary continuously withx; they also suggest several techniques for adapting these schemes so as to ensure continuity ofZ in the neighborhood of a given point.This paper is an extension of an earlier note that defines the procedure for computingZ. Here, we first describe howZ can be obtained byupdating an explicit QR factorization with Householder transformations. The properties of this representation ofZ with respect to perturbations inA are discussed, including explicit bounds on the change inZ. We then introduceregularized Householder transformations, and show that their use implies continuity of the full matrixQ. The convergence ofZ andQ under appropriate assumptions is then proved. Finally, we indicate why the chosen form ofZ is convenient in certain methods for nonlinearly constrained optimization.The research of the Stanford authors was supported by the U.S. Department of Energy Contract DE-AM03-76SF00326, PA No. DE-AT03-76ER72018; the National Science Foundation Grants MCS-7926009 and ECS-8312142; the Office of Naval Research Contract N00014-75-C-0267; and the U.S. Army Research Office Contract DAAG29-84-K-0156.The research of G.W. Stewart was supported by the Air Force Office of Scientific Research Contract AFOSR-82-0078.     

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.     

The value of the stochastic solution in stochastic linear programs with fixed recourse

Stochastic linear programs have been rarely used in practical situations largely because of their complexity. In evaluating these problems without finding the exact solution, a common method has been to find bounds on the expected value of perfect information. In this paper, we consider a different method. We present bounds on the value of the stochastic solution, that is, the potential benefit from solving the stochastic program over solving a deterministic program in which expected values have replaced random parameters. These bounds are calculated by solving smaller programs related to the stochastic recourse problem.This paper is an extension of part of the author's dissertation in the Department of Operations Research, Stanford University, Stanford, California. The research was supported at Stanford by the Department of Energy under Contract DE-AC03-76SF00326, PA#DE-AT03-76ER72018, Office of Naval Research under Contract N00014-75-C-0267 and the National Science Foundation under Grants MCS76-81259, MCS-7926009 and ECS-8012974 (formerly ENG77-06761).     

Lattice embeddings below a nonlow2 recursively enumerable degree

We introduce techniques that allow us to embed below an arbitary nonlow₂ recursively enumerable degree any lattice currently known to be embeddable into the recursively enumerable degrees. Research partially supported by NSF Grants DMS-9204308, DMS-93-44740, a US-NZ binational grant NSF 90-20558, the U.S. ARO through ACSyAM at the Mathematical Sciences Institute of Cornell Univrsity Contract DAAL03-91-C-0027 and the IGC of Victoria University.     

Optimization of unconstrained functions with sparse Hessian matrices—Quasi-Newton methods

Newton-type methods and quasi-Newton methods have proven to be very successful in solving dense unconstrained optimization problems. Recently there has been considerable interest in extending these methods to solving large problems when the Hessian matrix has a known a priori sparsity pattern. This paper treats sparse quasi-Newton methods in a uniform fashion and shows the effect of loss of positive-definiteness in generating updates. These sparse quasi-Newton methods coupled with a modified Cholesky factorization to take into account the loss of positive-definiteness when solving the linear systems associated with these methods were tested on a large set of problems. The overall conclusions are that these methods perform poorly in general—the Hessian matrix becomes indefinite even close to the solution and superlinear convergence is not observed in practice. Research for this paper was performed at the Department of Operations Research, Stanford, CA 94305. The research was partially supported by the Department of Energy Contract AM03-76SF00326. PA# DE-AT03-76ER72018: Office of Naval Research Contract N00014-75-C-0267; National Science Foundation Grants MCS-7681259, MCS-7926009 and ECS-8012974.     

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.     

Computing the Ehrhart polynomial of a convex lattice polytope

We prove that computation of any fixed number of highest coefficients of the Ehrhart polynomial of an integral polytope can be reduced in polynomial time to computation of the volumes of faces. This research was supported by the United States Army Research Office through the Army Center of Excellence for Symbolic Methods in Algorithmic Mathematics (ACSyAM), Mathematical Sciences Institute of Cornell University, Contract DAAL03-91-C-0027.     

Distributed computing viewed as a team problem with constraints

The optimal distribution of the workload in a system of interconnected computer units is considered. Formulated as a team decision problem with a singular cost criterion and with equality and inequality constraints, it is shown that the problem admits always a unique piecewise linear strategy which is globally optimal. Some interesting particular cases are studied.The research reported in this paper was made possible through support from the Office of Naval Research under the Joint Services Electronics Program by Contract No. N00014-75-C-0648 and Contract No. N00014-77-C-0531 and by the National Science Foundation, Grant No. ENG-76-11824.     

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.     

Methods of conjugate directions versus quasi-Newton methods

It is shown that algorithms for minimizing an unconstrained functionF(x), x E ⁿ , which are solely methods of conjugate directions can be expected to exhibit only ann or (n–1) step superlinear rate of convergence to an isolated local minimizer. This is contrasted with quasi-Newton methods which can be expected to exhibit every step superlinear convergence. Similar statements about a quadratic rate of convergence hold when a Lipschitz condition is placed on the second derivatives ofF(x). Research was supported in part by Army Research Office, Contract Number DAHC 19-69-C-0017 and the Office of Naval Research, Contract Number N00014-71-C-0116 (NR 047-99).     

Fast algorithms for the integral equations of the inverse scattering problem

The Gelfand-Levitan and Marchenko equations of inverse scattering theory are integral equations with Toeplitz and Hankel kernels respectively. It is shown that these facts can be used to reduce the integral equations to differential equations which can be solved with an order of magnitude less computation than generally envisaged.This work was supported by the Army Research Office under Contract DAAG29-77-C-0042, by the Air Force Office of Scientific Research, Air Force Systems Command, under Contract AF44-620-74-C-0068 and the Australian Research Grants Committee.     

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.     

Triangulations (tilings) and certain block triangular matrices

For a convex polygonP withn sides, a ‘partitioning’ ofP inton−2 nonoverlapping triangles each of whose vertices is a vertex ofP is called a triangulation or tiling, and each triangle is a tile. Each tile has a given cost associated with it which may differ one from another. This paper considers the problem of finding a tiling ofP such that the sum of the costs of the tiles used is a minimum, and explores the curiosity that (an abstract formulation of) it can be cast as a linear program. Further the special structure of the linear program permits a recursive O(n ³) algorithm. Research and reproduction of this report were partially supported by the National Science Foundation Grants MCS-8119774, MCS-7926009 and ECS-8012974; Department of Energy Contract DE-AM03-76SF00326, PA# DE-AT03-76ER72018; Office of Naval Research Contract N00014-75-C-0267. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the author(s) and donot necessarily reflect the views of the above sponsors.