Solving Rank-Constrained Semidefinite Programs in Exact Arithmetic
Solving Rank-Constrained Semidefinite Programs in Exact Arithmetic
复制标题
DOI：
10.1145/2930889.2930925
复制
发表时间：
2016-02
期刊：
影响因子：
--
通讯作者：
Simone Naldi
中科院分区：
文献类型：
--
作者：
Simone Naldi
考虑半正定矩阵锥的仿射部分上的线性函数极小化问题，并附加约束条件，即可行矩阵具有规定的秩。当秩约束是活动的时，这是一个非凸优化问题，否则它是一个半定规划。两者都有许多应用，特别是在系统控制理论和组合优化中，甚至在更一般的情况下，如多项式优化或真实的代数。虽然存在数值算法来解决这个问题，如边界点或牛顿算法，在本文中，我们提出了一种基于符号计算的方法。我们设计了一个精确的算法求解秩约束半定规划，其复杂性基本上是二次的自然度界相关的给定的优化问题：对于子族的可行矩阵的大小是固定的问题，复杂性是多项式的变量的数量。该算法的输入数据的假设下工作：我们证明，这些假设是一般满足。我们还实现了它在Maple和讨论实际实验。
We consider the problem of minimizing a linear function over an affine section of the cone of positive semidefinite matrices, with the additional constraint that the feasible matrix has prescribed rank. When the rank constraint is active, this is a non-convex optimization problem, otherwise it is a semidefinite program. Both find numerous applications especially in systems control theory and combinatorial optimization, but even in more general contexts such as polynomial optimization or real algebra. While numerical algorithms exist for solving this problem, such as interior-point or Newton-like algorithms, in this paper we propose an approach based on symbolic computation. We design an exact algorithm for solving rank-constrained semidefinite programs, whose complexity is essentially quadratic on natural degree bounds associated to the given optimization problem: for subfamilies of the problem where the size of the feasible matrix is fixed, the complexity is polynomial in the number of variables. The algorithm works under assumptions on the input data: we prove that these assumptions are generically satisfied. We also implement it in Maple and discuss practical experiments.