Subject: Review of "Solving Large-Scale Semidefinite Programs in Parallel"


The author describes an implementation of the spectral bundle method
for semidefinite programming in parallel on a distributed memory
"Beowulf" cluster.  The main focus of the paper is on issues in the
implementation of the method and on computational results.  In
comparison with parallel implementations of primal-dual interior point
methods, this approach may be more computationally efficient, but is
significantly less accurate.

The biggest weakness in this paper is in the discussion of accuracy
issues.  Just how inaccurate are the solutions produced by this
method, and are solutions that are this inaccurate actually useful?

In measuring the accuracy of the solutions, the author has not made
use of the DIMACS error measures, which separately measure primal and
dual feasibility, duality gap, and complementarity of the solution.
As is, the author compares only the optimal objective function value
returned by his code with the optimal value returned by a more
accurate code (SDPARA).  His code typically produces solutions with an
objective function value within 0.1% of the objective value of the
optimal solution found by SDPARA.  The method seems to be incapable of
consistently producing solutions with more accurate optimal objective
values.  Furthermore, the author does not measure the primal and dual
feasibility or complementarity of the solutions.

The author makes the point that the solutions to computational
chemistry problems produced by their code are not sufficiently
accurate for use in computational chemistry where answers with 6 to 7
digits of accuracy are necessary.  What about the solutions to
relaxations of combinatorial optimization problems?  It seems to this
reviewer that knowing the theta number of graph accurate to even 0.1%
might well not be adequate to prove the optimality of a solution to a
graph coloring or independent set problem.

The collection of test problems used in this paper is rather odd.
With the exception of two very large randomly generated Lovasz theta
problems, all of the SDP's are relatively small and can be solved by
primal-dual interior point codes on a typical desk top PC.  Why didn't
the test set include larger problems?  Also, why didn't the test set
include problems from a larger set of applications?  There are many
suitable problems in the SDPLIB and DIMACS Challenge suites of test
problems.

In reporting on the scalability of the solutions to their test
problems, the author gives parallel speedups but does not compute the
parallel efficiencies.  The parallel efficiencies can be computed
relatively easily from data in table 7.  The efficiencies vary
dramatically from one problem to the next, and are sometimes quite
poor.  For example, problem BeO takes nine and a half hours with one
processor and three hours with 64 processors, for a parallel
efficiency of only 5%.  Another interesting example is the LiF
problem, where the solution with 32 processors takes only 21 minutes,
while the solution with 64 processors takes over 39 minutes.  The
author should explain these anomalies in performance.

The author claims that his algorithm is faster than other methods, but
the computational experiments do not include a direct comparison of
the spectral bundle method with other methods.  It isn't clear whether
the spectral bundle method really is faster than other methods on the
test problems.  The computational testing should obviously be expanded
to include such a comparison.

Another major issue with this paper is its appropriateness for
Mathematical Programming.  The paper includes little in the way of new
theoretical developments, and as such might be more appropriate for a
journal that specializes in computational issues in optimization.