##
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