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.
Contact: [email protected]