New bounds for nonconvex quadratically constrained quadratic programming
\nameMoslem Zamaniabc M. Zamani. Email: a Parametric MultiObjective Optimization Research Group, Ton Duc Thang University, Ho Chi Minh City, Vietnam; b Faculty of Mathematics and Statistics, Ton Duc Thang University, Ho Chi Minh City, Vietnam; c School of Mathematics, Statistics and Computer Science, College of Science, University of Tehran, Enghelab Avenue, Tehran, Iran;
Abstract
In this paper, we study some bounds for nonconvex quadratically constrained quadratic programs. We propose two types of bounds for quadratically constrained quadratic programs, quadratic and cubic bounds. For quadratic bounds, we use affine functions as Lagrange multipliers. We demonstrate that most semi-definite relaxations can be obtained as the dual of a quadratic bound. In addition, we study bounds obtained by changing the ground set. For cubic bounds, in addition to affine multipliers we employ quadratic functions. We provide a comparison between the proposed cubic bound and typical bounds for standard quadratic programs. Moreover, we report comparison results of a quadratic and a cubic bound for some non-convex quadratically constrained quadratic programs.
中文速览
非凸二次约束二次规划（QCQP）是涵盖最大割、团问题等大量NP难组合优化问题的核心模型，如何快速算出紧的下界是求解它的关键瓶颈。这篇论文提出了两类新的下界方法：一是"二次界"，把拉格朗日乘子从常数推广到仿射函数，并证明大多数已有的半定松弛（semidefinite relaxation）都可以被统一解释为某个二次界的对偶问题；二是"三次界"，进一步把乘子扩展到二次函数，从而构造出更紧的松弛，并证明它与标准二次规划上的Parrilo层级松弛等价。数值实验表明，三次界在多个非凸QCQP算例上明显优于传统二次界，同时两类界都可以转化为标准半定规划或余正规划（copositive program）来求解。这项工作不仅为现有松弛方法提供了统一的理论框架，还给出了可实际计算的更紧下界，有望改善分支定界算法的效率。
原文 arXiv:1902.08861;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1902.08861v2