On The Reduction of Duality Gap in Box Constrained Nonconvex Quadratic Program
On The Reduction of Duality Gap in Box Constrained Nonconvex Quadratic Program
复制标题
DOI：
10.1137/100802153
复制
发表时间：
2011-08
期刊：
影响因子：
--
通讯作者：
Yong Xia;Xiaoling Sun;Duan Li;Xiaojin Zheng
中科院分区：
文献类型：
--
作者：
Yong Xia;Xiaoling Sun;Duan Li;Xiaojin Zheng
本文研究了箱约束非凸二次规划与其半定规划松弛（或拉格朗日对偶）之间对偶间隙的缩小问题。通过一组鞍点型条件刻画零对偶间隙，提出了一个多面体集C与扰动非凸集Λ（θ）之间的参数化距离测度δ（θ），用以度量零对偶间隙最优性条件的不满足程度.然后导出了对对偶间隙的低估，这导致对于所识别的最佳参数θ*，对偶间隙与δ2（θ*）成比例地减小。这种对偶间隙的缩减可以推广到同时具有盒子约束和线性等式约束的情形。证明了δ（θ*）的计算可以归结为离散几何中超平面排列的胞元计数问题。特别是，我们表明，减少对偶间隙可以在多项式时间内实现一个固定的退化度的修改…
In this paper, we investigate in this paper the reduction of the duality gap between box constrained nonconvex quadratic programming and its semidefinite programming (SDP) relaxation (or Lagrangian dual). Characterizing the zero duality gap by a set of saddle-point-type conditions, we propose a parameterized distance measure δ(θ) between a polyhedral set C and a perturbed nonconvex set Λ(θ) to measure the dissatisfaction degree of the optimality conditions for zero duality gap. An underestimation of the duality gap is then derived which leads to a reduction of the duality gap proportional to δ2(θ*) for the identified best parameter θ*. This reduction of duality gap can be extended to the cases with both box and linear equality constraints. We demonstrate that the computation of δ(θ*) can be reduced to the cell enumeration of hyperplane arrangement in discrete geometry. In particular, we show that the reduction of duality gap can be achieved in polynomial time for a fixed degeneracy degree of the modified ...