解非凸二次规划的分支定界缩减方法
|
摘要
目的研究带有二次约束的非凸二次规划问题。方法采用二级松弛技术、超矩形缩减与剪支技术。结果与结论提出了确定该类问题全局最优值的分支定界缩减算法,并证明了算法是收敛的,并用数值算例验证了算法的可行性与有效性。
Purpose—To study a class of non-convex quadratic programming problem with quadratic constraints.Methods—Two-level relaxation technique and a rectangular reduction-cut strategy are used to solve the aforesaid problem.Conclusion and Results—The convergence of the new algorithm is proved in addition to presenting a new branch-and-bound reduced algorithm for determining the global optimal value.The feasibility and effectiveness of this algorithm are verified by numerical examples.
Purpose—To study a class of non-convex quadratic programming problem with quadratic constraints.Methods—Two-level relaxation technique and a rectangular reduction-cut strategy are used to solve the aforesaid problem.Conclusion and Results—The convergence of the new algorithm is proved in addition to presenting a new branch-and-bound reduced algorithm for determining the global optimal value.The feasibility and effectiveness of this algorithm are verified by numerical examples.
引文
[1]王梦东,童仕宽.基于二次规划的多目标投资组合模型[J].武汉理工大学学报,2007,29(8):171-174.
[2]LOIOLA E M,ABREU N M M D,BOAVENTURA-NETTO P O,et al.A survey for the quadratic assignment problem[J].European Journal of Operational Research,2007,176(2):657-690.
[3]MATHUR K,SALKIN H M,MORITO S.A branch and search algorithm for a class of nonlinear knapsack problems[J].OperationsResearchLetters,1983,2(4):155-160.
[4]MURTY K G,Kabadi S N.Some NP-complete problems in quadratic and nonlinear programming[J].Mathematical Programming,1987,39(2):117-129.
[5]PARDALOS P M,SCHNITGER G.Checking local optimality in constrained quadratic programming is NP-hard[J].Operations Research Letters,1988,7(1):33-35.
[6]MUU L D,PHONG T Q,TAO P D.Decomposition methods for solving a class of nonconvex programming problems dealing with bilinear and quadratic functions[J].Computational Optimization and Applications,1995,4(3):203-216.
[7]李会荣,高岳林.带有二次约束非凸二次规划问题的一种全局优化方法[J].黑龙江大学自然科学版,2009,26(3):229-333.
[8]RYOO H S,SAHINIDIS N V.Global optimization of multiplicative programs[J].Journal of Global Optimization,2003,26(4):387-418.
[9]高岳林,井霞.一类线性乘积规划问题的分支定界缩减方法[J].计算数学,2013,35(1):89-98.
[10]王杉林.非凸二次规划问题的一个全局优化方法[J].重庆师范大学学报(自然科学版),2015,32(3):17-22.
[11]付文龙,杜廷松,翟军臣.基于D.C.分解的一类箱型约束的非凸二次规划的新型分支定界算法[J].数学研究,2013,46(3):311-318.
[12]高岳林,邓光智.凹二次规划问题的一个融合割平面方法的分支定界混合算法[J].工程数学学报,2008,25(4):548-596.
[13]TUY H.Global minimization of a difference of two convex functions[J].Nonlinear Analysis and Optimization,1987,30:150-182.
[2]LOIOLA E M,ABREU N M M D,BOAVENTURA-NETTO P O,et al.A survey for the quadratic assignment problem[J].European Journal of Operational Research,2007,176(2):657-690.
[3]MATHUR K,SALKIN H M,MORITO S.A branch and search algorithm for a class of nonlinear knapsack problems[J].OperationsResearchLetters,1983,2(4):155-160.
[4]MURTY K G,Kabadi S N.Some NP-complete problems in quadratic and nonlinear programming[J].Mathematical Programming,1987,39(2):117-129.
[5]PARDALOS P M,SCHNITGER G.Checking local optimality in constrained quadratic programming is NP-hard[J].Operations Research Letters,1988,7(1):33-35.
[6]MUU L D,PHONG T Q,TAO P D.Decomposition methods for solving a class of nonconvex programming problems dealing with bilinear and quadratic functions[J].Computational Optimization and Applications,1995,4(3):203-216.
[7]李会荣,高岳林.带有二次约束非凸二次规划问题的一种全局优化方法[J].黑龙江大学自然科学版,2009,26(3):229-333.
[8]RYOO H S,SAHINIDIS N V.Global optimization of multiplicative programs[J].Journal of Global Optimization,2003,26(4):387-418.
[9]高岳林,井霞.一类线性乘积规划问题的分支定界缩减方法[J].计算数学,2013,35(1):89-98.
[10]王杉林.非凸二次规划问题的一个全局优化方法[J].重庆师范大学学报(自然科学版),2015,32(3):17-22.
[11]付文龙,杜廷松,翟军臣.基于D.C.分解的一类箱型约束的非凸二次规划的新型分支定界算法[J].数学研究,2013,46(3):311-318.
[12]高岳林,邓光智.凹二次规划问题的一个融合割平面方法的分支定界混合算法[J].工程数学学报,2008,25(4):548-596.
[13]TUY H.Global minimization of a difference of two convex functions[J].Nonlinear Analysis and Optimization,1987,30:150-182.