Back to Search
Start Over
ERROR BOUNDS AND LIMITING BEHAVIOR OF WEIGHTED PATHS ASSOCIATED WITH THE SDP MAP X1/2SX1/2.
- Source :
-
SIAM Journal on Optimization . 2004, Vol. 15 Issue 2, p348-374. 27p. - Publication Year :
- 2004
-
Abstract
- This paper studies the limiting behavior of weighted infeasible central paths for semidefinite programming (SDP) obtained from centrality equations of the form X½ SX½ = vW, where W is a fixed positive definite matrix and v>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 √v can be extended analytically beyond 0 and hence that the path converges as v↓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: it converges either as &Tetha;(v) or asT &Tetha;(√v) 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, in light of the results of this paper, we give a characterization of a sufficient condition proposed by Potra and Sheng which guarantees the superlinear convergence of a class of primal-dual interior-point SDP algorithms. [ABSTRACT FROM AUTHOR]
- Subjects :
- *EQUATIONS
*ALGORITHMS
*ALGEBRA
*FOUNDATIONS of arithmetic
*MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 10526234
- Volume :
- 15
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 16197515
- Full Text :
- https://doi.org/10.1137/S1052623403430828