Research map / Learning theory and algorithms / Combinatorial and search optimization
Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes USBS, a unified spectral bundle method for SDPs with equality and inequality constraints, optionally combined with Nyström matrix sketching, which scales to billions of variables and warm-starts well.
Problem
Solving large-scale semidefinite programs with both equality and inequality constraints efficiently, while keeping convergence fast and allowing warm-starts from incrementally arriving data or mixed-integer programming.
Approach
A spectral bundle method on a penalized dual that handles equality and inequality constraints, with no iteration-dependent step-size schedules (so warm starts work), combined with a Nyström sketch of the primal iterate to reduce memory.
Key results
- USBS reaches an accurate solution on all ten DIMACS10 MaxCut instances within 28 hours without warm-start, while CGAL fails on 7 of 10 within 72 hours.
- USBS gives a 500x speed-up over CGAL on an instance with 2 billion decision variables.
- Warm-starting can give more than 100x convergence speed-up for USBS versus cold-start.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use USBS instead of CGAL | scalable SDP solving · MaxCut, 2 billion decision variables | speedup: 500x | Helped |
| warm-start USBS from a related solution instead of cold-starting | USBS · SDP convergence | speedup: more than a 100x | Helped |
| use USBS instead of CGAL | scalable SDP solving · MaxCut, ten DIMACS10 instances | instances reaching an ε-approximate solution: USBS: all; CGAL: 7 out of 10 instances not solved within 72 hours | Helped |
| increase the number of current eigenvectors k_c (ablation) | USBS · Spectral bundle convergence | convergence | Helped |
| include past spectral information using k_p (ablation) | USBS · Spectral bundle convergence | convergence | Mixed |
| initialize each interior-point subproblem from the previous execution's solution (ablation) | USBS interior-point subproblem solver · Sequential subproblem solves | convergence | Helped |
| warm-start CGAL from a related solution | CGAL · SDP convergence | convergence | Mixed |
| warm-start from the smaller MaxCut instance | SDP solvers · MaxCut, 598a | convergence time | Mixed |
Surprising findings
- Larger spectral model dimension k_c gives better convergence, while past spectral information k_p is not very helpful and sometimes harmful.
- Warm-starting does not always help (e.g. instance 598a in MaxCut).
Limitations
- Convergence rates are sublinear (O(1/eps^3) generally, O(1/eps) under strict complementarity), and the bundle subproblems rely on interior point solves.
- Projected gradient alternatives for subproblems were found impractical, so an interior point method is required per iteration.
- Sketching error is constant but the Nyström rank r must be chosen by the user, trading accuracy for scalability.
Experimental setup
Datasets: DIMACS10 MaxCut instances QAPLIB TSPLIB author coreference datasets (PubMed, QIAN, SCAD-zbMATH)
Benchmarks: DIMACS10 MaxCut QAPLIB TSPLIB author coreference SDPs with exists-constraints
Metrics: solve time to relative error 1e-1 best relative gap cumulative solve time relative suboptimality and infeasibility
Baselines: CGAL CSDP PATH
Builds on: proximal bundle method spectral bundle method CGAL Nyström sketch
Closest papers by meaning
- A Scalable Frank-Wolfe-Based Algorithm for the Max-Cut SDP (ICML 2023 · similarity 0.87)
- Smoothed analysis of the low-rank approach for smooth semidefinite programs (NeurIPS 2018 · similarity 0.86)
- On the Expressive Power of GNNs to Solve Linear SDPs (ICML 2026 · similarity 0.85)
- Learning Valid Dual Bounds in Constraint Programming: Boosted Lagrangian Decomposition with Self-Supervised Learning (AAAI 2025 · similarity 0.84)
- B$^3$-PWL: GPU-Batched Branch-and-Bound for Piecewise-Linear Optimization with SOS2 Constraints (NeurIPS 2026 · similarity 0.84)
- Iterative Methods via Locally Evolving Set Process (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.