Solving Semidefinite Quadratic Problems Within Nonsmooth Optimization Algorithms

Bundle methods for Nondifferentiable Optimization are widely recognised 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. We present an active-set method for the solution of such problems, that 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, we show how the algorithm can be adapted to the several needs that arises in practice within Bundle algorithms; we describe 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 nondifferentiable function. Finally, we describe the important implementation issues, and we report 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.