A decomposition method for quadratic programming

Abstract

We discuss the algorithms used in the Optimization Subroutine Library for the solution of convex quadratic programming problems. The basic simplex algorithm for convex quadratic programming is described. We then show how the simplex method for linear programming can be used in a decomposition crash procedure to obtain a good initial basic solution for the quadratic programming algorithm. We show how this solution may be used as a starting solution for the simplex-based algorithm. Besides its ability to obtain good starting solutions, this procedure has several additional properties. It can be used directly to find an optimal solution to a quadratic program instead of simply finding a good initial solution; it provides both upper and lower bounds on the objective function value as the algorithm proceeds; it reduces the complexity of intermediate calculations; it avoids certain numerical difficulties that arise in quadratic, but not linear programming