BMZ

Authors: Burer, Monteiro, Zhang
Version: 5/2000;
Available: no;
Key paper: [5]
Features: special transformation of the dual SDP to an NLP
Language, Input format: C; graph
Error computations: no
Solves: maxcut, FAP, bisection, theta

The code BMZ is a dual feasible descent method to solve SDP problems for which all primal feasible solutions $X$ 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 $I\!\!R^n_{++} \times I\!\!R^N$, where $n$ is the size of the primal matrix variable $X$ and $N$ a suitable integer, see [5]. 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 $S$, 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 $\mu$ has passed below a specified threshold. For each of the three examples above, the thresholds are as follows: maxcut, $10^{-3}$; theta, $10^{-3}$; FAP, $10^{-4}$.

• The main strength of BMZ is that it is a first-order algorithm and hence can attack large-scale SDPs; this property is also shared by BUNDLE and BMPR.
• That BMZ is a feasible method is a distinct advantage over BMPR, though BUNDLE is also a dual feasible method.
• In our opinion, an advantage of BMZ over BUNDLE is that BMZ seems to handle a large number of constraints more effectively. The current DIMACS results don't exactly show this, but the more recent results in [6] give a different viewpoint.
• A distinct disadvantage of BMZ to both BUNDLE and BMPR is that BMZ works with the Cholesky factor $L$ of $S$, that is, BMZ must deal with the fill-in of the Cholesky factorization, whereas both BMPR and BUNDLE work only with the density of $S$ itself. There are several instances in which $S$ fills in dramatically, causing a slow-down for BMZ.