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

Global optimization of quadratic programming problem with quadratic constraints

作　　者：马小华[1] 魏飞[1] 高岳林[1] 

机构地区：[1]北方民族大学信息与系统科学研究所,宁夏银川750021

出　　处：《兰州理工大学学报》2013年第3期136-140,共5页Journal of Lanzhou University of Technology

基　　金：国家自然科学基金(11161001);北方民族大学科研项目(2013XYZ025)的资助

摘　　要：根据带有二次约束二次规划模型的特殊结构,利用乘积的凸包络和凹包络,给出带有二次约束二次规划问题的松弛线性规划问题,以确定全局最优值的下界,使用超矩形缩减技术以加快分支定界算法的收敛速度,从而提出一个求解带有二次约束二次规划问题的全局最优化算法,证明该算法的收敛性,这个新算法实际上是把分支定界方法与外逼近方法有机地结合起来.数值算例表明所提出的算法是可行的.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.

关 键 词：全局最优化 二次约束二次规划 松弛线性规划 分支定界 外逼近 缩减技术 

分 类 号：O211.1[理学—概率论与数理统计]