Scholarlink

<p>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 <i>low-rank primal solutions</i>. Under mild regularity conditions, a recent result by Ding and Grimmer has established fast linear convergence rates when the bundle method captures <i>the rank of primal solutions</i>. In this paper, we present an overview and comparison of spectral bundle methods for solving both <i>primal</i> and <i>dual</i> SDPs. In particular, we introduce a new family of spectral bundle methods for solving SDPs in the <i>primal</i> 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 <i>the rank of the dual solutions</i>. Therefore, the original spectral bundle method by Helmberg and Rendl is well-suited for SDPs with <i>low-rank primal solutions</i>. On the other hand, our new spectral bundle method works well for SDPs with <i>low-rank dual solutions</i>. We support these theoretical findings with 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 <Emphasis FontCategory="SansSerif">SDPT3</Emphasis>, <Emphasis FontCategory="SansSerif">MOSEK</Emphasis>, <Emphasis FontCategory="SansSerif">CDCS</Emphasis>, and <Emphasis FontCategory="SansSerif">SDPNAL+</Emphasis>.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

An overview and comparison of spectral bundle methods for primal and dual semidefinite programs

  • 期刊论文

  • 发表日期：

    2025年10月1日

查看全文
  • Feng-Yi Liao,
  • Lijun Ding,
  • Yang Zheng

摘要

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. On the other hand, our new spectral bundle method works well for SDPs with low-rank dual solutions. We support these theoretical findings with 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 SDPT3, MOSEK, CDCS, and SDPNAL+.