• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>The 8th international conference on optimization: Techniques and Applications >Optimal Weighted Reduction of Duality Gap in Binary Quadratic Optimization
【24h】

Optimal Weighted Reduction of Duality Gap in Binary Quadratic Optimization

机译：二元二次优化中对偶间隙的最优加权减小

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper, we reinvestigate the reduction of duality gap between the binary quadratic programming and its SDP relaxation (or Lagrangian dual). Characterizing the zero duality gap by a set of saddle-point-type conditions, we propose a weighted distance measure δ(w) between a polyhedral set C and a {-1, 1}n 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(w*) for certain weight w*. We demonstrate that the computation of δ(w*) can be reduced to the cell enumeration of hyperplane arrangement in discrete geometry and the optimal w* is obtained by solving an SDP. In particular, we show that the optimal weighted reduction of duality gap can be achieved in polynomial time for a fixed degeneracy degree of the coefficient matrix determined from SDP relaxation.
机译：在本文中，我们重新研究了二进制二次编程与其SDP松弛（或拉格朗日对偶）之间对偶间隙的减小。通过一组鞍点型条件表征零对偶间隙，我们提出了多面体集C与{-1，1} n之间的加权距离度量δ（w），以测量对最优条件的不满意程度零对偶间隙。然后推导出对偶间隙的低估，这导致对于某些权重w *与δ2（w *）成正比的对偶间隙减小。我们证明，δ（w *）的计算可以简化为离散几何中超平面排列的单元枚举，并且通过求解SDP可以获得最佳w *。特别地，我们表明，对于由SDP松弛确定的系数矩阵的固定简并度，可以在多项式时间内实现对偶间隙的最佳加权减小。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号