The Gauss-Newton Direction in Semidefinite Programming

Serge Kruk, Masakazu Muramatsu, Franz Rendl, Robert J. Vanderbei, Henry Wolkowicz

Primal-dual interior-point methods have proven to be very successful for both linear programming (LP) and, more recently, for semidefinite programming (SDP) problems. Many of the techniques that have been so successful for LP have been extended to SDP. In fact, interior point methods are currently the only successful techniques for SDP. We present a new paradigm for deriving these methods: 1) using the optimality conditions from the dual log-barrier problem, we obtain primal feasibility, dual feasibility, and perturbed complementary slackness equations; 2) the perturbed complementary slackness condition is quite nonlinear, so we modify this condition to obtain a bilinear condition, i.e. a condition that is less nonlinear; 3) we now find a search direction by applying the Gauss-Newton method to the least squares problem for these optimality conditions; equivalently we find the least squares solution of the linearized perturbed optimality conditions. In the case of LP, the Gauss-Newton direction for the least squares problem is equivalent to the Newton direction applied to solving the modified (square) nonlinear system of optimality conditions. Though this paradigm does not directly provide a new search direction for linear programming, it does provide a new approach for convergence proofs as well as motivation for step lengths larger than one. However, there is one major difference between LP and SDP that raises several interesting questions. That difference is the form of the perturbed complementarity condition used in the optimality conditions. In LP this condition is modified to be $ZX - \mu I = 0.$ The primal matrix $X$ and the dual slack matrix $Z$ are diagonal in LP but may only be symmetric in SDP; this results in $ZX$ not being symmetric in general, i.e. the optimality conditions in the SDP case end up as an overdetermined system of nonlinear equations. There have been various approaches which modify the complementarity condition so that the linearization of the optimality conditions are ``square'', i.e. map between the same spaces. These approaches can have several drawbacks, e.g. numerical instability near the optimum and lack of positive definiteness after symmetrization. Our least squares approach requires no symmetrization and does not suffer from these drawbacks. We concentrate on solving the overdetermined, system in the best way possible. In particular, we use Gauss-Newton type methods. This leads to numerically stable as well as excellent search directions which lead to the central path. Though the numerical efficient calculation of the Gauss-Newton direction is still an open question, we present a preliminary ``top down'' elimination approach that is competitive timewise and empirical evidence suggests that it is often more robust than other directions currently in use.