Limiting behavior of the central path in semidefinite optimization

M. Halicka (halickafmph.uniba.sk)
E. De Klerk (E.deKlerkits.tudelft.nl)
C. Roos (C.Roosits.tudelft.nl)

Abstract: It was recently shown that, unlike in linear optimization, the central path in semidefinite optimization (SDO) does not converge to the analytic center of the optimal set in general. In this paper we analyze the limiting behavior of the central path to explain this unexpected phenomenon. This is done by deriving a new necessary and sufficient condition for strict complementarity. We subsequently show that, in the absence of strict complementarity, the central path converges to the analytic center of a certain subset of the optimal set. We further derive sufficient conditions under which this subset coincides with the optimal set, i.e. sufficient conditions for the convergence of the central path to the analytic center of the optimal set. Finally, we show that convex quadratically constraint quadratic optimization problems, when rewritten as an SDO problems, satisfy these sufficient conditions. Several examples are given to illustrate the possible convergence behavior.

Keywords: Semidefinite optimization, linear optimization, interior point method,

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Preprint, Faculty of Information Technology and Systems, Delft University of Technology, The Netherlands

Download: [Postscript][PDF]

Entry Submitted: 06/12/2002
Entry Accepted: 06/12/2002
Entry Last Modified: 06/12/2002

Modify/Update this entry