Sdpha: a Matlab implementation of homogeneous interior-point algorithms for semidefinite programming
- 1 January 1999
- journal article
- software
- Published by Informa UK Limited in Optimization Methods and Software
- Vol. 11 (1-4), 583-596
- https://doi.org/10.1080/10556789908805763
Abstract
Mehrotra type primal-dual predictor-corrector interior-point algorithms for semidefinite programming are implemented, using the homogeneous formulation proposed and analyzed by Potra and Sheng. Several search directions, including the AHO, HKM, NT, Toh, and Gu directions, are used. A rank-2 update technique is employed in our MATLAB code so that the computation of homogeneous directions is only slightly more expensive than in the non-homogeneous case. However, the homogeneous algorithms generally take fewer iterations to compute an approximate solution within a desired accuracy. Numerical results show that the homogeneous algorithms outperform their non-homogeneous counterparts, with improvement of more than 20% in many cases, in terms of total CPU time.Keywords
This publication has 16 references indexed in Scilit:
- A Predictor-Corrector Interior-Point Algorithm for the Semidefinite Linear Complementarity Problem Using the Alizadeh--Haeberly--Overton Search DirectionSIAM Journal on Optimization, 1999
- Polynomial Convergence of Primal-Dual Algorithms for Semidefinite Programming Based on the Monteiro and Zhang Family of DirectionsSIAM Journal on Optimization, 1998
- Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical ResultsSIAM Journal on Optimization, 1998
- A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programmingMathematical Programming, 1998
- Local convergence of predictor—corrector infeasible-interior-point algorithms for SDPs and SDLCPsMathematical Programming, 1998
- Primal--Dual Path-Following Algorithms for Semidefinite ProgrammingSIAM Journal on Optimization, 1997
- Interior-Point Methods for the Monotone Semidefinite Linear Complementarity Problem in Symmetric MatricesSIAM Journal on Optimization, 1997
- An Interior-Point Method for Semidefinite ProgrammingSIAM Journal on Optimization, 1996
- On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear ProgrammingMathematics of Operations Research, 1993
- On the Implementation of a Primal-Dual Interior Point MethodSIAM Journal on Optimization, 1992