Adaptive Constraint Reduction for Convex Quadratic Programming

Jin Jung(jjungcs.umd.edu)
Dianne O'Leary(olearycs.umd.edu)
Andre Tits(andreumd.edu)

Abstract: We propose an adaptive constraint-reduction primal-dual interior-point algorithm for convex quadratic programming with many more inequality constraints than variables. We reduce the computational effort by assembling, instead of the exact normal-equation matrix, an approximate matrix from a well chosen index set which includes indices of constraints that seem to be most critical. Starting with a large portion of the constraints, our proposed scheme excludes more unnecessary constraints at later iterations. We provide proofs for the global convergence and the quadratic local convergence rate of an affine-scaling variant. A similar constraint-reduction approach can be applied to algorithms of Mehrotra's predictor-corrector type.

Keywords: Convex Quadratic Programming, Constraint Reduction, Column Generation, Primal-Dual Interior-Point Method

Category 1: Nonlinear Optimization (Quadratic Programming )

Citation: University of Maryland, January 2008

Download: [PDF]

Entry Submitted: 01/22/2008
Entry Accepted: 01/22/2008
Entry Last Modified: 01/22/2008

Modify/Update this entry