**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 by employing an implicit factorization that is valid for at least one optimal solution (but not necessarily for all feasible solutions). Using a theorem of Pataki, is chosen to be an matrix, where is the smallest integer satisfying and is the number of primal constraints (aside from the constraint ). A stationary point 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 .

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 . 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 , 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 (an advantage over BMZ) and
moreover works with a small number of columns (an advantage
over BUNDLE). As a result, the iterations of BMPR are extremely
fast.