The Simplest Semidefinite Programs are Trivial
The Simplest Semidefinite Programs are Trivial
复制标题
最简单的半定规划是微不足道的
DOI：
10.1287/moor.20.3.590
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
Bing Yang
中科院分区：
文献类型：
--
作者：
R. Vanderbei;Bing Yang
我们考虑以下类型的最优化问题：$$Mbox{tr}CX\colon AX=B，X\quad\Mbox{正半定}\Right$这里，tr·表示迹算子，C和X是对称n×n矩阵，B是对称m×m矩阵，A·表示线性算子。这类问题被称为半定规划，由于与极大极小特征值问题和整数规划的新的界有重要的联系，近年来已成为人们非常感兴趣的对象。在对称矩阵的上下文中，最简单的线性算子具有以下形式：$$AX=MXM^T，$$其中M是任意m×n矩阵。在这篇文章中，我们证明了对于这样的线性算子，在可以给出显式解的意义下，优化问题是平凡的。
We consider optimization problems of the following type: $$\min\left\{\mbox{tr}CX\COLON AX = B, X \quad \mbox{positive semidefinite}\right\}.$$ Here, tr· denotes the trace operator, C and X are symmetric n × n matrices, B is a symmetric m × m matrix and A· denotes a linear operator. Such problems are called semidefinite programs and have recently become the object of considerable interest due to important connections with max-min eigenvalue problems and with new bounds for integer programming. In the context of symmetric matrices, the simplest linear operators have the following form: $$AX = MXM^T,$$ where M is an arbitrary m × n matrix. In this paper, we show that for such linear operators the optimization problem is trivial in the sense that an explicit solution can be given.