Solving semidefinite quadratic problems within nonsmooth optimization algorithms

Bundle methods for Nondifferentiable Optimization are widely recognized as one of the best choices for the solution of Lagrangean Duals; one of their major drawbacks is that they require the solution of a Semidefinite Quadratic Programming subproblem at every iteration. The paper presents an active-set method for the solution of such problems, which enhances upon the ones in the literature by distinguishing among bases with different properties and exploiting their structure in order to reduce the computational cost of the basic step. Furthermore, it shows how the algorithm can be adapted to the several needs that arises in practice within Bundle algorithms; the paper describes how it is possible to allow constraints on the primal direction, how special (box) constraints can be more efficiently dealt with and how to accommodate changes in the number of variables of the non-differentiable function. Finally, it describes the important implementation issues, and reports some computational experience to show that the algorithm is competitive with other QP codes when used within a Bundle code for the solution of Lagrangean Duals of large-scale (Integer) Linear Programs.