Description: |
An implementation of the QSPLINE method for solving convex quadratic programming problems with simple bound constraints
A convex quadratic programming problem with simple bound constraints can be reformulated as an unconstrained minimization problem with a convex quadratic spline (i.e., a differentiable convex piecewise quadratic function) as the objective function. This leads to a new paradigm for solving the original quadratic programming problem, in which various unconstrained minimization algorithms can be used to find a stationary point of the convex quadratic spline. In this paper, we give an implementation of a regularized Newton method (called the QSPLINE method) for finding a stationary point of the convex quadratic spline. The QSPLINE method can also be considered as an implicit active-set method with two novel features: (i) a mixed primal-dual approach for identifying active indices and (ii) a line search strategy for a dynamic balance between the need for minimizing the original objective function and that of forcing the iterates to stay in the feasible region. The implemented version of the QSPLINE method uses a matrix updating technique for computing Newton directions and a correction strategy for robust reduction of the convex quadratic spline when line search in a Newton direction fails. We have tested the code on a variation of the test problems used by J. J. Móre and G. Toraldo [Numer. Math. 55, No. 4, 377–400 (1989; Zbl 0675.65061)]. For our generated test problem, the Hessian of the objective function could be an n×n positive semidefinite matrix with rank 2n 3, and one-third of the Lagrange multipliers corresponding to active constraints at a generated optimal solution could be zero. That is, our test problems are degenerate and have highly singular Hessians. The code finds very accurate numerical solutions for all 2800 randomly generated test problems (with n=300 and 500), even though all these problems are degenerate and about 60 |