Primal-Dual Interior-Point Methods for Semidefinite Programming in Finite Precision
The author studies the numerical stability of some primal-dual interior point methods for solving semidefinite programming problems. Two families of methods based on symmetric search directions for the approximation of the central-path are discussed. On the one hand the method introduced by Alizadeh, Haerberly and Overton (AHO direction) [SIAM J. Optim. 8, 746-768 (1998; Zbl 0911.65047)] and on the other hand the family of search directions pointed out by Todd, Toh and Tuetuencue (TTT directions) [SIAM J. Optim. 8, 769-796 (1998; Zbl 0913.90217)]. For both methods the authors show that numerical stability could appear if an effective condition number associated with certain coefficient matrices depending on the search direction is small, but numerical instabilities are expected otherwise. For this analysis the Schur complement approach derived from block Gaussian elimination for the calculation of the search direction is used. For the TTT method the Schur complement equation can be also described as the normal equation of a linear least squares problem. However, it is showed, that the least square approach in general does not perform better than the Schur complement approach. Finally some numerical experiments supporting the analysis are presented. In particular, the numerical results indicate that the AHO method appears to be more accurate than the TTT methods. This fact can be explained from the analysis presented in the paper, since the coefficient matrix used for the TTT methods is in general much worse conditioned than the one for the AHO method.
- The Gauss-Newton direction in semidefinite programming
- A study of search directions in primal-dual interior-point methods for semidefinite programming
- A robust algorithm for semidefinite programming
- Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
- An \(O(\sqrt nL)\) wide neighborhood interior-point algorithm for semidefinite optimization
- A feasible primal-dual interior point method for linear semidefinite programming
- Sdpha: a Matlab implementation of homogeneous interior-point algorithms for semidefinite programming
- On Extending Some Primal--Dual Interior-Point Algorithms From Linear Programming to Semidefinite Programming
- scientific article; zbMATH DE number 741122
- A wide neighbourhood interior-point method with iteration-complexity bound for semidefinite programming
- Avoiding numerical cancellation in the interior point method for solving semidefinite programs
- An interior point-proximal method of multipliers for linear positive semi-definite programming
- Some new search directions for primal-dual interior point methods in semidefinite programming
- On the Turing model complexity of interior point methods for semidefinite programming
- scientific article; zbMATH DE number 5734472 (Why is no real title available?)
- Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
- scientific article; zbMATH DE number 741122 (Why is no real title available?)
- A study of search directions in primal-dual interior-point methods for semidefinite programming
- The RPR2 rounding technique for semidefinite programs
- The Q method for symmetric cone programming
This page was built for publication: Primal-Dual Interior-Point Methods for Semidefinite Programming in Finite Precision
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4943940)
