Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints

被引:9
作者
Bertsimas, Dimitris [1 ]
Cory-Wright, Ryan [2 ]
Pauphilet, Jean [3 ]
机构
[1] MIT, Sloan Sch Management & Operat Res Ctr, Cambridge, MA 02142 USA
[2] MIT, Operat Res Ctr, Cambridge, MA 02142 USA
[3] London Business Sch, London NW1 4SA, England
关键词
rank minimization; semidefinite optimization; global optimization; discrete optimization; outer approximation; regularization; perspective relaxation; matrix completion; nuclear norm; MATRIX COMPLETION; SEMIDEFINITE PROGRAMS; VARIABLE SELECTION; BOUND ALGORITHM; INTEGER; BRANCH; RELAXATIONS; COMPLEXITY; SUM; CUT;
D O I
10.1287/opre.2021.2182
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
We propose a framework for modeling and solving low-rank optimization problems to certifiable optimality. We introduce symmetric projection matrices that satisfy Y-2 = Y, the matrix analog of binary variables that satisfy z(2) = z, to model rank constraints. By leveraging regularization and strong duality, we prove that this modeling paradigm yields convex optimization problems over the nonconvex set of orthogonal projection matrices. Furthermore, we design outer-approximation algorithms to solve low-rank problems to certifiable optimality, compute lower bounds via their semidefinite relaxations, and provide near optimal solutions through rounding and local search techniques. We implement these numerical ingredients and, to our knowledge, for the first time solve low-rank optimization problems to certifiable optimality. Our algorithms also supply certifiably near-optimal solutions for larger problemsizes and outperformexisting heuristics by deriving an alternative to the popular nuclear norm relaxation. Using currently available spatial branch-and-bound codes, not tailored to projection matrices, we can scale our exact (respectively, near-exact) algorithms to matrices with up to 30 (600) rows/columns. All in all, our framework, which we name mixed-projection conic optimization, solves low-rank problems to certifiable optimality in a tractable and unified fashion.
引用
收藏
页码:3321 / 3344
页数:24
相关论文
共 81 条
[51]  
Jain P, 2013, STOC'13: PROCEEDINGS OF THE 2013 ACM SYMPOSIUM ON THEORY OF COMPUTING, P665
[52]   THE CUTTING-PLANE METHOD FOR SOLVING CONVEX PROGRAMS [J].
KELLEY, JE .
JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1960, 8 (04) :703-712
[53]   Strong SOCP Relaxations for the Optimal Power Flow Problem [J].
Kocuk, Burak ;
Dey, Santanu S. ;
Sun, X. Andy .
OPERATIONS RESEARCH, 2016, 64 (06) :1177-1196
[54]   Global optimization with polynomials and the problem of moments [J].
Lasserre, JB .
SIAM JOURNAL ON OPTIMIZATION, 2001, 11 (03) :796-817
[55]   Zero Duality Gap in Optimal Power Flow Problem [J].
Lavaei, Javad ;
Low, Steven H. .
IEEE TRANSACTIONS ON POWER SYSTEMS, 2012, 27 (01) :92-107
[56]   Optimal rank-sparsity decomposition [J].
Lee, Jon ;
Zou, Bai .
JOURNAL OF GLOBAL OPTIMIZATION, 2014, 60 (02) :307-315
[57]   A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs [J].
Linderoth, J .
MATHEMATICAL PROGRAMMING, 2005, 103 (02) :251-282
[58]   Mixed-Integer Convex Representability [J].
Lubin, Miles ;
Vielma, Juan Pablo ;
Zadik, Ilias .
MATHEMATICS OF OPERATIONS RESEARCH, 2022, 47 (01) :720-749
[59]  
Luo Z.-Q., 1996, Mathematical Programs with Equilibrium Constraints
[60]   Low-Rank Matrix Completion: A Contemporary Survey [J].
Luong Trung Nguyen ;
Kim, Junhan ;
Shim, Byonghyo .
IEEE ACCESS, 2019, 7 :94215-94237