Limiting behavior of the central path in semidefinite optimization

Publisher Website
Google Scholar
Abstract
It was recently shown by [Halická et al. 2002). On the convergence of the central path in semidefinite optimization. SIAM J. Optimization, 12(4), 1090–1099] 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 article, 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 constrained quadratic optimization problems, when rewritten as SDO problems, satisfy these sufficient conditions. Several examples are given to illustrate the possible convergence behavior.