A Barrier Function Method for the Nonconvex Quadratic Programming Problem with Box Constraints

In this paper a barrier function method is proposed for approximating a solution of the nonconvex quadratic programming problem with box constraints. The method attempts to produce a solution of good quality by following a path as the barrier parameter decreases from a sufficiently large positive number. For a given value of the barrier parameter, the method searches for a minimum point of the barrier function in a descent direction, which has a desired property that the box constraints are always satisfied automatically if the step length is a number between zero and one. When all the diagonal entries of the objective function are negative, the method converges to at least a local minimum point of the problem if it yields a local minimum point of the barrier function for a sequence of decreasing values of the barrier parameter with zero limit. Numerical results show that the method always generates a global or near global minimum point as the barrier parameter decreases at a sufficiently slow pace.     

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 dual differentiable exact penalty function

A new penalty function is associated with an inequality constrained nonlinear programming problem via its dual. This penalty function is globally differentiable if the functions defining the original problem are twice globally differentiable. In addition, the penalty parameter remains finite. This approach reduces the original problem to a simple problem of maximizing a globally differentiable function on the product space of a Euclidean space and the nonnegative orthant of another Euclidean space. Many efficient algorithms exist for solving this problem. For the case of quadratic programming, the penalty function problem can be solved effectively by successive overrelaxation (SOR) methods which can handle huge problems while preserving sparsity features. Sponsored by the United States Army under Contract No. DAAG 29-80-C-0041. This material is based upon work supported by the National Science Foundation under Grants No. MCS-790166 and ENG-7903881.     

Exact penalty functions in nonlinear programming

It is shown that the existence of a strict local minimum satisfying the constraint qualification of [16] or McCormick's [12] second order sufficient optimality condition implies the existence of a class of exact local penalty functions (that is ones with a finite value of the penalty parameter) for a nonlinear programming problem. A lower bound to the penalty parameter is given by a norm of the optimal Lagrange multipliers which is dual to the norm used in the penalty function.Sponsored by the United States Army under Contract No. DAAG29-75-C-0024 and by the National Science Foundation under Grant No. MCS74-20584 A02.     

Exact penalty functions and stability in locally Lipschitz programming

In this paper we extend the theory of exact penalty functions for nonlinear programs whose objective functions and equality and inequality constraints are locally Lipschitz; arbitrary simple constraints are also allowed. Assuming a weak stability condition, we show that for all sufficiently large penalty parameter values an isolated local minimum of the nonlinear program is also an isolated local minimum of the exact penalty function. A tight lower bound on the parameter value is provided when certain first order sufficiency conditions are satisfied. We apply these results to unify and extend some results for convex programming. Since several effective algorithms for solving nonlinear programs with differentiable functions rely on exact penalty functions, our results provide a framework for extending these algorithms to problems with locally Lipschitz functions.     

Global Optimization of a Quadratic Functional with Quadratic Equality Constraints, Part 2

In this paper, we investigate a constrained optimization problem with a quadratic cost functional and two quadratic equality constraints. It is assumed that the cost functional is positive definite and that the constraints are both feasible and regular (but otherwise they are unrestricted quadratic functions). Thus, the existence of a global constrained minimum is assured. We develop a necessary and sufficient condition that completely characterizes the global minimum cost. Such a condition is of essential importance in iterative numerical methods for solving the constrained minimization problem, because it readily distinguishes between local minima and global minima and thus provides a stopping criterion for the computation. The result is similar to one obtained previously by the authors. In the previous result, we gave a characterization of the global minimum of a constrained quadratic minimization problem in which the cost functional was an arbitrary quadratic functional (as opposed to positive-definite here) and the constraints were at least positive-semidefinite quadratic functions (as opposed to essentially unrestricted here).     

A numerically stable dual method for solving strictly convex quadratic programs

