Tightening a copositive relaxation for standard quadratic optimization problems
Tightening a copositive relaxation for standard quadratic optimization problems
复制标题
加强标准二次优化问题的共正松弛
DOI：
10.1007/s10589-012-9522-7
复制
发表时间：
2012-12
影响因子：
2.2
通讯作者：
D. Li
中科院分区：
文献类型：
--
作者：
Y. Xia;R.-L. Sheu;X. L. Sun;D. Li
我们在本文中重点关注改进标准二次优化问题（简称标准 QP）的半定规划（SDP）松弛问题，该问题涉及最小化单纯形上的二次形式。我们首先分析标准 QP 与其 SDP 松弛之一（称为“强化 Shor 松弛”）之间的对偶差距。为了估计对偶间隙，我们利用 SDP 松弛的对偶信息构建图G*。然后，估计可以简化为一个两阶段问题，首先枚举 G* 的所有最小顶点覆盖，然后解决一系列二阶锥规划问题。当存在非零对偶间隙时，这种对偶间隙估计可以导致比强化的 Shor 的 SDP 界限更严格的下界。通过对偶间隙估计改进方案，我们进一步开发了一种启发式算法，以获得标准 QP 的良好近似解。
We focus in this paper the problem of improving the semidefinite programming (SDP) relaxations for the standard quadratic optimization problem (standard QP in short) that concerns with minimizing a quadratic form over a simplex. We first analyze the duality gap between the standard QP and one of its SDP relaxations known as “strengthened Shor’s relaxation”. To estimate the duality gap, we utilize the duality information of the SDP relaxation to construct a graphG∗. The estimation can be then reduced to a two-phase problem of enumerating first all the minimal vertex covers ofG∗and solving next a family of second-order cone programming problems. When there is a nonzero duality gap, this duality gap estimation can lead to a strictly tighter lower bound than the strengthened Shor’s SDP bound. With the duality gap estimation improving scheme, we develop further a heuristic algorithm for obtaining a good approximate solution for standard QP.
登录
查看更多内容
DOI：
10.1109/tit.1979.1056072
发表时间：
1979-07
期刊：
IEEE Trans. Inf. Theory
影响因子：
--
作者：
A. Schrijver
通讯作者：
A. Schrijver
影响因子：
2.7
作者：
I. Bomze;M. Locatelli;F. Tardella
通讯作者：
I. Bomze;M. Locatelli;F. Tardella
影响因子：
2.5
作者：
LOVASZ, L
通讯作者：
LOVASZ, L
DOI：
10.1016/s0927-0507(05)12008-8
发表时间：
2002
期刊：
--
影响因子：
--
作者：
M. Laurent;F. Rendl
通讯作者：
M. Laurent;F. Rendl
DOI：
10.1137/s0895480104429181
发表时间：
2005-06
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
C. Luz;A. Schrijver
通讯作者：
C. Luz;A. Schrijver