# On the Exactness of Dantzig-Wolfe Relaxation for Rank Constrained Optimization Problems

arXiv: https://arxiv.org/abs/2210.16191 · HTML: https://mlsanity.com/paper/2210.16191/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 69 references that are in the map.
- First posted on arXiv 28 Oct 2022.

## Builds on (most cited first, 20 of 20)

- [The Price of Fair PCA: One Extra Dimension](https://mlsanity.com/paper/1811.00103/) (2018)
- [AC Power Flow Data in MATPOWER and QCQP Format: iTesla, RTE Snapshots, and PEGASE](https://mlsanity.com/paper/1603.01533/) (2016)
- [A new perspective on low-rank optimization](https://mlsanity.com/paper/2105.05947/) (2021)
- [Ideal formulations for constrained convex optimization problems with indicator variables](https://mlsanity.com/paper/2007.00107/) (2020)
- [Exact Semidefinite Formulations for a Class of (Random and Non-Random) Nonconvex Quadratic Programs](https://mlsanity.com/paper/1802.02688/) (2018)
- [On the tightness of SDP relaxations of QCQPs](https://mlsanity.com/paper/1911.09195/) (2019)
- [Consensus-ADMM for General Quadratically Constrained Quadratic Programming](https://mlsanity.com/paper/1601.02335/) (2016)
- [Optimized Transmission for Parameter Estimation in Wireless Sensor Networks](https://mlsanity.com/paper/1908.00600/) (2019)
- [Exactness in SDP relaxations of QCQPs: Theory and applications](https://mlsanity.com/paper/2107.06885/) (2021)
- [Explicit convex hull description of bivariate quadratic sets with indicator variables](https://mlsanity.com/paper/2208.08703/) (2022)
- [Strong Duality for Generalized Trust Region Subproblem: S-Lemma with Interval Bounds](https://mlsanity.com/paper/1407.0465/) (2014)
- [Spectrahedral cones generated by rank 1 matrices](https://mlsanity.com/paper/1409.4781/) (2014)
- [A Second-Order Cone Based Approach for Solving the Trust Region Subproblem and Its Variants](https://mlsanity.com/paper/1603.03366/) (2016)
- [The convex hull of a quadratic constraint over a polytope](https://mlsanity.com/paper/1812.10160/) (2018)
- [Necessary and sufficient conditions for rank-one generated cones](https://mlsanity.com/paper/2007.07433/) (2020)
- [KKT-based primal-dual exactness conditions for the Shor relaxation](https://mlsanity.com/paper/2011.05033/) (2020)
- [A Geometric View of SDP Exactness in QCQPs and its Applications](https://mlsanity.com/paper/2011.07155/) (2020)
- [On obtaining the convex hull of quadratic inequalities via aggregations](https://mlsanity.com/paper/2106.12629/) (2021)
- [Exact SDP relaxations for quadratic programs with bipartite graph structures](https://mlsanity.com/paper/2204.09509/) (2022)
- [Aggregations of quadratic inequalities and hidden hyperplane convexity](https://mlsanity.com/paper/2210.01722/) (2022)

## Built on by (most cited first, 3 of 3)

- [Variable Selection for Kernel Two-Sample Tests](https://mlsanity.com/paper/2302.07415/) (2023)
- [Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances](https://mlsanity.com/paper/2405.15441/) (2024)
- [On the Partial Convexification for Low-Rank Spectral Optimization: Rank Bounds and Algorithms](https://mlsanity.com/paper/2305.07638/) (2023)

## Abstract (arXiv)

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.