• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Mathematical Programming >Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation
【24h】

Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation

机译：非凸二次约束二次规划的凸松弛：矩阵锥分解和多面体逼近

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

摘要

We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme and polyhedral (piecewise linear) underestimation. By employing suitable matrix cones, we then show that the convex conic relaxation can be reduced to a semidefinite programming (SDP) problem. In particular, we investigate polyhedral underestimations for several classes of matrix cones, including the cones of rank-1 and rank-2 matrices, the cone generated by the coefficient matrices, the cone of positive semidefinite matrices and the cones induced by rank-2 semidefinite inequalities. We demonstrate that in general the new SDP relaxations can generate lower bounds at least as tight as the best known SDP relaxations for QCQP. Moreover, we give examples for which tighter lower bounds can be generated by the new SDP relaxations. We also report comparison results of different convex relaxation schemes for nonconvex QCQP with convex quadratic/linear constraints, nonconvex quadratic constraints and 0–1 constraints.
机译：我们提出了一种分解近似方法，用于为非凸二次约束二次规划（QCQP）生成凸松弛。我们首先基于矩阵分解方案和多面体（分段线性）低估，为QCQP开发一般的圆锥程序松弛。通过采用合适的矩阵锥，我们然后证明了凸圆锥松弛可以减少到半定规划（SDP）问题。特别是，我们研究了几类矩阵圆锥的多面体低估，包括等级1和等级2的圆锥，由系数矩阵生成的圆锥，正半定矩阵的圆锥以及由等级2半定矩阵引起的圆锥不平等。我们证明，一般而言，新的SDP松弛可以生成下限，至少与QCQP的最著名SDP松弛一样紧密。此外，我们给出了一些示例，这些示例可以通过新的SDP松弛生成更严格的下限。我们还报告了具有凸二次/线性约束，非凸二次约束和0-1约束的非凸QCQP的不同凸松弛方案的比较结果。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号