Text
Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates
The spectral bundle method proposed by Helmberg and Rendl [SIAM J. Optim., 10 (2000), pp. 673–696] is well established for solving large-scale semidefinite programs (SDPs) thanks to its low per iteration computational complexity and strong practical performance. In this paper, we revisit this classic method showing that it achieves sublinear convergence rates in terms of both primal and dual SDPs under merely strong duality, complementing previous guarantees on primal-dual convergence. Moreover, we show that the method speeds up to linear convergence if (1) structurally the SDP admits strict complementarity and (2) algorithmically the bundle method captures the rank of the optimal solutions. Such complementary and low-rank structure is prevalent in many modern and classical applications. The linear convergence result is established via an eigenvalue approximation lemma which might be of independent interest. Numerically, we confirm our theoretical findings that the spectral bundle method, for modern and classical applications, speeds up under these conditions. Finally, we show that the spectral bundle method combined with a recent matrix sketching technique is able to solve an SDP with billions of decision variables in a matter of minutes.
Barcode | Tipe Koleksi | Nomor Panggil | Lokasi | Status | |
---|---|---|---|---|---|
art146439 | null | Artikel | Gdg9-Lt3 | Tersedia namun tidak untuk dipinjamkan - No Loan |
Tidak tersedia versi lain