next up previous
Next: BUNDLE Up: The Codes Previous: BMPR


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}$.

next up previous
Next: BUNDLE Up: The Codes Previous: BMPR
Hans D. Mittelmann 2002-08-17