A Dual Method for Certain Positive Semidefinite Quadratic Programming Problems

This paper presents a dual active set method for minimizing a sum of piecewise linear functions and a strictly convex quadratic function, subject to linear constraints. It may be used for direction finding in nondifferentiable optimization algorithms and for solving exact penalty formulations of (possibly inconsistent) strictly convex quadratic programming problems. An efficient implementation is described extending the Goldfarb and Idnani algorithm, which includes Powell's refinements. Numerical results indicate excellent accuracy of the implementation.