Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 278C: Optimization and Data Science

Feng-Yi Liao

UCSD

Spectral Bundle Methods For Primal And Dual Semidefinite Programs

Abstract:

 

In this work, we present an overview and comparison of spectral bundle methods for solving both primal and dual semidefinite programs (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 achieves linear convergence rates for primal feasibility, dual feasibility, and duality gap when the algorithm captures the rank of the dual solutions. 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.

Host: Jiawang Nie

November 22, 2023

4:00 PM

APM 7321

****************************