非线性规划问题的两种方法样本

第一章非线性规划问题基本概念1.1非线性规划问题简介非线性规划问题时形成于二十世纪五十年代新兴学科，是运筹学一个重要分支[1]。库恩和塔克于1951年刊登关于最优性条件(日后称为库恩－塔克条件，又称为K-T条件)论文是非线性规划正式诞生一种重要标志。非线性规划问题重要研究是在线性或非线性约束函数条件下线性或非线性目的函数最优化问题，典型应用领域涉及预报、生产流程安排、库存控制、质量控制、过程设计等诸多方面。特别是在近来三十近年，非线性规划发展不久，不断有研究者提出各种新算法，并其应用范畴也越来越广泛，例如在各种预报、管理方面、最优设计、质量控制、系统控制等领域。1.2共轭梯度法简介共轭梯度法一开始是19由Schmidt引入梯度类办法计算效率高,特别是Hestenes和Stiefel在大概1951年通过不断改进,并且和记录类反演办法结合形成了记录加迭代组合反演办法,消除了依赖于初始猜测缺陷,成了一种广受欢迎反演方案。共扼梯度法具备构造简朴,计算量小,存储量少且构造搜索方向不需规定解线性方程组以及算法具备二次终结性等长处,因而该算法是最优化办法中相对较好一种办法,特别是在求解大规模无约束最优化间题时更是得到了广泛应用"1.3变尺度法简介变尺度法是近30近年来发展起来，它是求解无约束极值问题一种有效办法。由于它既避免了计算二阶导数矩阵及其求逆过程，又比梯度法收敛速度快，特别是对高维问题具备明显地优越性，因而使变尺度法获得了更高名誉，至今仍被公以为求解无约束极值问题最有效算法之一。第二章共轭梯度法2.1引言共轭梯度法是介于最速下降法与牛顿法之间一种办法，它仅需运用一阶导数信息，但克服了最速下降法收敛慢缺陷，又避免了牛顿法需要存储和计算Hesse矩阵并求逆缺陷，共轭梯度法不但是解决大型线性方程组最有用办法之一，也是解大型非线性最优化最有效算法之一.（1）最初是由计算数学家Hestenes和几何学家Stiefel于1952年为求正定系数矩阵线性方程组而独立提出.她们合伙知名文章Methodofconjugategradientsforsolvinglinearsystems被以为是共轭梯度法奠基性文章。（2）1964年，Fletcher和Reeves将此办法推广到非线性最优化，得到了求解普通函数极小值共轭梯度法.共轭梯度法收敛性分析初期工作重要由Fletcher、Powell、Beale等学者给出.Nocedal、Gilbert、Nazareth、Al-Baali、Storey、Dai、Yuan和Han等学者在收敛性方面得到了不少新成果.共轭梯度法（conjugategradientmethod，CG）是以共轭方向（conjugatedirection）作为搜索方向一类算法。CG法是由Hesteness和Stiefel于1952年为求解线性方程组而提出。日后用于求解无约束最优化问题，它是一种重要数学优化办法。这种办法具备二次终结性。2.2基本原理由于，故有但故（2-1）任取初始近似点，并取初始搜索方向为此点负梯度方向，即沿射线进行一维搜索，得算出，由于从而可知和正交（这里假设和均不等于零）。和构成一正交系，咱们可以在由它们生成二维子空间中谋求。为此，可令式中为待定系数，欲使与与A共轭，由式，必要故令由此可得觉得搜索方向进行最优一维搜索，可得算出，假定，因和为A共轭，故但故由于所有即和构成一正交系。现由它们生成三维子空间中，谋求与和为A共轭搜索方向。令式中和均为待定系数。由于应与和为A共轭，故须从而解之得令，则，于是继续上述环节，可得普通公式如下：对于正定二次函数来说，由式由于进行是最优一维上述，故有从而如此，即可得共轭梯度法一组计算公式如下：其中为初始近似，由于以及，故式也可以写成2.3共轭梯度法算法（1）选取初始近似，给出容许误差（2）计算并用式和式算出。（3）普通地，假定已得出和，则克计算其第k+1次近似：（4）若，停止计算，即为规定近似解。否则，若，则用式和式计算和，并转向第（3）步。2.4数值实验求下述二次函数极小点：解将化成式形式，得现从开始，由于故于是故第三章变尺度法3.1基本原理假定无约束极值问题目的函数具备二阶持续偏导数，X为其极小点某一近似。在这个点附近取二阶泰勒多项式逼近（3-1）则其梯度为（3-2）这个近似函数极小点满足（3-3）从而（3-4）其中为在点海赛矩阵。如果是二次函数，则为常数阵。这时，逼近式（3-1）是精确。在这种状况下，从任一点出发，用（3-4）式只要一步即可求出极小点（假定正定）。当不是二次函数时，（3-1）式仅是在点附近近似表达式。这时，按（3-4）式求得极小点，只是极小点近视。在这种状况下，人们常取为搜索方向，即（3-5）（3-5）式拟定搜索方向，为在点牛顿方向。3.2计算环节（1）给定初始点及梯度容许误差。（2）若则即为近似极小点，停止迭代。否则，转向下一步。（3）令（单位阵）在方向进行一维搜索，拟定最佳步长：如此可得下一种近似点（4）普通地，设已得到近似点，算出，若则即为所求近似解，停止迭代；否则，按式计算，并令在方向进行一维搜索，拟定最佳步长：其下一种近似点为（5）若点满足精度规定，则即为所求近似解。否则，转回第四步，懂得求出某点满足规定为止。3.3数值实验下面咱们针对变尺度法进行数值实验：解：取，由于故令可得由此可得故如上求最佳步长，可得代入上式得这就是极小点。参照文献：[1]胡运权著.运筹学教程【M】.北京：清华大学出版社，[2]王宜举、修乃华著.非线性规划理论与算法【M】.西安：陕西科学技术出版社，[3]袁亚湘著.非线性规划数值办法【M】.上海：上海科学技术出版社，1993[4]袁亚湘、孙文瑜著.最优化理论与办法【M】.北京：科学出版社，1997[4]王德人著.非线性方程组解法与最优化办法.北京：人民教诲出版社，1979[5]中华人民共和国科学院数学研究所运筹室编.最优化办法.北京：科学出版社，1980[6]席少霖、赵凤治著.最优化计算办法.上海：上海科学技术出版社，1983[7]M.阿佛里耳著.李元熹等译.非线性规划——分析与办法.上海：上海科学技术出版社，1979[8]戴彧虹、袁亚湘著.非线性共轭梯度法.上海：上海科学技术出版社，1994[9]戚厚铎、韩继业、刘光辉著.修正He