A boundary point method to solve semidefinite programs. (English) Zbl 1275.90055

Povh, Janez; Rendl, Franz; Wiegele, Angelika

Computing 78, No. 3, 277-286 (2006).

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.

MSC:

90C22	Semidefinite programming
90C06	Large-scale problems in mathematical programming

Keywords:

Semidefinite programming; augmented Lagrangian method; theta function

Software:

Benchmarks for Optimization Software; PENSDP; SDPLR

References:

[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.