The code BMZ is a dual feasible descent method to solve SDP problems for which all primal feasible solutions have the same diagonal. The maximum cut SDP relaxation, the Lovász theta SDP, and the frequency assignment SDP relaxation are examples of problems that can be solved by BMZ.
The main idea of BMZ is to convert the dual SDP into a nonlinear optimization problem over feasible sets of the form , where is the size of the primal matrix variable and a suitable integer, see . The resulting objective function is nonconvex but can be computed in time and space proportional to the time and space required to perform the Cholesky factorization of a dual feasible slack matrix , which is typically efficient for large, sparse SDPs. The function's gradient can also be computed efficiently. By employing ideas from interior-point methods, it is possible to optimize the nonconvex function over its open feasible set by following a ``central path'' towards optimality. Computationally, a first-order nonlinear optimization algorithm is used to fully exploit problem structure while still achieving a reasonable amount of accuracy.
The stopping criterion for BMZ is to terminate once the barrier parameter has passed below a specified threshold. For each of the three examples above, the thresholds are as follows: maxcut, ; theta, ; FAP, .