zbMATH — the first resource for mathematics

A boundary point method to solve semidefinite programs. (English) Zbl 1275.90055
Summary: We investigate the augmented Lagrangian penalty function approach to solve semidefinite programs. It turns out that this method generates iterates which lie on the boundary of the cone of semidefinite matrices which are driven to the affine subspace described by the linear equations defining the semidefinite program. We provide some computational experience with this method and show in particular, that it allows to compute the theta number of a graph to reasonably high accuracy for instances which are beyond reach by other methods.

90C22 Semidefinite programming
90C06 Large-scale problems in mathematical programming
Full Text: DOI
[1] Bertsekas, D.: Constrained optimization and Lagrange multiplier methods. Academic Press 1982. · Zbl 0572.90067
[4] Dukanovic, I., Rendl, F.: Semidefinite programming relaxations for graph coloring and maximal clique problems. Math. Progr. (forthcoming). · Zbl 1278.90299
[6] Kocvara, M., Stingl, M.: On the solution of large-scale sdp problems by the modified barrier method using iterative solvers. Technical report 2005.
[9] Malick, J., Povh, J., Rendl, F., Wiegele, A.: Proximal methods for semidefinite programming. Technical report 2006. · Zbl 1187.90219
[11] Povh, J.: Applications of semidefinite and copositive programming in combinatorial optimization. PhD thesis, Universtity of Ljubljana, Slovenia, 2006.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.