二次约束下的边界约束非凸二次规划问题的最优化算法

发布时间：2018-05-04 08:04

本文选题：非线性规划 + 二次规划　；参考：《科技通报》2017年05期

【摘要】：二次规划是非线性规划问题中较为重要的一种,非线性规划问题的发展方向是使非线性规划问题变换成以序列为基础的对二次规划问题的求解与计算。文中将二次约束下的边界约束非凸二次规划问题作为研究目标,运用改进的分支定界算法对该问题进行最优化求解。首先,利用非线性二次函数的特性对原问题实现等价问题的变换,采用新型改进的线性松弛策略实现对原问题函数的松弛效果,利用外接最小体积椭球松弛法求解目标函数最优解下界值,再用最大体积椭球紧缩法求解目标函数最优解上界值,重复迭代步骤至下界与上界相等;其次,在确定原问题的最优下界和上界后,利用超矩形缩减法及标准二分法在松弛结果基础上对超矩形实现削减,使全局中不是最优解的部分得到剔除,最终实现非凸二次规划问题最优解。通过仿真实验证明,利用文中改进型分支定界算法使非凸二次规划问题达到了全局最优解。
[Abstract]:Quadratic programming is one of the most important nonlinear programming problems. The development direction of nonlinear programming problem is to transform the nonlinear programming problem into the solution and calculation of quadratic programming problem based on sequence. In this paper, the boundary constrained nonconvex quadratic programming problem with quadratic constraints is considered as the research objective, and the improved branch and bound algorithm is used to solve the problem optimally. Firstly, the nonlinear quadratic function is used to realize the transformation of the original problem, and a new improved linear relaxation strategy is used to realize the relaxation effect of the original problem function. The minimum volume ellipsoid relaxation method is used to solve the lower bound value of the optimal solution of the objective function, and the maximum volume ellipsoid contraction method is used to solve the upper bound value of the optimal solution of the objective function. The iterative steps are repeated until the lower bound is equal to the upper bound. After determining the optimal lower bound and upper bound of the original problem, the hyperrectangular reduction method and the standard dichotomy method are used to reduce the hyperrectangle on the basis of the relaxation results, so that the parts of the whole world which are not the optimal solution are eliminated. Finally, the optimal solution of nonconvex quadratic programming problem is realized. The simulation results show that the improved branch and bound algorithm is used to achieve the global optimal solution of the non-convex quadratic programming problem.
【作者单位】：商丘学院计算机工程学院;
【基金】：国家自然科学基金(11501345)
【分类号】：O221.2

【相似文献】