An efficient and numerically stable dual algorithm for positive definite quadratic programming is described which takes advantage of the fact that the unconstrained minimum of the objective function can be used as a starting point. Its implementation utilizes the Cholesky and QR factorizations and procedures for updating them. The performance of the dual algorithm is compared against that of primal algorithms when used to solve randomly generated test problems and quadratic programs generated in the course of solving nonlinear programming problems by a successive quadratic programming code (the principal motivation for the development of the algorithm). These computational results indicate that the dual algorithm is superior to primal algorithms when a primal feasible point is not readily available. The algorithm is also compared theoretically to the modified-simplex type dual methods of Lemke and Van de Panne and Whinston and it is illustrated by a numerical example. This research was supported in part by the Army Research Office under Grant No. DAAG 29-77-G-0114 and in part by the National Science Foundation under Grant No. MCS-6006065.     

A global quadratic algorithm for solving a system of mixed equalities and inequalities

A new algorithm is proposed which, under mild assumptions, generates a sequence{x _i } that starting at any point inR ⁿ will converge to a setX defined by a mixed system of equations and inequalities. Any iteration of the algorithm requires the solution of a linear programming problem with relatively few constraints. By only assuming that the functions involved are continuously differentiable a superlinear rate of convergence is achieved. No convexity whatsoever is required by the algorithm.     

Global minimization of large-scale constrained concave quadratic problems by separable programming

The global minimization of a large-scale linearly constrained concave quadratic problem is considered. The concave quadratic part of the objective function is given in terms of the nonlinear variablesx R ⁿ , while the linear part is in terms ofy R ^k. For large-scale problems we may havek much larger thann. The original problem is reduced to an equivalent separable problem by solving a multiple-cost-row linear program with 2n cost rows. The solution of one additional linear program gives an incumbent vertex which is a candidate for the global minimum, and also gives a bound on the relative error in the function value of this incumbent. Ana priori bound on this relative error is obtained, which is shown to be 0.25, in important cases. If the incumbent is not a satisfactory approximation to the global minimum, a guaranteed-approximate solution is obtained by solving a single liner zero–one mixed integer programming problem. This integer problem is formulated by a simple piecewise-linear underestimation of the separable problem.This research was supported by the Division of Computer Research, National Science Foundation under Research Grant DCR8405489.Dedicated to Professor George Dantzig in honor of his 70th Birthday.     

Locally unique solutions of quadratic programs,linear and nonlinear complementarity problems

It is shown that McCormick's second order sufficient optimality conditions are also necessary for a solution to a quadratic program to be locally unique and hence these conditions completely characterize a locally unique solution of any quadratic program. This result is then used to give characterizations of a locally unique solution to the linear complementarity problem. Sufficient conditions are also given for local uniqueness of solutions of the nonlinear complementarity problem.Research supported by National Science Foundation Grant MCS74-20584 A02.     

Nonlinear programming via an exact penalty function: Global analysis

In this paper we motivate and describe an algorithm to solve the nonlinear programming problem. The method is based on an exact penalty function and possesses both global and superlinear convergence properties. We establish the global qualities here (the superlinear nature is proven in [7]). The numerical implementation techniques are briefly discussed and preliminary numerical results are given.This work is supported in part by NSERC Grant No. A8639 and the U.S. Dept. of Energy.     

A polynomially bounded algorithm for a singly constrained quadratic program

This paper presents a characterization of the solutions of a singly constrained quadratic program. This characterization is then used in the development of a polynomially bounded algorithm for this class of problems.     

Mixed-integer quadratic programming

This paper considers mixed-integer quadratic programs in which the objective function is quadratic in the integer and in the continuous variables, and the constraints are linear in the variables of both types. The generalized Benders' decomposition is a suitable approach for solving such programs. However, the program does not become more tractable if this method is used, since Benders' cuts are quadratic in the integer variables. A new equivalent formulation that renders the program tractable is developed, under which the dual objective function is linear in the integer variables and the dual constraint set is independent of these variables. Benders' cuts that are derived from the new formulation are linear in the integer variables, and the original problem is decomposed into a series of integer linear master problems and standard quadratic subproblems. The new formulation does not introduce new primary variables or new constraints into the computational steps of the decomposition algorithm.The author wishes to thank two anonymous referees for their helpful comments and suggestions for revising the paper.     

Estimating functions for noisy observations of ergodic diffusions

