求解非凸二次规划的一类两阶段算法研究

发布时间：2020-03-30 18:11

【摘要】：非凸二次规划是约束优化中的一个重要模型,在经济学、工程设计、投资组合等领域有着广泛的应用,在近年来受到众多的关注.与凸二次规划问题不同的是,求解非凸二次规划的全局最优解通常是NP难的,这使得设计求解非凸二次规划的算法具有一定的挑战性.近年来对非凸二次规划的算法的研究有了很大进展,但在求解规模、计算时间等指标方面仍有欠缺.本文基于最近提出的线性化方法,提出了求解非凸二次规划的一种新策略,即两阶段构造法.并基于此策略构造了求解非凸二次规划的全局和局部算法,建立了相应的收敛性分析并进行了初步的数值计算.本文的具体内容如下:首先,本文对目前非凸二次规划的研究进展进行介绍,总结了现有的求解非凸二次规划问题的分枝定界法,半定松弛技术等方法,并给出本文的研究内容.其次,基于已有的DIRECT算法提出了一种求解非凸二次规划的全局算法.先将非凸二次规划构造成一个等价的两阶段优化问题,然后利用最优值函数的连续性建立了算法的全局收敛性.再次,通过对构造的两阶段优化问题的两个阶段问题进行交替求解得到求解非凸二次规划的局部算法,建立了算法的收敛性分析,分析表明通过这种算法产生的解序列收敛到一个非凸二次规划的η局部最优解.最后,对全局算法和局部算法进行了初步的数值实验,给出相应的数值结果,数值实验表明两种算法可以分别得到非凸二次规划的全局和近似局部最优解.而且把提出的算法应用到现实生活中的一类实际问题中,为实际问题的解决提供了一个有效途径.
【图文】：

图 4.1 例 7 的两阶段全局优化算法计算结果4.1 Two-stage global optimization algorithm’s calculation results of example

图 4.2 例 8 的两阶段全局优化算法计算结果Fig. 4.2 Two-stage algorithm’s calculation results of example 8
【学位授予单位】：辽宁师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O221

【参考文献】

相关期刊论文 前8条

1 XIA Yong;;New semidefinite programming relaxations for box constrained quadratic program[J];Science China(Mathematics);2013年04期

2 杨静俐;杜廷松;;求解线性约束的二次规划神经网络学习新算法[J];计算机工程与应用;2010年24期

3 王延菲;郑小金;;基于DC分解的非凸二次规划SDP近似解[J];应用数学与计算数学学报;2009年02期

4 李会荣;高岳林;;带有二次约束非凸二次规划问题的一种全局优化方法[J];黑龙江大学自然科学学报;2008年05期

5 申培萍;刘利敏;;带非凸二次约束的二次规划问题的全局优化方法[J];工程数学学报;2008年05期

6 高岳林;邓光智;;凹二次规划问题的一个融合割平面方法的分支定界混合算法[J];工程数学学报;2008年04期

7 杜廷松;费浦生;蹇继贵;;非凸二次规划全局极小问题的新型分枝定界算法[J];计算机工程与应用;2008年17期

8 申培萍;裴永刚;顾敏娜;;求非凸二次规划全局最优解的分解线性化方法[J];河南师范大学学报(自然科学版);2008年03期

，

本文编号：2607873