- 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/2003Entry Accepted: 06/24/2003Entry Last Modified: 12/08/2004Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.