On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming
On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming
复制标题
二次矩阵规划半定松弛的等价
DOI：
10.1287/moor.1100.0473
复制
发表时间：
2011-02
影响因子：
1.7
通讯作者：
Wolkowicz, Henry
中科院分区：
文献类型：
--
作者：
Ding, Yichuan;Ge, Dongdong;Wolkowicz, Henry
我们分析了针对具有矩阵变量的二次约束二次规划的两种流行的半定规划松弛方法。这些松弛方法基于向量提升和矩阵提升；它们具有不同的规模和成本。我们证明，在……（“unde”这个词似乎不完整，可能影响了句子的准确理解）
We analyze two popular semidefinite programming relaxations for quadratically constrained quadratic programs with matrix variables. These relaxations are based on vector lifting and on matrix lifting; they are of different size and expense. We prove, under mild assumptions, that these two relaxations provide equivalent bounds. Thus, our results provide a theoretical guideline for how to choose a less expensive semidefinite programming relaxation and still obtain a strong bound. The main technique used to show the equivalence and that allows for the simplified constraints is the recognition of a class of nonchordal sparse patterns that admit a smaller representation of the positive semidefinite constraint.
登录
查看更多内容
DOI：
10.1137/s0895479898340299
发表时间：
2000-04
期刊：
SIAM J. Matrix Anal. Appl.
影响因子：
--
作者：
K. Anstreicher;Henry Wolkowicz
通讯作者：
K. Anstreicher;Henry Wolkowicz
DOI：
10.1137/040621600
发表时间：
2006-12
期刊：
SIAM J. Optim.
影响因子：
--
作者：
M. W. Carter;Holly H. Jin;M. Saunders;Y. Ye
通讯作者：
M. W. Carter;Holly H. Jin;M. Saunders;Y. Ye
DOI：
--
发表时间：
1981
期刊：
--
影响因子：
--
作者：
A. Graham
通讯作者：
A. Graham
DOI：
10.1007/978-1-4615-4381-7_13
发表时间：
2000
期刊：
--
影响因子：
--
作者：
Y. Nesterov;Henry Wolkowicz;Y. Ye
通讯作者：
Y. Nesterov;Henry Wolkowicz;Y. Ye
影响因子：
1.1
作者：
L. Hogben
通讯作者：
L. Hogben