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
HomogeneousMATLABSemidefinite programmingAlgorithmInterior point methodRank (graph theory)Computer sciencePoint (geometry)MathematicsMathematical optimizationCombinatoricsGeometry
Affiliated Institutions
Related Publications
SDPT3 -- A Matlab Software Package for Semidefinite Programming
This software package is a Matlab implementation of infeasible path-following algorithms for solving standard semidefinite programs (SDP). Mehrotra-type predictor-corrector vari...
SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
This software package is a MATLAB implementation of infeasible path-following algorithms for solving standard semidefinite programs (SDP). Mehrotra-type predictor-corrector vari...
On a Wide Region of Centers and Primal-Dual Interior Point Algorithms for Linear Programming
In the adaptive step primal-dual interior point method for linear programming, polynomial algorithms are obtained by computing Newton directions towards targets on the central p...
On the implementation of primal-dual interior-point methods for semidefinite programming problems derived from the KYP lemma
We discuss fast implementations of primal-dual interior-point methods for semidefinite programs derived from the Kalman-Yakubovich-Popov lemma, a class of problems that are wide...
An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
We present an O(√nL)-iteration homogeneous and self-dual linear programming (LP) algorithm. The algorithm possesses the following features: • It solves the linear programming pr...
Publication Info
- Year
- 1999
- Type
- article
- Volume
- 11
- Issue
- 1-4
- Pages
- 583-596
- Citations
- 21
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
21
OpenAlex
Cite This
Nathan W. Brixius,
Florian A. Potra,
Rongqin Sheng
(1999).
Sdpha: a Matlab implementation of homogeneous interior-point algorithms for semidefinite programming.
Optimization methods & software
, 11
(1-4)
, 583-596.
https://doi.org/10.1080/10556789908805763
Identifiers
- DOI
- 10.1080/10556789908805763