论文标题
受秩限制的双曲线编程
Rank-constrained Hyperbolic Programming
论文作者
论文摘要
我们使用Matroid等级的概念扩展到一般双曲线程序（HP）的一般双曲线程序（HP）。对于LP和SDP，这将减少到已经进行了充分研究的稀疏度约束的LP和受范围约束的SDP。但是对于QCQP和SOCP而言，我们获得了新的有趣的优化问题。例如，受范围受限的SOCP包括加权最大切割和非convex QP作为特殊情况，并且放弃等级约束产生这些问题的标准SOCP - 释放。我们将展示（i）如何对SOCP和QCQP进行排名降低，（ii）（ii）将受到限制的SOCP和受等级约束的QCQP是NP-HARD，并且（iii）等级约束的SDP的改进结果表明，如果限制的数量为$ M $，并且$ M $的数量是$ M $，并且$ 2^$ 2^{1/2- $ 2-} $ 2-} $ \ sq ai} $ \ sq rt，Mort \ sq。问题是NP-HARD。我们还将研究受稀疏性受限的HP，并将LP稀疏性的结果扩展到SOCP和QCQP。特别是，我们表明（a）最多是基数的SOCP的解决方案，最多是约束数量的两倍，（b）最多最多是线性约束数量和矩阵等级的总和的总和。并且（a）和（b）均可有效地找到。
We extend rank-constrained optimization to general hyperbolic programs (HP) using the notion of matroid rank. For LP and SDP respectively, this reduces to sparsity-constrained LP and rank-constrained SDP that are already well-studied. But for QCQP and SOCP, we obtain new interesting optimization problems. For example, rank-constrained SOCP includes weighted Max-Cut and nonconvex QP as special cases, and dropping the rank constraints yield the standard SOCP-relaxations of these problems. We will show (i) how to do rank reduction for SOCP and QCQP, (ii) that rank-constrained SOCP and rank-constrained QCQP are NP-hard, and (iii) an improved result for rank-constrained SDP showing that if the number of constraints is $m$ and the rank constraint is less than $2^{1/2-ε} \sqrt{m}$ for some $ε>0$, then the problem is NP-hard. We will also study sparsity-constrained HP and extend results on LP sparsification to SOCP and QCQP. In particular, we show that there always exist (a) a solution to SOCP of cardinality at most twice the number of constraints and (b) a solution to QCQP of cardinality at most the sum of the number of linear constraints and the sum of the rank of the matrices in the quadratic constraints; and both (a) and (b) can be found efficiently.
