论文-非线性规划问题

绪论非线性规划问题时形成于二十世纪五十年代的新兴学科，是运筹学的一个重要分支.库恩和塔克于1951年发表的关于最优性条件(后来称为库恩－塔克条件，又称为K-T条件)的论文是非线性规划正式诞生的一个重要标志.非线性规划问题主要研究的是在线性或非线性的约束函数条件下线性或非线性的目标函数的最优化问题，典型的应用领域包括预报、生产流程的安排、库存控制、质量控制、过程设计等诸多方面.特别是在最近三十多年，非线性规划的发展很快，不断有研究者提出各种新的算法，并其的应用范围也越来越广泛，例如在各种预报、管理方面、最优设计、质量控制、系统控制等领域.2非线性规划问题的方法2.1共轭梯度法简介共轭梯度法一开始是1908年由Schmidt引入梯度类方法计算效率高,特别是Hestenes和Stiefel在大约1951年经过不断的改进,并且和统计类反演方法结合形成了统计加迭代的组合反演方法,消除了依赖于初始猜测的缺点,成了一种广受欢迎的反演方案.共扼梯度法具有结构简单,计算量小,存储量少且构造搜索方向不需要求解线性方程组以及算法具有二次终止性等优点,因此该算法是最优化方法中相对较好的一种方法,特别是在求解大规模无约束最优化间题时更是得到了广泛的应用.2.2变尺度法简介变尺度法是近30多年来发展起来的，它是求解无约束极值问题的一种有效方法。由于它既避免了计算二阶导数矩阵及其求逆过程，又比梯度法的收敛速度快，特别是对高维问题具有显著地优越性，因而使变尺度法获得了更高的声誉，至今仍被公认为求解无约束极值问题最有效的算法之一.3共轭梯度法3.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年为求解线性方程组而提出的.后来用于求解无约束最优化问题，它是一种重要的数学优化方法.这种方法具有二次终止性.3.2基本原理定理1设为对称正定阵，为共轭的非零向量，则这一组向量线性独立.证明设向量之间存在如下的线性关系对，用左乘上式得但，为正定，即故必有从而线性独立.无约束极值问题的一个特殊情形是式中为对称正定阵；；为常数。问题上式称为正定二次函数极小问题，它在整个最优化问题中起着极其重要的作用.定理2设向量，，为共轭，则从任一点出发，相继以为搜索方向的下述算法经次一维搜索收敛于问题（1）式的极小点.证明由上式设相继各次搜索得到近似解分别为，则假定，则有由于在进行一维搜索时，为确定最佳步长，令故对，有和个线性独立的向量（它们为共轭）正交，从而必有即为的极小点.由于，故有但故（1）任取初始近似点，并取初始搜索方向为此点的负梯度方向，即沿射线进行一维搜索，得算出，因为从而可知和正交（这里假设和均不等于零）.和构成一正交系，我们可以在由它们生成的二维子空间中寻求.为此，可令式中为待定系数，欲使与与A共轭，由(1)式，必须故令(2)由此可得(3)以为搜索方向进行最优一维搜索，可得算出，假定，因和为A共轭，故但故由于所以即、和构成一正交系.现由它们生成的三维子空间中，寻求与和为A共轭的搜索方向.令式中和均为待定系数.由于应与和为A共轭，故须从而解之得令，则，于是(4)继续上述步骤，可得一般公式如下：对于正定二次函数来说，,由(1)式由于进行的是最优一维上述，故有从而如此，即可得共轭梯度法的一组计算公式如下：(5)(6)(7)(8)其中为初始近似，.由于以及，故(6)式也可以写成(9)3.3共轭梯度法的算法（1）选择初始近似，给出允许误差.（2）计算并用(5)式和(6)式算出.一般地，假定已得出和，则克计算其第k+1次近似：若，停止计算，即为要求的近似解.否则，若，则用(7)式和(8)式计算和，并转向第（3）步.3.4数值实验求下述二次函数的极小点：解将化成的形式，得现从开始，由于故于是故这就是的极小点.4变尺度法4.1引言变尺度法是一个有效地求解约束问题的最优化方法，但对实际工程中存在的诸如函数不可导及函数求值复杂等非理想情况，求解尚有不少具体困难．下面从应用角度出发，通过适当选择差商形式和对一维不精确线性搜索方法的修正，提高了适用范围，并保持了其函数计算次数少和收敛速度快的特点．通过检验函数和实际问题的计算，证明改进的算法方便有效且具有较高的稳定性和普遍适用性．4.2基本原理假定无约束极值问题的目标函数具有二阶连续偏导数，X为其极小点的某一近似.在这个点附近取的二阶泰勒多项式逼近（10）（11）这个近似函数的极小点满足（12）从而（13）其中为在点的海赛矩阵.如果是二次函数，则为常数阵.这时，逼近式（11）是准确的.在这种情况下，从任一点出发，用（13）式只要一步即可求出的极小点（假定正定）.当不是二次函数时，（11）式仅是在点附近的近似表达式.这时，按（13）式求得的极小点，只是的极小点的近视.在这种情况下，人们常取为搜索方向，即(14)(15)(16)（15)(16)(17)式确定的搜索方向，为在点的牛顿方向.4.3计算步骤（1）给定初始点及梯度允许误差.（2）若则即为近似极小点，停止迭代.否则，转向下一步.（3）令（单位阵）在方向进行一维搜索，确定最佳步长：如此可得下一个近似点（4）一般地，设已得到近似点，算出，若则即为所求的近似解，停止迭代；否则，按式计算，并令在方向进行一维搜索，确定最佳步长：其下一个近似点为（5）若点满足精度要求，则即为所求的近似解.否则，转回第四步，知道求出某点满足要求为止.4.4数值实验下面我们针对变尺度法进行数值实验：解取，由于故令可得由此可得故如上求最佳步长，可得代入上式得这就是极小点.结论本文主要研究的是非线性规划问题的求解方法,主要包括下面两种方法：第一种是共轭梯度法，用于求解无约束最优化问题，它是一种重要的数学优化方法，这种方法具有二次终止性.第二种是变尺度法，它既避免了计算二阶导数矩阵及其求逆过程，又比梯度法的收敛速度快，特别是对高维问题具有显著地优越性，因而使变尺度法获得了更高的声誉，至今仍被公认为求解无约束极值问题最有效的算法之一.这两种方法是求解非线性规划问题比较有效的算法，在很多领域有很重要的运用.参考文献[1]胡运权著.运筹学教程[M].北京：清华大学出版社，2003[2]王宜举、修乃华著.非线性规划理论与算法[M].西安：陕西科学技术出版社，2008[3]袁亚湘著.非线性规划数值方法[M].上海：上海科学技术出版社，1993[4]袁亚湘、孙文瑜著.最优化理论与方法[M].北京：科学出版社，1997[4]王德人著.非线性方程组解法与最优化方法[M].北京：人民教育出版社，1979[5]中国科学院数学研究所运筹室编.最优化方法.北京：科学出版社，1980[6]席少霖、赵凤治著.最优化计算方法[M].上海：上海科学技术出版社，1983[7]阿佛里耳著、李元熹等译.非线性规划——分析与方法[M].上海：上海科学技术出版社，1979[8]戴彧虹、袁亚湘著.非线性共轭梯度法[M].上海：上海科学技术出版社，1994[9]戚厚铎、韩继业、刘光辉著.修正Hestenes—Stiefel共轭梯度算法[J].数学年刊，1996，17A（3）；177—284[10]席少霖著.约束变尺度法[J].运筹学学报，1985年01期[11]张慧生、王堂生著.约束变尺度法应用探讨[J].新疆工学院学报，1994,15（A）；249—253[12]赵凤治、尉继英著.约束最优化的计算方法[M].北京：科学出版社，1991致谢在本文的撰写过程中，胡小平老师作为我的指导老师，他治学严谨，学识渊博，视野广阔，为我营造了一种良好的学术氛围.置身其间，耳濡目染，潜移默化，使我不仅接受了全新的思想观念，树立了明确的学术目标，领会了