Authors: Burer, Monteiro
Available: no; Key paper: 
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.