带有二次约束二次规划问题的全局最优化

摘要

According to the special structure of quadratic programming model with quadratic constraints and using the convex envelope and concave envelope of the product,the relaxation linear programming problem of quadratic programming with quadratic constraints was proposed so as to determine the lower bound of the global optimum.Using the hyper-rectangular reduction technique,the convergence speed of the branch-and-bound algorithm was accelerated.Thus,a global optimization algorithm was presented for solving quadratic programming problem with quadratic constraints and the convergence of the algorithm was proved.The new algorithm was actually an organically combined one of branch-and-bound with outer approximation.Numerical example showed that the proposed algorithm was feasible.%根据带有二次约束二次规划模型的特殊结构,利用乘积的凸包络和凹包络,给出带有二次约束二次规划问题的松弛线性规划问题,以确定全局最优值的下界,使用超矩形缩减技术以加快分支定界算法的收敛速度,从而提出一个求解带有二次约束二次规划问题的全局最优化算法,证明该算法的收敛性,这个新算法实际上是把分支定界方法与外逼近方法有机地结合起来.数值算例表明所提出的算法是可行的.