An Interior-Point Method for Semidefinite Programming
- 1 May 1996
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 6 (2) , 342-361
- https://doi.org/10.1137/0806020
Abstract
We propose a new interior point based method to minimize a linear function of a matrix variable subject to linear equality and inequality constraints over the set of positive semidefinite matrices. We show that the approach is very ecient for graph bisection problems, such as max-cut. Other applications include max-min eigenvalue problems and relaxations for the stable set problem.Keywords
This publication has 21 references indexed in Scilit:
- Nonpolyhedral Relaxations of Graph-Bisection ProblemsSIAM Journal on Optimization, 1995
- Second Derivatives for Optimizing Eigenvalues of Symmetric MatricesSIAM Journal on Matrix Analysis and Applications, 1995
- Max-min eigenvalue problems, primal-dual Interior point algorithms, and Trust region subproblemstOptimization Methods and Software, 1995
- Computational experience with a primal-dual interior-point method for smooth convex programmingOptimization Methods and Software, 1994
- On the convergence of an infeasible primal-dual interior-point method for convex programmingOptimization Methods and Software, 1994
- Higher-Order Predictor-Corrector Interior Point Methods with Application to Quadratic ObjectivesSIAM Journal on Optimization, 1993
- The max-cut problem on graphs not contractible to K5Operations Research Letters, 1983
- Some applications of optimization in matrix theoryLinear Algebra and its Applications, 1981
- On the Shannon capacity of a graphIEEE Transactions on Information Theory, 1979
- The minimization of certain nondifferentiable sums of eigenvalues of symmetric matricesPublished by Springer Nature ,1975