一种基于Freudenthal单纯形细分的二次规划方法

发布时间：2020-11-21 11:22

　　 二次规划是一种以二次函数为目标函数,以线性函数为约束的极值问题,它是一种包含了线性规划的特殊形式的非线性规划。二次规划问题是一种典型的优化问题,与经济数学、管理科学等问题有着密切的联系,并在金融、生产制造等领域内有着广泛和重要的应用。本文针对凸二次规划问题的对偶解法进行了研究。首先,利用Glover、Greenberg和Pierskalla提出的不等式约束非线性规划的代理约束及代理对偶问题的解法,推导二次规划的代理对偶问题。每一个约束都乘上一个不小于0的代理乘子,这些乘子之和为1。每个乘子的大小代表其所对应约束的积极或有效程度。如果某一乘子为0则表示其所对应的约束为无效约束。把所有乘上代理乘子的约束相加形成一个约束,即为代理约束。通过推到,得出了一个目标函数为显式分式形式表达的代理对偶问题,其约束仅为一个单纯形函数。其次,对显示的目标函数进行分析,分式的分子和分母均为凸函数,因此构成的目标函数无法确定是凸函数还是凹函数,因此构成了一个非凸规划问题。第三,鉴于对偶问题的约束仅为一个单纯形,提出一种基于Freudenthal单纯形细分的优化方法,通过使用Freudenthal的细分方法,对单纯形进行均匀细分,得到各细分节点的坐标值,把坐标值带入目标函数,确定最大值,实现二次函数的全局优化。最后,通过二次规划例题对提出的方法进行了验证。提出的方法对约束数目小于自变量数目的二次规划问题求解非常有效,因为对偶问题的自变量数是原问题的约束数。但对于约束数大的二次规划问题,会导致对偶问题的约束是一个高维的单纯形,方法求解效率不高。因为在提高精度的要求下,必须把单纯形划分得非常细,带来了较大的计算量。因此下一步工作是结合分支定界方法,通过先粗分,再在小范围内细分的办法来加以解决。
【学位单位】：天津职业技术师范大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：O221
【部分图文】：

Lagrange乘子法的几何意义是表示寻求约束α上的一点使得该点到无约束极小点的距离最短，目标函数在该点处的值用s(λ)表示，s(λ)同x 到弧线的距离的平方是等价的两者相差一个常数 c H c,在§4.4 的例题中会看到这一点。当λ从0变化到1时，α从α化到α ,则通过 Lagrange 乘子法得到的点构成了一条弧线，见图 4-1。

显式对偶

图 4.3 隐式对偶图 4-3 隐式对偶注意到x 相对于约束的不同的位置对显示对偶问题目标函数的凸凹性的法则总能保证对偶目标函数的拟凹性，但是很难找到有效的数值解法。法的目标函数具有拟凹性质的条件，那么我们可以通过解一系列的具有划来解代理问题，图 4-2和图 4-3 分别为显式对偶和隐式对偶的目标函数
【参考文献】

相关期刊论文 前7条

1 蔡剑;;求不定二次规划全局最优解的新的线性化技术[J];西安文理学院学报(自然科学版);2015年03期

2 黎健玲;马林;王鹏;;不定整数二次规划的一个新的分支定界算法[J];工程数学学报;2010年05期

3 赵玉琴;张明望;周意元;;凸二次规划宽邻域原始-对偶势下降内点算法[J];三峡大学学报(自然科学版);2008年04期

4 张艺;线性约束凸二次规划的一个原始-对偶内点算法[J];宁波大学学报(理工版);2004年03期

5 李兴斯,宣兆成;二次规划的代理对偶问题及其解法[J];数值计算与计算机应用;1998年02期

6 宣兆成,李兴斯,隋允康;解二次规划代理对偶问题的内点法[J];大连理工大学学报;1997年05期

7 宣兆成,李兴斯;结构优化的内点序列二次规划方法[J];计算力学学报;1997年03期

本文编号：2892930