一种求解二次约束二次规划问题的自适应全局优化算法

An adaptive global optimization algorithm for solving quadratically constrained quadratic programming problems

为了更好地解决二次约束二次规划问题(QCQP),本文基于分支定界算法框架提出了自适应线性松弛技术,在理论上证明了这种新的定界技术对于解决(QCQP)是可观的。文中分支操作采用条件二分法便于对矩形进行有效剖分;通过缩减技术删除不包含全局最优解的部分区域,以加快算法的收敛速度。最后,通过数值结果表明提出的算法是有效可行的。

In order to better solve the quadratically constrained quadratic programming problem(QCQP),an adaptive linearized relaxation technique based on the framework of the branch and bound algorithm is proposed in this paper,which theoretically proved that this new delimitation technique is considerable for solving(QCQP).The branch operation in this paper adopts the conditional dichotomy to facilitate effective division of the rectangle;the reduction technique is used to delete some regions that do not contain the global optimal solution to speed up the convergence of the algorithm.Finally,the numerical results show that the proposed algorithm in this paper is effective and feasible.