Extending Mehrotra and Gondzio Higher Order Methods to Mixed Semidefinite-Quadratic-Linear Programming

Jean-Pierre Haeberly, Madhu Nayakkankuppam and Michael Overton

We discuss extensions of Mehrotra's higher order corrections scheme and Gondzio's multiple centrality corrections scheme tomixed semidefinite-quadratic-linear programming (SQLP). These extensions have been included in a solver forSQLP written in C and based on LAPACK. The code implements a primal--dual path--following algorithm for solving SQLP problems based on the XZ+ZX search direction and Mehrotra's predictor--corrector method. We present benchmarks showing that the use of the higher orderschemes yields substantial reductions in both the number of iterations and the running time of the algorithm, and also improves its robustness.

To appear in Optimization Methods and Software.

Contact: madhu@cs.nyu.edu