BMPR

Authors: Burer, Monteiro
Version: 6/2000;
Available: no; Key paper: [4]
Features: Augmented Lagrangian algorithm applied to an NLP formulation of an SDP arising by replacing the primal variable by a low-rank factorization.
Language, Input format: C; graph
Error computations: none
Solves: maxcut, bisection, theta

The code BMPR is an infeasible, nonlinear programming method for solving any standard form primal SDP. So far, BMPR has been tested on the maximum cut SDP relaxation, the bisection SDP relaxation , and the Lovász theta SDP.

The main idea of BMPR is to eliminate the primal positive semidefiniteness constraint $X \succeq 0$ by employing an implicit factorization $X = RR^T$ that is valid for at least one optimal solution (but not necessarily for all feasible solutions). Using a theorem of Pataki, $R$ is chosen to be an $n \times r$ matrix, where $r$ is the smallest integer satisfying $r(r+1)/2 \ge m$ and $m$ is the number of primal constraints (aside from the constraint $X \succeq 0$). A stationary point $\bar R$ of the new nonlinear problem is then found using a first-order augmented Lagrangian method, and in practice, such a stationary point reliably gives an optimal SDP solution $\bar X = \bar R \bar R^T$.

The stopping criterion for BMPR is problem dependent. For maxcut, BMPR can be easily altered to a primal feasible method that is terminated once the norm of the gradient is less than $10^{-5}$. For bisection and theta, however, BMPR is an infeasible method that is terminated once the norm of the primal infeasibility has been reduced to a value of $10^{-6}$, which, in accordance with the augmented Lagrangian algorithm, indicates an approximate stationary point.

• The main strength of BMPR is that it is a first-order algorithm and hence can attack large-scale SDPs; this property is also shared by BUNDLE and BMZ.

• The infeasible nature of BMPR is a strong disadvantage.

• BMPR does not have a formal convergence proof, while both BMZ and BUNDLE do.

• BMPR performs better on all problem classes that it shares with BMZ and BUNDLE. For theta, the Hamming problems are not representative of the generic performance of BUNDLE; see the above technical report.

• BMPR works with density of the dual matrix $S$ (an advantage over BMZ) and moreover works with a small number of columns $r$ (an advantage over BUNDLE). As a result, the iterations of BMPR are extremely fast.