Limiting behavior of the central path in semidefinite optimization

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.

Citation

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

Article

Download

View Limiting behavior of the central path in semidefinite optimization