Date/Time : 16 Dec 2025 14:00
Venue : S17 #05-12 (Seminar Room 4)
Speaker : Yongchun Li, The Chinese University of Hong Kong

The low-rank constrained optimization arises in various machine learning and operations research problems. It minimizes a linear objective function subject to multiple two-sided linear inequalities and a low-rank domain set. Although the low-rank constrained optimization is generally NP-hard, a viable approach is to convexify the domain set (i.e., replace the domain set with its convex hull), known as “partial convexification.” Partial convexification often leads to a tractable convex relaxation; however, its solution quality lacks theoretical guarantees. To fill this gap, (i) we establish the necessary and sufficient condition under which the partial convexification matches the original low-rank constrained optimization; and (ii) we derive an upper bound on the minimum rank among all the optimal solutions of the partial convexification and prove its tightness. To efficiently solve the partial convexification, we develop a column generation algorithm combined with a rank-reduction algorithm. This combination ensures that the output solution satisfies the theoretical guarantees. Finally, our numerical experiments validate the strength of the partial convexification and the effectiveness of the proposed algorithms.

Add to calendar :