Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization
Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization
复制标题
DOI：
10.1007/s10898-018-0617-2
复制
发表时间：
2018-02
影响因子：
1.8
通讯作者：
Shinji Yamada;A. Takeda
中科院分区：
文献类型：
--
作者：
Shinji Yamada;A. Takeda
目标函数和约束条件均为二次多项式的优化问题称为二次约束二次规划（QCQP）。QCQP问题一般是NP难问题，在优化理论和实践中具有重要意义。关于QCQP问题的近似求解已有很多研究。其中，半定规划（SDP）松弛法是一种著名的凸松弛法。近年来，许多研究者试图通过增加线性约束作为有效不等式来寻找更好的松弛解。另一方面，SDP松弛需要很长的计算时间，并且对于实际中的大规模问题具有很高的空间复杂度;因此，SDP松弛对于这样的问题可能不是有用的。在本文中，我们提出了一个新的凸松弛方法，是弱，但速度比SDP松弛方法。该方法将QCQP问题转化为拉格朗日对偶优化问题，并在更新拉格朗日乘子的同时逐次求解子问题。在我们的方法中的子问题是一个QCQP只有一个约束，我们提出了一个有效的算法。数值实验表明，我们的方法可以快速找到一个放松的解决方案，适当的终止条件。
Optimization problems whose objective function and constraints are quadratic polynomials are called quadratically constrained quadratic programs (QCQPs). QCQPs are NP-hard in general and are important in optimization theory and practice. There have been many studies on solving QCQPs approximately. Among them, a semidefinite program (SDP) relaxation is a well-known convex relaxation method. In recent years, many researchers have tried to find better relaxed solutions by adding linear constraints as valid inequalities. On the other hand, the SDP relaxation requires a long computation time, and it has high space complexity for large-scale problems in practice; therefore, the SDP relaxation may not be useful for such problems. In this paper, we propose a new convex relaxation method that is weaker but faster than SDP relaxation methods. The proposed method transforms a QCQP into a Lagrangian dual optimization problem and successively solves subproblems while updating the Lagrange multipliers. The subproblem in our method is a QCQP with only one constraint for which we propose an efficient algorithm. Numerical experiments confirm that our method can quickly find a relaxed solution with an appropriate termination condition.