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

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

1、精选学习资料 - - - - - - - - - 第一章 非线性规划问题的基础概念1.1 非线性规划问题的简介 非线性规划问题时形成于二十世纪五十岁月的新兴学科,是运筹学的一个重要 分支 1 ；库恩和塔克于 1951 年发表的关于最优性条件 后来称为库恩塔克 条件,又称为 K-T 条件 的论文是非线性规划正式产生的一个重要标志；非 线性规划问题主要讨论的是在线性或非线性的约束函数条件下线性或非线性的 目标函数的最优化问题,典型的应用领域包括预报、生产流程的支配、库存控 制、质量掌握、过程设计等诸多方面；特殊是在最近三十多年,非线性规划的进展很快,不断有讨论者提出各种新的算法,并其的应用范畴也越

2、来越广泛,例如在各种预报、治理方面、最优设计、质量掌握、系统掌握等领域；1.2 共轭梯度法简介 共轭梯度法一开头是 1908 年由 Schmidt 引入梯度类方法运算效率高 , 特殊是 Hestenes 和 Stiefel 在大约 1951 年经过不断的改进 , 并且和统计类反演方法结 合形成了统计加迭代的组合反演方法 , 排除了依靠于初始推测的缺点 , 成了一种广受欢迎的反演方案；共扼梯度法具有结构简洁, 运算量小 , 储备量少且构造搜索方向不需要求解线性方程组以及算法具有二次终止性等优点 , 因此该算法是最优化方法中相对较好的一种方法 , 特殊是在求解大规模无约束最优化间题时更是得到了广泛

3、的应用 1.3 变尺度法简介变尺度法是近 30 多年来进展起来的,它是求解无约束极值问题的一种有效方法；由于它既防止了运算二阶导数矩阵及其求逆过程,又比梯度法的收敛速度快,特殊是对高维问题具有显著地优越性,因而使变尺度法获得了更高的声誉,至今仍被公认为求解无约束极值问题最有效的算法之一；其次章 共轭梯度法2.1 引言共轭梯度法是介于最速下降法与牛顿法之间的一个方法,它仅需利用一阶导数信息,但克服了最速下降法收敛慢的缺点,又防止了牛顿法需要储备和运算 Hesse 矩阵并求逆的缺点,共轭梯度法不仅是解决大型线性方程组最有用的方法之一,也是解大型非线性最优化最有效的算法之一 . 1）最初是由运算数学

4、家 Hestenes 和几何学家 Stiefel 于 1952 年 为求正定 系 数 矩 阵 线 性 方 程 组 而 独 立 提 出 的 . 他 们 合 作 的 著 名 文 章 Method of conjugate gradients for solving linear systems 基性文章；被认为是共轭梯度法的奠2）1964 年,Fletcher 和 Reeves 将此方法推广到非线性最优化,得到了求解一般函数微小值的共轭梯度法 . （3）共轭梯度法的收敛性分析的早期工作主要由Beale 等学者给出 . Fletcher 、Powell 、（4） Nocedal 、Gilbert、N

5、azareth 、 Al-Baali、 Storey 、 Dai、 Yuan和 Han等学者在收敛性方面得到了不少新成果. 共轭梯度法 conjugate gradient method, CG）是以共轭方向 conjugate direction）作为搜寻方向的一类算法；CG法是由Hesteness 和 Stiefel于1 / 8 名师归纳总结 - - - - - - -第 1 页,共 8 页精选学习资料 - - - - - - - - - 1952 年为求解线性方程组而提出的；后来用于求解无约束最优化问题,它是一 种重要的数学优化方法；这种方法具有二次终止性；2.2 基本原理由于,故有但故

6、 2-1）任取初始近似点,并取初始搜寻方向为此点的负梯度方向,即沿射线 进行一维搜寻,得算出,由于从而可知和正交 这里假设和均不等于零）；和构成一正交系,我们可以在由它们生成的二维子空间中寻求为此,可令 式中为待定系数,欲使与与 A 共轭,由式,必需 故 令 由此可得 以为搜寻方向进行最优一维搜寻,可得 算出,假定,因和为 A 共轭,故 但 故 由于2 / 8 名师归纳总结 - - - - - - -第 2 页,共 8 页精选学习资料 - - - - - - - - - 全部 即和构成一正交系；现由它们生成的三维子空间中,寻求与和为A 共轭的搜寻方向；令 式中和均为待定系数；由于应与和为 A

7、共轭,故须 从而 解之得 令,就,于是 连续上述步骤,可得一般公式如下：对于正定二次函数来说,由式 由于进行的是最优一维上述,故有 从而 如此,即可得共轭梯度法的一组运算公式如下：其中为初始近似,由于以及,故式也可以写成 2.3 共轭梯度法的算法 1）挑选初始近似,给出答应误差2）运算并用式和式算出；3）一般地,假定已得出和,就克运算其第k+1 次近似：4）如,停止运算,即为要求的近似解；否就,如,就用式和式运算和,并转向第 3）步；2.4 数值试验 求下述二次函数的微小点：解 将化成式的形式,得 现从开头,由于 故 于是 故3 / 8 名师归纳总结 - - - - - - -第 3 页,共

8、8 页精选学习资料 - - - - - - - - - 第三章 变尺度法3.1 基本原理假定无约束极值问题的目标函数具有二阶连续偏导数,X为其微小点的某一近似；在这个点邻近取的二阶泰勒多项式靠近 3-1）就其梯度为 3-2 ）这个近似函数的微小点满意 3-3 ）从而 3-4 ）其中为在点的海赛矩阵；3-1）是精确的；在这种情正假如是二次函数,就为常数阵；这时,靠近式况下,从任一点动身,用 3-4 ）式只要一步即可求出的微小点 假定定）；当不是二次函数时,3-1）式仅是在点邻近的近似表达式；这时,按3-4）式求得的微小点,只是的微小点的近视；在这种情形下,人们常取为搜寻方向,即 3-5 ）3-5

9、）式确定的搜寻方向,为在点的牛顿方向；3.2 运算步骤4 / 8 名师归纳总结 - - - - - - -第 4 页,共 8 页精选学习资料 - - - - - - - - - 1）给定初始点及梯度答应误差； 2）如就 即为近似微小点,停止迭代；否就,转向下一步； 3）令单位阵）在方向进行一维搜寻,确定正确步长：如此可得下一个近似点 4）一般地,设已得到近似点,算出,如就即为所求的近似解,停止迭代；否就,按式运算,并令在方向进行一维搜寻,确定正确步长：其下一个近似点为 5）如点满意精度要求,就即为所求的近似解；否就,转回第四步,知道求出某点满意要求为止；3.3 数值试验5 / 8 名师归纳总结

10、 - - - - - - -第 5 页,共 8 页精选学习资料 - - - - - - - - - 下面我们针对变尺度法进行数值试验：解：取,由于故令可得由此可得6 / 8 名师归纳总结 - - - - - - -第 6 页,共 8 页精选学习资料 - - - - - - - - - 故如上求正确步长,可得代入上式得这就是微小点；参考文献：1 胡运权著 . 运筹学教程【 M】. 北京：清华高校出版社, 2003 2 王宜举、修乃华著 . 非线性规划理论与算法【出版社, 2022 M】. 西安：陕西科学技术3 袁亚湘著 . 非线性规划数值方法【 M】. 上海：上海科学技术出版社,1993 4 袁

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