Abstract
In the rank-constrained optimization problem (RCOP), it minimizes a linear objective function over a prespecified closed rank-constrained domain set and $m$ generic two-sided linear matrix inequalities. Motivated by the Dantzig-Wolfe (DW) decomposition, a popular approach of solving many nonconvex optimization problems, we investigate the strength of DW relaxation (DWR) of the RCOP, which admits the same formulation as RCOP except replacing the domain set by its closed convex hull. Notably, our goal is to characterize conditions under which the DWR matches RCOP for any $m$ two-sided linear matrix inequalities. From the primal perspective, we develop the first-known simultaneously necessary and sufficient conditions that achieve: (i) extreme point exactness -- all the extreme points of the DWR feasible set belong to that of the RCOP; (ii) convex hull exactness -- the DWR feasible set is identical to the closed convex hull of RCOP feasible set; and (iii) objective exactness -- the optimal values of the DWR and RCOP coincide. The proposed conditions unify, refine, and extend the existing exactness results in the quadratically constrained quadratic program (QCQP) and fair unsupervised learning. These conditions can be very useful to identify new results, including the extreme point exactness for a QCQP problem that admits an inhomogeneous objective function with two homogeneous two-sided quadratic constraints and the convex hull exactness for fair SVD.
Introduction
Rank-Constrained Optimization Problems (RCOP) are foundational to various fields, including power systems, signal processing, and fair machine learning. However, these problems are typically NP-hard due to the nonconvexity of the rank constraint. A standard approach to tackle this difficulty is the Dantzig-Wolfe Relaxation (DWR), which replaces the nonconvex domain with its closed convex hull to create a computationally tractable convex problem.
A critical theoretical challenge lies in determining when this relaxation is "exact"—that is, when the solution to the convex relaxation perfectly recovers the global optimum of the original nonconvex problem. Previous research often relied on the Slater condition or dual-perspective proofs that lacked generality. This work introduces a unified, geometric framework to characterize exactness without requiring the Slater condition, applicable to any number of constraints.
Theoretical Framework: Three Notions of Exactness
The authors define three distinct, hierarchical notions of exactness to analyze the relationship between the original RCOP and its relaxation. These relationships are visualized in the following diagram:
- Extreme Point Exactness: Every extreme point of the relaxed feasible set is also a feasible point for the original nonconvex problem. This implies objective exactness for any objective function where the relaxation is bounded.
- Convex Hull Exactness: The relaxed feasible set is exactly the closed convex hull of the original nonconvex feasible set. This is equivalent to extreme point exactness when the relaxed set is bounded.
- Objective Exactness: The optimal values of the relaxation and the original problem are identical.
Methods: The Inclusive Face Condition
The core contribution is a geometric, primal-oriented approach. Rather than analyzing the Lagrangian dual, the authors focus on the faces of the convex sets. They introduce the "Inclusive Face" condition, proving that exactness depends on whether the original nonconvex domain contains all faces of its convex hull up to a specific dimension determined by the number of linear constraints, $m$.
This geometric perspective reveals that the number of constraints ($m$) dictates the degree to which the original set must "fill in" the boundary of its convex hull. For $m=1$, the requirements are minimal; as $m$ increases, the domain must exhibit more convex-like properties to maintain exactness.
Key Results and Applications
- QCQP Breakthroughs: The framework proves that for a QCQP with a single quadratic constraint, DWR always achieves extreme point exactness. It also identifies specific conditions for convex hull exactness in problems with two-sided constraints.
- Fair Machine Learning: The paper provides the first-known convex hull exactness results for Fair SVD and extends results for Fair PCA to more complex cases involving linearly dependent groups.
- Rank Bounds: In cases where exactness fails, the authors provide formulas to upper-bound the rank of extreme points in the relaxed set, offering a measure of the relaxation's potential error.
- Generalization: The results for objective exactness in simultaneously diagonalizable QCQPs are generalized to include two-sided constraints without needing the Slater condition.
Conclusion
By shifting the focus from duality to the geometry of inclusive faces, this work provides a robust foundation for understanding the strength of Dantzig-Wolfe relaxations. Future research will look toward applying these conditions to domain sets defined by spectral functions and developing more efficient column-generation algorithms based on these theoretical insights.
Summary updated