2022年非线性计划问题的两种方法 .pdf

《2022年非线性计划问题的两种方法 .pdf》由会员分享，可在线阅读，更多相关《2022年非线性计划问题的两种方法 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 / 8 第一章 非线性规划问题的基础概念1.1 非线性规划问题的简介非线性规划问题时形成于二十世纪五十年代的新兴学科，是运筹学的一个重要分支1。库恩和塔克于1951 年发表的关于最优性条件( 后来称为库恩塔克条件，又称为K-T 条件 的论文是非线性规划正式诞生的一个重要标志。非线性规划问题主要研究的是在线性或非线性的约束函数条件下线性或非线性的目标函数的最优化问题，典型的应用领域包括预报、生产流程的安排、库存控制、质量控制、过程设计等诸多方面。特别是在最近三十多年，非线性规划的发展很快，不断有研究者提出各种新的算法，并其的应用范围也越来越广泛，例如在各种预报、管理方面、最优设计、质量控制、

2、系统控制等领域。1.2 共轭梯度法简介共轭梯度法一开始是1908 年由 Schmidt 引入梯度类方法计算效率高, 特别是Hestenes 和 Stiefel在大约 1951 年经过不断的改进 , 并且和统计类反演方法结合形成了统计加迭代的组合反演方法, 消除了依赖于初始猜测的缺点, 成了一种广受欢迎的反演方案。共扼梯度法具有结构简单, 计算量小 , 存储量少且构造搜索方向不需要求解线性方程组以及算法具有二次终止性等优点, 因此该算法是最优化方法中相对较好的一种方法, 特别是在求解大规模无约束最优化间题时更是得到了广泛的应用 1.3 变尺度法简介变尺度法是近30 多年来发展起来的，它是求解无约

3、束极值问题的一种有效方法。由于它既避免了计算二阶导数矩阵及其求逆过程，又比梯度法的收敛速度快，特别是对高维问题具有显著地优越性，因而使变尺度法获得了更高的声誉，至今仍被公认为求解无约束极值问题最有效的算法之一。第二章 共轭梯度法2.1 引言共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算 Hesse 矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一. 1）最初是由计算数学家Hestenes 和几何学家 Stiefel于 1952 年 为求正定 系 数

4、 矩阵 线 性 方 程 组 而 独 立 提 出 的 . 他 们 合 作 的 著名 文 章Method of conjugate gradients for solving linear systems 被认为是共轭梯度法的奠基性文章。2）1964 年，Fletcher和 Reeves 将此方法推广到非线性最优化，得到了求解一般函数极小值的共轭梯度法. （3）共轭梯度法的收敛性分析的早期工作主要由Fletcher 、Powell 、Beale 等学者给出 . （4） Nocedal 、Gilbert、Nazareth 、Al-Baali、Storey 、 Dai、Yuan和 Han等学者在收敛性

5、方面得到了不少新成果. 共轭梯度法 conjugate gradient method, CG）是以共轭方向 conjugate direction）作为搜索方向的一类算法。CG法是由Hesteness 和 Stiefel于精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 8 页2 / 8 1952 年为求解线性方程组而提出的。后来用于求解无约束最优化问题，它是一种重要的数学优化方法。这种方法具有二次终止性。2.2 基本原理由于，故有但故 2-1）任取初始近似点，并取初始搜索方向为此点的负梯度方向，即沿射线进行一维搜索，得算出，因为从而可

6、知和正交 这里假设和均不等于零）。和构成一正交系，我们可以在由它们生成的二维子空间中寻求。为此，可令式中为待定系数，欲使与与A共轭，由式，必须故令由此可得以为搜索方向进行最优一维搜索，可得算出，假定，因和为A共轭，故但故由于精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 8 页3 / 8 所有即和构成一正交系。现由它们生成的三维子空间中，寻求与和为A 共轭的搜索方向。令式中和均为待定系数。由于应与和为A共轭，故须从而解之得令，则，于是继续上述步骤，可得一般公式如下：对于正定二次函数来说，由式由于进行的是最优一维上述，故有从而如此，即可得

7、共轭梯度法的一组计算公式如下：其中为初始近似，由于以及，故式也可以写成2.3 共轭梯度法的算法1）选择初始近似，给出允许误差2）计算并用式和式算出。3）一般地，假定已得出和，则克计算其第k+1 次近似：4）若，停止计算，即为要求的近似解。否则，若，则用式和式计算和，并转向第 3）步。2.4 数值实验求下述二次函数的极小点：解 将化成式的形式，得现从开始，由于故于是故精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 8 页4 / 8 第三章变尺度法3.1 基本原理假定无约束极值问题的目标函数具有二阶连续偏导数，X为其极小点的某一近似。在这个

8、点附近取的二阶泰勒多项式逼近 3-1）则其梯度为 3-2 ）这个近似函数的极小点满足 3-3）从而 3-4 ）其中为在点的海赛矩阵。如果是二次函数，则为常数阵。这时，逼近式3-1）是准确的。在这种情况下，从任一点出发，用 3-4）式只要一步即可求出的极小点 假定正定）。当不是二次函数时，3-1）式仅是在点附近的近似表达式。这时，按3-4）式求得的极小点，只是的极小点的近视。在这种情况下，人们常取为搜索方向，即 3-5）3-5）式确定的搜索方向，为在点的牛顿方向。3.2 计算步骤精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 8 页5 /

9、 8 1）给定初始点及梯度允许误差。 2）若则即为近似极小点，停止迭代。否则，转向下一步。 3）令单位阵）在方向进行一维搜索，确定最佳步长：如此可得下一个近似点 4）一般地，设已得到近似点，算出，若则即为所求的近似解，停止迭代；否则，按式计算，并令在方向进行一维搜索，确定最佳步长：其下一个近似点为 5）若点满足精度要求，则即为所求的近似解。否则，转回第四步，知道求出某点满足要求为止。3.3 数值实验精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 8 页6 / 8 下面我们针对变尺度法进行数值实验：解：取，由于故令可得由此可得精选学习资料

10、 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 8 页7 / 8 故如上求最佳步长，可得代入上式得这就是极小点。参考文献：1 胡运权著 . 运筹学教程【 M 】. 北京：清华大学出版社， 2003 2 王宜举、修乃华著 . 非线性规划理论与算法【M 】. 西安：陕西科学技术出版社， 2008 3 袁亚湘著 . 非线性规划数值方法【 M 】. 上海：上海科学技术出版社，1993 4 袁亚湘、孙文瑜著 . 最优化理论与方法【 M 】. 北京：科学出版社， 1997 4 王德人著 . 非线性方程组解法与最优化方法. 北京：人民教育出版社，1979 5 中

11、国科学院数学研究所运筹室编. 最优化方法 . 北京：科学出版社，1980 6 席少霖、赵凤治著 . 最优化计算方法 . 上海：上海科学技术出版社，1983 7 M.阿佛里耳著 . 李元熹等译 . 非线性规划分析与方法. 上海：上海科 学技术出版社， 1979 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 8 页8 / 8 8 戴彧虹、袁亚湘著 . 非线性共轭梯度法 . 上海：上海科学技术出版社，1994 9 戚厚铎、韩继业、刘光辉著. 修正 HestenesStiefel共轭梯度算法 . 数学年刊， 1996，17A3 ）；177284 10 席少霖著 . 约束变尺度法【 J】. 运筹学学报， 1985年 01 期11 张慧生、王堂生著 . 约束变尺度法应用探讨【 J】. 新疆工学院学报，1994,15A）；249253 12 赵凤治、尉继英著 . 约束最优化的计算方法【 M 】. 北京：科学出版社，1991 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 8 页