Numerical methods for large-scale non-convex quadratic programming

N. I. M. Gould (n.gouldrl.ac.uk)
Ph. L. Toint (philippe.tointfundp.ac.be)

Abstract: We consider numerical methods for finding (weak) second-order critical points for large-scale non-convex quadratic programming problems. We describe two new methods. The first is of the active-set variety. Although convergent from any starting point, it is intended primarily for the case where a good estimate of the optimal active set can be predicted. The second is an interior-point trust-region type, and has proved capable of solving problems involving up to half a million unknowns and constraints. The solution of a key equality constrained subproblem, common to both methods, is described. The results of comparative tests on a large set of convex and non-convex quadratic programming examples are given.

Keywords: non-convex quadratic programming, interior-point methods, active-set methods

Category 1: Nonlinear Optimization (Quadratic Programming )

Citation: Technical Report RAL-TR-2001-017 (2001), Rutherford Appleton Laboratory, Chilton, England.

Download: [Compressed Postscript]

Entry Submitted: 02/23/2001
Entry Accepted: 02/23/2001
Entry Last Modified: 02/23/2001

Modify/Update this entry