⚡ electrical engineering

An Overview and Comparison of Spectral Bundle Methods for Primal and Dual Semidefinite Programs

This paper introduces a new family of spectral bundle methods for solving primal semidefinite programs that mirror the established dual approach, achieving fast linear convergence for problems with low-rank dual solutions and demonstrating state-of-the-art efficiency in polynomial optimization compared to leading solvers.

Original authors: Feng-Yi Liao, Lijun Ding, Yang Zheng

Published 2026-02-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Feng-Yi Liao, Lijun Ding, Yang Zheng

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, incredibly complex puzzle. In the world of mathematics and engineering, this puzzle is called a Semidefinite Program (SDP). These puzzles are used to optimize everything from designing efficient networks to training artificial intelligence. However, as the puzzles get bigger (with thousands or millions of pieces), traditional methods for solving them become too slow or run out of memory, like trying to solve a jigsaw puzzle by looking at every single piece individually.

This paper introduces a smarter way to solve these puzzles, focusing on a specific technique called the Spectral Bundle Method. Here is a simple breakdown of what the authors did and why it matters.

The Two Sides of the Same Coin

In the world of these math puzzles, there are usually two ways to look at the problem: the Primal view and the Dual view. Think of them like looking at a sculpture from the front or the back.

The Old Way: For a long time, mathematicians had a very efficient tool (the Spectral Bundle Method) that worked great if you looked at the puzzle from the Dual side, but only if the solution to the original (Primal) puzzle was "simple" or "low-rank" (meaning it had a lot of empty space or zeros, like a sparse matrix).
The Problem: Sometimes, the puzzle is the other way around. The Dual side is the simple one, and the Primal side is the messy, complex one. The old tool struggled here.

The New Tool: A Mirror Image

The authors of this paper built a new version of this tool. They took the logic of the old tool and flipped it, creating a "mirror image" that works perfectly when you need to solve the Primal version of the puzzle directly.

The Analogy: Imagine you have a specialized screwdriver designed to tighten screws on the left side of a machine. It works perfectly there. But if the screws are on the right side, that screwdriver is useless. The authors didn't just make a better screwdriver; they made a left-handed screwdriver that is just as effective for the right side of the machine.
How it Works: Instead of trying to look at the whole giant puzzle at once, this method looks at the "skeleton" or the most important parts (the eigenvectors) of the solution. It builds a small, manageable model of the big problem, solves that, and then refines it step-by-step.

The "Rank" Secret Sauce

The paper discovered a crucial rule about when this method works best, which they call the Rank Condition.

The Rule: If the solution to your puzzle is "low-rank" (meaning it's simple and doesn't use all its potential complexity), this method zooms in and solves it incredibly fast—like finding the exit in a maze by following a single, clear path.
The Match:
- If the Primal puzzle is simple (low-rank), the old tool is best.
- If the Dual puzzle is simple (low-rank), the new tool (created in this paper) is best.

What They Proved

The authors didn't just build the tool; they proved mathematically that it works:

Speed: They showed that under the right conditions (when the solution is simple), the new method doesn't just get closer to the answer slowly; it speeds up and finds the answer very quickly (linear convergence).
Accuracy: They proved it can get the answer as precise as you need it to be.

Real-World Testing

To make sure their theory wasn't just math on paper, they tested it on real-world problems:

Random Puzzles: They generated random math problems to see how the tools behaved. The results confirmed that using the "wrong" tool for the type of puzzle led to slow progress, while using the "right" tool (matching the low-rank side) was lightning fast.
Max-Cut Problem: This is a classic problem about splitting a group of people into two teams to maximize the number of arguments between them. The authors found that for this specific problem, the old tool was superior because the solution was naturally simple on the Primal side.
Polynomial Optimization: This involves finding the best solution for complex curves (like in chemistry or engineering design). Here, the new tool shined. It solved these problems faster and more efficiently than the top commercial software currently available (like MOSEK, SDPT3, and SDPNAL+).

The Bottom Line

The paper is a "user manual" and a "proof of concept" for a new mathematical tool. It tells us:

We now have a tool to solve the Primal version of these big puzzles directly, not just the Dual version.
The key to speed is knowing which side of the puzzle is "simple" (low-rank).
When the Dual side is the simple one, this new tool is the state-of-the-art champion, beating out existing high-end software in speed and efficiency.

The authors have also made their code open-source, allowing others to use this new "left-handed screwdriver" to solve their own complex optimization problems.

Technical Summary: Spectral Bundle Methods for Primal and Dual Semidefinite Programs

Problem Statement
Semidefinite Programs (SDPs) are a fundamental class of convex optimization problems involving linear objectives over the cone of positive semidefinite (PSD) matrices subject to linear equality constraints. While second-order interior-point methods (IPMs) can solve SDPs to arbitrary precision in polynomial time, they often suffer from computational and memory bottlenecks when applied to large-scale practical applications due to the need to solve dense, ill-conditioned linear systems. First-order methods (FOMs) have emerged as scalable alternatives, with spectral bundle methods being particularly effective for large-scale SDPs that admit low-rank solutions.

