  We develop a novel variant of the classical Frank-Wolfe algorithm, which we
call spectral Frank-Wolfe, for convex optimization over a spectrahedron. The
spectral Frank-Wolfe algorithm has a novel ingredient: it computes a few
eigenvectors of the gradient and solves a small-scale SDP in each iteration.
Such procedure overcomes slow convergence of the classical Frank-Wolfe
algorithm due to ignoring eigenvalue coalescence. We demonstrate that strict
complementarity of the optimization problem is key to proving linear
convergence of various algorithms, such as the spectral Frank-Wolfe algorithm
as well as the projected gradient method and its accelerated version.
