  A Low-rank Spectral Optimization Problem (LSOP) minimizes a linear objective
subject to multiple two-sided linear matrix inequalities intersected with a
low-rank and spectral constrained domain set. Although solving LSOP is, in
general, NP-hard, its partial convexification (i.e., replacing the domain set
by 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 the feasible set
of LSOP-R and prove their tightness for the domain sets with different matrix
spaces. The proposed rank bounds recover two well-known results in the
literature from a fresh angle and also allow us to derive sufficient conditions
under which the relaxation LSOP-R is equivalent to the original LSOP. To
effectively solve LSOP-R, we develop a column generation algorithm with a
vector-based convex pricing oracle, coupled with a rank-reduction algorithm,
which ensures the output solution satisfies the theoretical rank bound.
Finally, we numerically verify the strength of the LSOP-R and the efficacy of
the proposed algorithms.
