Optimization Online


Methods for Convex and General Quadratic Programming

Philip E. Gill (pgill***at***ucsd.edu)
Elizabeth Wong (elwong***at***ucsd.edu)

Abstract: Computational methods are considered for finding a point that satisfies the second-order necessary conditions for a general (possibly nonconvex) quadratic program (QP). The first part of the paper considers the formulation and analysis of an active-set method for a generic QP with both equality and inequality constraints. The method uses a search direction that is the solution of an equality-constrained subproblem involving a “working set” of linearly independent constraints. The method is a reformulation of a method for general QP first proposed by Fletcher, and modified subsequently by Gould. The reformulation facilitates a simpler analysis and has the benefit that the algorithm reduces to a variant of the simplex method when the QP is a linear program. The search direction is computed from a KKT system formed from the QP Hessian and the gradients of the working-set constraints. It is shown that, under certain circumstances, the solution of this KKT system may be updated using a simple recurrence relation, thereby giving a significant reduction in the number of KKT systems that need to be solved. The second part of the paper focuses on the solution of QP problems with constraints in so-called standard form. We describe how the constituent KKT systems are solved, and discuss how an initial basis is defined. Numerical results are presented for all QPs in the CUTEst test collection.

Keywords: Large-scale quadratic programming, active-set methods, convex quadratic programming, dual quadratic program, nonconvex quadratic programming, KKT systems

Category 1: Nonlinear Optimization (Quadratic Programming )

Citation: UCSD Center for Computational Mathematics Technical Report CCoM-14-3

Download: [PDF]

Entry Submitted: 09/30/2010
Entry Accepted: 09/30/2010
Entry Last Modified: 07/17/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society