On the partial convexification for low-rank spectral optimization: rank bounds and algorithms
Abstract
A Low-rank Spectral Optimization Problem (LSOP) minimizes a linear objective function subject to multiple two-sided linear inequalities intersected with a low-rank and spectral constrained domain. Although solving LSOP is generally NP-hard, its partial convexification (i.e., replacing the domain with its convex hull), termed “LSOP-R," is often tractable and yields a high-quality solution. This motivates us to study the strength of LSOP-R. Specifically, we derive rank bounds for any extreme point of LSOP-R in different matrix spaces and prove their tightness. The proposed rank bounds recover two well-known results in the literature from a fresh angle and allow us to derive sufficient conditions under which the relaxation LSOP-R is equivalent to LSOP. To effectively solve LSOP-R, we develop a column generation algorithm with a vector-based convex pricing oracle and a rank-reduction algorithm, which ensures that the output solution always satisfies the theoretical rank bound. Finally, we numerically verify the strength of LSOP-R and the efficacy of the proposed algorithms.
Related
- Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization
- Combinatorial Algorithms for Partial Inverse Min-Max Spanning Tree Problem under the Weighted Sum Hamming Distance
- Design-Based Validation Method of EHR Algorithms to Address Partial Verification Bias
- Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms
- Functional Analysis and Partial Differential Equations in Spectral Barron Spaces
BibTeX
@article{li2026partial,
title = {{On the partial convexification for low-rank spectral optimization: rank bounds and algorithms}},
author = {Yongchun Li and Weijun Xie},
journal = {Mathematical Programming},
year = {2026},
month = oct,
doi = {10.1007/s10107-025-02316-y},
url = {https://hal.science/hal-05783679v1},
note = {CC BY},
}
RIS
TY - JOUR
TI - On the partial convexification for low-rank spectral optimization: rank bounds and algorithms
AU - Yongchun Li
AU - Weijun Xie
PY - 2026
DA - 2026/10/07
JO - Mathematical Programming
DO - 10.1007/s10107-025-02316-y
UR - https://hal.science/hal-05783679v1
AB - A Low-rank Spectral Optimization Problem (LSOP) minimizes a linear objective function subject to multiple two-sided linear inequalities intersected with a low-rank and spectral constrained domain. Although solving LSOP is generally NP-hard, its partial convexification (i.e., replacing the domain with its convex hull), termed “LSOP-R," is often tractable and yields a high-quality solution. This motivates us to study the strength of LSOP-R. Specifically, we derive rank bounds for any extreme point of LSOP-R in different matrix spaces and prove their tightness. The proposed rank bounds recover two well-known results in the literature from a fresh angle and allow us to derive sufficient conditions under which the relaxation LSOP-R is equivalent to LSOP. To effectively solve LSOP-R, we develop a column generation algorithm with a vector-based convex pricing oracle and a rank-reduction algorithm, which ensures that the output solution always satisfies the theoretical rank bound. Finally, we numerically verify the strength of LSOP-R and the efficacy of the proposed algorithms.
SN - 0025-5610
SN - 1436-4646
ER -