We propose an adaptive constraint reduction primal-dual interior-point algorithm for convex quadratic programming with many more constraints than variables. We reduce the computational effort by assembling the normal equation matrix with a subset of the constraints. Instead of the exact matrix $H + A^T S^{-1}\Lambda A$, we compute a reduced matrix $H + A_Q^T S_{Q^2}^{-1} \Lambda_{Q^2} A_Q$ for a well chosen index set Q 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.
Keywords: Convex Quadratic Programming, Constraint Reduction, Column Generation, Primal-Dual Interior Point Method, Affine Scaling
Paper (DRAFT)
CRCQP.m (MATLAB function script)
Minimum requirement: MATLAB 7.0 or higher.