Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- 1 February 1995
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 5 (1) , 13-51
- https://doi.org/10.1137/0805002
Abstract
We study the semidefinite programming problem (SDP), i.e the problem of optimization of a linear functionof a symmetric matrix subject to linear equality constraints and the additional condition that the matrixbe positive semidefinite. First we review the classical cone duality as specialized to SDP. Next we presentan interior point algorithm which converges to the optimal solution in polynomial time. The approach is adirect extension of Ye's projective method for linear programming. We...This publication has 44 references indexed in Scilit:
- Expressing combinatorial optimization problems by Linear ProgramsPublished by Elsevier ,2003
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- A monotonic projective algorithm for fractional linear programmingAlgorithmica, 1986
- Facial reduction for a cone-convex programming problemJournal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics, 1980
- Characterization of optimality for the abstract convex program with finite dimensional rangeJournal of the Australian Mathematical Society, 1980
- On the Shannon capacity of a graphIEEE Transactions on Information Theory, 1979
- Generalizations of Farkas’ TheoremSIAM Journal on Mathematical Analysis, 1977
- The minimization of certain nondifferentiable sums of eigenvalues of symmetric matricesPublished by Springer Nature ,1975
- Normal hypergraphs and the perfect graph conjectureDiscrete Mathematics, 1972
- Some convexity theorems for matricesGlasgow Mathematical Journal, 1971