论文标题
混合预测圆锥优化：用于建模等级约束的新范式
Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints
论文作者
论文摘要
我们提出了一个框架，用于建模和解决低排名优化问题，以确认最佳性。我们介绍满足$ y^2 = y $的对称投影矩阵，这是满足$ z^2 = z $的二进制变量的矩阵类似物，以模型等级约束。通过利用正则化和强双重性，我们证明这种建模范式在非凸线的正交投影矩阵上产生了可拖动的凸优化问题。此外，我们设计了外部应用算法，以解决低级别的问题以确保最佳性，通过其半决赛松弛来计算下限，并通过圆形和本地搜索技术提供近乎最佳的解决方案。我们实施了这些数值成分，并首次解决了低级优化问题，以确保最佳性。使用当前可用的空间分支和结合代码，而不是针对投影矩阵量身定制的，我们可以将精确的（分别近似）算法扩展到最多30（分别为600）行/列的矩阵。我们的算法还通过推导了流行的核规范放松的替代方案，可以证明近距离的解决方案，以概于较大的问题大小，并胜过现有的启发式方法，该替代方案将媒介从向量到矩阵的视角概括。总而言之，我们将混合反射锥优化的框架命名为以易于且统一的方式解决了低级问题，以确认最优性。
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 tractable convex optimization problems over the non-convex 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, for the first time, solve low-rank optimization problems to certifiable optimality. Using currently available spatial branch-and-bound codes, not tailored to projection matrices, we can scale our exact (resp. near-exact) algorithms to matrices with up to 30 (resp. 600) rows/columns. Our algorithms also supply certifiably near-optimal solutions for larger problem sizes and outperform existing heuristics, by deriving an alternative to the popular nuclear norm relaxation which generalizes the perspective relaxation from vectors to matrices. 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.
