Error bounds and limiting behavior of weighted paths associated with the SDP map $X^{1/2}SX^{1/2}$

Zhaosong Lu (zhaosongisye.gatech.edu)
Renato D. C. Monteiro (monteiroisye.gatech.edu)

Abstract: This paper studies the limiting behavior of weighted infeasible central paths for semidefinite programming obtained from centrality equations of the form $X^{1/2}S X^{1/2} = \nu W$, where $W$ is a fixed positive definite matrix and $\nu>0$ is a parameter, under the assumption that the problem has a strictly complementary primal-dual optimal solution. It is shown that a weighted central path as a function of $\sqrt{\nu}$ can be extended analytically beyond $0$ and hence that the path converges as $\nu \downarrow 0$. Characterization of the limit points of the path and its normalized first-order derivatives are also provided. As a consequence, it is shown that a weighted central path can have two types of behavior, namely: either it converges as ${\Theta}(\nu)$ or as ${\Theta}(\sqrt{\nu})$ depending on whether the matrix $W$ on a certain scaled space is block diagonal or not, respectively. We also derive an error bound on the distance between a point lying in a certain neighborhood of the central path and the set of primal-dual optimal solutions. Finally, we propose a new sufficient condition for superlinear convergence of primal-dual interior point SDP algorithms and show that it is is weaker than other conditions that have been proposed earlier.

Keywords: Limiting behavior, weighted central path, error bound,superlinear convergence, semidefinite programming.

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

Citation: Manuscript, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, June 2003.

Download: [Postscript][PDF]

Entry Submitted: 06/24/2003
Entry Accepted: 06/24/2003
Entry Last Modified: 12/08/2004

Modify/Update this entry