一种新的二次约束二次规划问题的分支定界算法

A New Branch and Bound Algorithm for Quadratically Constrained Quadratic Programming Problem

本文为了获得二次约束二次规划(QCQP)问题的全局最优解,提出一种新的参数化线性松弛分支定界算法.该算法利用参数化线性松弛技术,得到(QCQP)的全局最小值的下界,并利用区域缩减技术以最大限度地删除不可行区域,加快该算法的收敛速度.数值实验表明,本文提出的算法是有效并且可行的.

In this paper,in order to obtain globally optimal solution of the quadratically constrained quadratic programming problem(QCQP),a new parametric linearized relaxation branch and bound algorithm is proposed.Our algorithm utilize the parametric linearized relaxation technique to get the lower bound of the global minimum value of(QCQP),using the region-reduction-technique to delete the infeasible region as much as possible in which can accelerate the convergence speed of the algorithm.The numerical experiments show that the proposed algorithm is effective and feasible.