In this article, general estimating functions for ergodic diffusions sampled at high frequency with noisy observations are presented. The theory is formulated in terms of approximate martingale estimating functions based on local means of the observations, and simple conditions are given for rate optimality. The estimation of the diffusion parameter is faster than the estimation of the drift parameter, and the rate of convergence is classical for the drift parameter but not classical for the diffusion parameter. The link with specific minimum contrast estimators is established, as an example.     

Penalty for zero–one integer equivalent problem

The equivalence of zero–one integer programming and a concave quadratic penalty function problem has been shown by Raghavachari, for a sufficiently large value of the penalty. A lower bound for this penalty is obtained here, which in specific cases cannot be reduced.This research was supported in part by the Computer Science Section of the National Science Foundation under Research Grant MCS 8101214.     

Quadratic geometric programming with application to machining economics

Geometric Programming is extended to include convex quadratic functions. Generalized Geometric Programming is applied to this class of programs to obtain a convex dual program. Machining economics problems fall into this class. Such problems are studied by applying this duality to a nested set of three problems. One problem is zero degree of difficulty and the solution is obtained by solving a simple system of equations. The inclusion of a constraint restricting the force on the tool to be less than or equal to the breaking force provides a more realistic solution. This model is solved as a program with one degree of difficulty. Finally the behavior of the machining cost per part is studied parametrically as a function of axial depth. This research was supported by the Air Force Office of Scientific Research Grant AFOSR-83-0234     

Equivalence of some quadratic programming algorithms

We formulate a general algorithm for the solution of a convex (but not strictly convex) quadratic programming problem. Conditions are given under which the iterates of the algorithm are uniquely determined. The quadratic programming algorithms of Fletcher, Gill and Murray, Best and Ritter, and van de Panne and Whinston/Dantzig are shown to be special cases and consequently are equivalent in the sense that they construct identical sequences of points. The various methods are shown to differ only in the manner in which they solve the linear equations expressing the Kuhn-Tucker system for the associated equality constrained subproblems. Equivalence results have been established by Goldfarb and Djang for the positive definite Hessian case. Our analysis extends these results to the positive semi-definite case. This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant No. A8189.     

A continuous approch for globally solving linearly constrained quadratic

In a continuous approach we propose an efficient method for globally solving linearly constrained quadratic zero-one programming considered as a d.c. (difference of onvex functions) program. A combination of the d.c. optimization algorithm (DCA) which has a finite convergence, and the branch-and-bound scheme was studied. We use rectangular bisection in the branching procedure while the bounding one proceeded by applying d.c.algorithms from a current best feasible point (for the upper bound) and by minimizing a well tightened convex underestimation of the objective function on the current subdivided domain (for the lower bound). DCA generates a sequence of points in the vertex set of a new polytope containing the feasible domain of the problem being considered. Moreover if an iterate is integral then all following iterates are integral too.Our combined algorithm converges so quite often to an integer approximate solution.Finally, we present computational results of several test problems with up to 1800

variables which prove the efficiency of our method, in particular, for linear zero-one programming     

A decomposition algorithm for quadratic programming

A decomposition algorithm using Lemke's method is proposed for the solution of quadratic programming problems having possibly unbounded feasible regions. The feasible region for each master program is a generalized simplex of minimal size. This property is maintained by a dropping procedure which does not affect the finiteness of the convergence. The details of the matrix transformations associated with an efficient implementation of the algorithm are given. Encouraging preliminary computational experience is presented.     

A Branch-and-Bound Approach for Solving a Class of Generalized Semi-infinite Programming Problems

A nonconvex generalized semi-infinite programming problem is considered, involving parametric max-functions in both the objective and the constraints. For a fixed vector of parameters, the values of these parametric max-functions are given as optimal values of convex quadratic programming problems. Assuming that for each parameter the parametric quadratic problems satisfy the strong duality relation, conditions are described ensuring the uniform boundedness of the optimal sets of the dual problems w.r.t. the parameter. Finally a branch-and-bound approach is suggested transforming the problem of finding an approximate global minimum of the original nonconvex optimization problem into the solution of a finite number of convex problems.