Historically, spectral bundle methods, pioneered by Helmberg and Rendl, have been developed exclusively for solving SDPs in their dual form. These methods excel when the primal SDP admits low-rank solutions, a common scenario in combinatorial optimization and phase retrieval. However, many applications, such as moment/sum-of-squares (SOS) optimization and polynomial optimization, naturally yield SDPs where the dual solution is low-rank. In these cases, existing dual-form spectral bundle methods may offer suboptimal convergence and efficiency. This paper addresses the gap by developing and analyzing spectral bundle methods specifically for the primal form of SDPs.

Methodology
The authors propose a new family of spectral bundle methods, termed $(r_p, r_c)$ -SBMP, designed to solve primal SDPs directly. The methodology mirrors the elegant duality between primal and dual SDPs, paralleling the structure of the existing dual spectral bundle methods (denoted as $(r_p, r_c)$ -SBMD).

Exact Penalization: The constrained primal SDP is reformulated into an unconstrained (or simply constrained) nonsmooth optimization problem using an exact penalty method. The semidefinite constraint $X \succeq 0$ is moved into the objective function via a penalty term involving the maximum eigenvalue of $-X$ .
Bundle Framework: The algorithm employs the generic bundle method framework, which constructs a lower approximation model of the nonsmooth objective function. Unlike standard subgradient methods, the bundle method incorporates a regularization strategy (proximal step) to improve convergence.
Spectral Approximation: A key innovation is the construction of a specialized lower approximation model using spectral information. At each iteration, the algorithm maintains a set of orthonormal vectors ( $P_t$ $P_{t}$ ) and a weight matrix ( $\bar{W}_t$ $\overset{ˉ}{W}_{t}$ ). The approximation model utilizes:
- Current Information ( $r_c$ ): The top $r_c$ eigenvectors of the current iterate (specifically of $-X$ for the primal method).
- Past Information ( $r_p$ ): A compressed accumulation of spectral information from previous iterates.
  This allows the algorithm to solve a small-scale subproblem (a quadratic SDP with dimension $r = r_p + r_c \ll n$ ) at each iteration, rather than the full-dimensional problem.
Update Strategy: The algorithm iteratively updates the reference point (primal variable) based on whether the actual decrease in the objective function meets a predicted threshold (descent step vs. null step). The spectral matrices are updated to capture the null space of the optimal solutions.

Key Contributions

Primal Spectral Bundle Methods: The paper introduces $(r_p, r_c)$ -SBMP, the first family of spectral bundle methods explicitly designed for solving primal SDPs. This complements the existing dual-focused methods.
Convergence Analysis:
- Sublinear Convergence: The authors establish an $O(1/\epsilon^3)$ convergence rate for the cost value gap, primal feasibility, dual feasibility, and duality gap under standard assumptions (Slater's condition and linear independence of constraints).
- Linear Convergence: Under the assumption of strict complementarity and when the number of current eigenvectors ( $r_c$ ) exceeds the dimension of the null space of the dual optimal solutions, the method achieves a linear convergence rate of $O(1/\epsilon)$ .
Duality and Symmetry: The paper provides a detailed comparison between the primal and dual formulations, highlighting the symmetry in parameters and convergence behaviors. It clarifies that the choice of algorithm should depend on the rank properties of the specific SDP instance:
- Existing dual methods ( $(r_p, r_c)$ -SBMD) are optimal when the primal solution is low-rank.
- The new primal methods ( $(r_p, r_c)$ -SBMP) are optimal when the dual solution is low-rank.
Open-Source Implementation: The authors provide an open-source MATLAB implementation of both primal and dual spectral bundle methods, filling a gap where existing implementations were not easily accessible.

Results
The theoretical findings are validated through extensive numerical experiments on large-scale problems:

Random SDPs: Experiments on randomly generated SDPs with known low-rank primal or dual solutions confirm that the algorithm matching the low-rank property (e.g., SBMP for low-rank dual) achieves fast linear convergence, while the mismatched algorithm exhibits slow sublinear convergence.
Max-Cut Problems: For Max-Cut relaxations, which typically have low-rank primal solutions, the dual spectral bundle method (SBMD) significantly outperforms the primal method in terms of accuracy and convergence speed.
Polynomial Optimization (SOS): For SOS relaxations of polynomial optimization problems, which typically admit low-rank dual solutions, the new primal spectral bundle method (SBMP) demonstrates superior performance.
- Comparison with Baselines: In solving quartic polynomial optimization on a sphere, $(r_p, r_c)$ -SBMP consistently outperformed state-of-the-art solvers including interior-point methods (SDPT3, MOSEK) and other first-order methods (CDCS, SDPNAL+).
- Scalability: While SDPT3 failed due to memory constraints and MOSEK struggled with larger instances, SBMP solved all tested instances to high accuracy within reasonable timeframes, often an order of magnitude faster than CDCS and with better duality gap performance than SDPNAL+.

Significance
The paper claims that the development of $(r_p, r_c)$ -SBMP provides a crucial tool for solving a specific class of large-scale SDPs that were previously less efficiently handled by spectral bundle methods. By exploiting the low-rank structure of dual solutions (common in SOS and moment problems), the new method achieves state-of-the-art efficiency and scalability. The work establishes a symmetric theoretical framework for primal and dual spectral bundle methods, offering practitioners a clear guideline on algorithm selection based on the rank properties of their specific SDP formulation. The open-source release further facilitates the adoption of these methods in the optimization community.