2023/07/14 by Feng-Yi Liao, Liao, Feng-Yi, Lijun Ding +3
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Electrical engineering #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2307.07651
openalex publication_date 2023/07/14 · openalex created_date 2023/07/19 · openalex updated_date 2026/07/28
The spectral bundle method developed by Helmberg and Rendl is well-established for solving large-scale semidefinite programs (SDPs) in the dual form, especially when the SDPs admit low-rank primal solutions. Under mild regularity conditions, a recent result by Ding and Grimmer has established fast linear convergence rates when the bundle method captures the rank of primal solutions. In this paper, we present an overview and comparison of spectral bundle methods for solving both primal and dual SDPs. In particular, we introduce a new family of spectral bundle methods for solving SDPs in the primal form. The algorithm developments are parallel to those by Helmberg and Rendl, mirroring the elegant duality between primal and dual SDPs. The new family of spectral bundle methods also achieves linear convergence rates for primal feasibility, dual feasibility, and duality gap when the algorithm captures the rank of the dual solutions. Therefore, the original spectral bundle method by Helmberg and Rendl is well-suited for SDPs with low-rank primal solutions, while on the other hand, our new spectral bundle method works well for SDPs with low-rank dual solutions. These theoretical findings are supported by a range of large-scale numerical experiments. Finally, we demonstrate that our new spectral bundle method achieves state-of-the-art efficiency and scalability for solving polynomial optimization compared to a set of baseline solvers \textsfSDPT3, \textsfMOSEK, \textsfCDCS, and \textsfSDPNAL+.