A note on efficient computation of the gradient in semidefinite programming

S. Vavasis

In the Goemans-Williamson semidefinite relaxation of MAX-CUT, the gradient of the dual barrier objective function has a term of the form $\diag(Z^{-1})$, where $Z$ is the slack matrix. The purpose of this note is to show that this term can be computed in time and space proportional to the time and space for computing a sparse Cholesky factor of $Z$. The algorithm for computing the term is motivated by automatic differentiation in backward mode.

September 14, 1999

Contact: vavasis@cs.cornell.edu