On Extending Primal-dual Interior-Point Algorithms
from Linear Programming to Semidefinite Programming
Yin Zhang
This work concerns primal-dual interior-point methods for
semidefinite programming (SDP) that use a linearized complementarity
equation originally proposed by Kojima, Shindoh and Hara and recently
rediscovered by Monteiro in a more explicit form. In analyzing these
methods, a number of basic equalities and inequalities were developed
by the authors of the two papers through different means and in
different forms.
In this paper, we give a very short derivation of the key equalities
and inequalities along the exact line used in linear programming
(LP), producing basic relationships that have highly compact forms
almost identical to their counterparts in LP. We also introduce a
new definition of the central path and a variable-metric measure of
centrality. These results provide convenient tools for extending
existing polynomiality results for many, if not most, algorithms from
LP to SDP with little complication. We present examples of such
extensions, including the long-step infeasible-interior-point
algorithm of Zhang extended to SDP for the first time.
Technical Report TR95-20, Department of Mathematics and
Statistics, University of Maryland Baltimore County,
November, 1995.
![[POSTSCRIPT]](../../InteriorPoint/gif/PS.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)