论文标题
光谱Frank-Wolfe算法：严格的互补性和线性收敛性
Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergence
论文作者
论文摘要
我们开发了古典Frank-Wolfe算法的新颖变体，我们称其为Spectral Frank-Wolfe，以优化频谱。光谱Frank-Wolfe算法具有一种新颖的成分：它计算梯度的一些特征向量，并在每次迭代中求解一个小规模的SDP。由于忽略了特征值合并，因此这种程序克服了经典的弗兰克 - 沃尔夫算法的趋势。我们证明，优化问题的严格互补性是证明各种算法的线性收敛的关键，例如光谱Frank-Wolfe算法以及预计的梯度方法及其加速版本。
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.
