\documentstyle[ltexconf]{report} 
\begin{document}
 
\title{The Gauss-Newton Direction for Interior-Point Methods in Linear and
Semidefinite Programming}
 
\abstract{
Primal-dual interior-point methods have proven to be very successful for
both linear programming and, more recently,
for semidefinite programming (SDP) problems. 
Many of the techniques that have
been so successful for linear programming (LP)  have been extended to SDP.
In fact, interior point methods appear to be 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 more linear; 
3) we now find
a search direction by applying the Gauss-Newton method to the least
squares problem for these optimality conditions.
~\\
Though this paradigm does not provide a new search direction for linear
programming, it does provide a new viewpoint and
new convergence proofs. 
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, 
i.e. $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. In addition, problems with numerical instability can
arise near the optimal solution.
~\\
There have been various approaches which attempt to symmetrize
the complementarity condition so that the linearization of the optimality
conditions are ``square'', i.e. map between the same spaces. 
However, the paradigm suggests that no symmetrization is necessary.
We concentrate on solving the ``nonsquare,'' or overdetermined, system
in the best way possible. In particular, we use
Gauss-Newton type methods. This leads to numerically stable and efficient
search directions. 
}


\author{\underbar{Henry Wolkowicz}\\
University of Waterloo, Waterloo, Ont. Canada\\
\\
}

\end{document}

% end of example file.

%Henry Wolkowicz                |Fax:   (519) 725-5441
%University of Waterloo         |Tel:   (519) 888-4567, 1+ext. 5589
%Dept of Comb and Opt           |email:  henry@orion.math.uwaterloo.ca
%Waterloo, Ont. CANADA N2L 3G1  |URL: http://orion.math.uwaterloo.ca/~hwolkowi


