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