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.