最优化课程设计

最优化课程设计《最优化》课程设计题目：牛顿法与阻尼牛顿法算法分析学院:数学与计算科学学院专业：数学与应用数学姓名学号：廖丽红1000730105欧艳1000730107骆宗元1000730122沈琼赞1000730127指导教师：李向利日期：2012年11月08日最优化课程设计1摘要本文基于阻尼牛顿法在解决无约束最优化问题中的重要性，对其原理与算法予以讨论。论文主要是参阅大量数学分析和最优化理论方法，还有最优化方法课程以及一些学术资料，结合自己在平时学习中掌握的知识，并在指导老师的建议下，拓展叙述牛顿法和其改进方法——阻尼牛顿法的优缺点，同时针对阻尼牛顿法的基本思路和原理进行研究，其搜索方向为负梯度方向，改善了牛顿法的缺点，保证了下降方向。关键词：无约束牛顿法下降方向阻尼牛顿法最优解最优化课程设计2AbstractThisthesisisbasedontheimportanceofthedampingNewton'smethodtosolveunconstrainedoptimizationproblems,wegivethediscussionaboutitsprinciplesandalgorithms.Wesearchalargenumberofmathematicalanalysisandoptimizationtheorymethods,optimizationmethodscourses,aswellassomeacademicinformation,andatthesametimecombinedwithknowledgewehavelearninginpeacetimeandthankstotheinstructor'sadvice,wealsogiveanexpandingnarrativefortheNewton'smethodandtheimprovedmethod--dampingNewtonmethod'sadvantagesanddisadvantages,andmakeastudyofthebasicideasandprinciplesfordampingNewtonmethodatthesametime,wefindthatanegativegradientdirectionisforthesearchdirectionofthedampingNewtonmethod,thismethodimprovestheshortcomingsoftheNewtonmethodwhichcanensurethedescentdirection.Keywords:unconstrained,Newton'smethod,descentdirection,dampingNewton'smethod,optimalsolution最优化课程设计3目录1．引言——————————————————————————42.基本原理2.1无约束问题的最优性条件——————————————52.2牛顿法的基本思想—————————————————62.3阻尼牛顿法的基本思想和迭代步骤——————————73.阻尼牛顿法与牛顿法的比较———————————————83.1牛顿法—————————————————————83.2阻尼牛顿法———————————————————104.算法实现———————————————————————134.1牛顿法C++程序—————————————————134.2阻尼牛顿法Matlab算法——————————————145.总结——————————————————————————155.1总结慨括————————————————————155.2具体分工及个人感言———————————————166.参考文献———————————————————————21最优化课程设计4一、引言最优化方法是近几十年形成的，它主要运用数学方法研究各种系统各种问题的优化途径及方案，为决策者提供科学决策的依据。而无约束优化问题是最优化问题的基础，是数值计算领域中十分活跃的研究课题之一。其中非线性无约束最优化方法在科学计算和工程分析中起着越来越重要的作用。对于无约束优化问题minf(x)(其中x∈Rn，f:Rn-R是一个连续可微函数)，牛顿法则是解决最优化问题的有效方法之一。然而牛顿法虽具有较好的局部收敛性质，但却存在有一定的局限性的，只在初始点充分接近目标函数极小点时收敛速度才相对较快，对目标函数要求严格，也不能保证下降方向。是以，在解决非线性无约束优化问题的过程中，我们改用牛顿法的改进方法——阻尼牛顿法来解决问题。并详细分析其过程且对结果进行讨论研究。最优化课程设计5二、基本原理2.1、无约束问题的最优性条件无约束问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据，为此我们有以下几个定理。定理1：设f:Rn→R1在点X*∈Rn处可微。若存在p∈Rn，使∇𝑓(𝑥*)𝑇p0,则向量p是f在点X*的下降方向。定理2：设设f:Rn→R1在点X*∈Rn处可微。若X*是无约束问题的局部最优解，则∇𝑓(𝑥*)=0。由上课所学知识我们知道，使∇f(x)=0的点x为函数f的平稳点。函数f的稳定点。函数f的一个稳定点可以是极小点，也可以是极大点，甚至两者都不是。若是最后一种情况，则成它为函数f的鞍点。以上定理告诉我们，X*是无约束问题的局部最优解的必要条件是：X*是目标函数f的稳定点。现给出无约束问题局部最优解的充分条件。定理3：设f:Rn→R1在点X*∈Rn处的Hesse阵∇2𝑓((𝑥*)存在可微。若∇𝑓(𝑥*)=0，并且∇2𝑓((𝑥*)正定，则X*是无约束问题的严格局部最优解。一般而言，无约束问题的目标函数的稳定点不一定是无约束问题的最优解。但对于其目标函数是凸函数的无约束凸规划，下面定理证明了，它的目标函数的稳定点就是它的整体最优解。定理4：设f:Rn→R1，X*∈Rn，f是Rn上的可微凸函数。若有∇𝑓(𝑥*)=0，则X*无约束问题的整体最优解。最优化课程设计62.2．牛顿法的基本思想牛顿法的基本原理是：原目标函数f(X)用在迭代点X(k)邻域展开的泰勒二次多项式(X)去近似的代替，再以(X)这个二次函数的极小点作为原目标函数的下一个迭代点X(k+1），这样重复迭代若干次后，使迭代点点列逐步逼近原目标函数f(X)的极小点X*。二次逼近函数(X)可写为：(X)=f(X(k）)+[▽f(X(k))]T[X-X(k)]+1/2[X-X(k)]TH(X(k))[X-X(k)]f(X)(1）式中，▽f(X(k))，H(X(k))分别为原目标函数f(X)在X(k)点的梯度和赫森矩阵。(X)的极小点可由极值存在的必要条件，令其梯度▽(X(k))=0来求得，亦即▽(X(k))=▽f(X(k))+H(X(k))-X(k)这样，H(X(k))-X(k)=-▽f(X(k))若H(X(k))为可逆矩阵，将上式等号两边左乘以[H(X(k))]-1，则得X(k)=X(k)-[H(X(k))]-1▽f(X(k))（2）将取作下一个优化迭代点X(k+1)，即可得到牛顿法的迭代公式为X(k+1）=X(k)-[H(X(k))]-1▽f(X(k))（3）由上式可知牛顿法的搜索方向为S(k)=-[H(X(k))]-1▽f(X(k))（4）这个方向称牛顿方向。由式(3)还可看到迭代公式中没有步长因子α(k)，所以牛顿法是一种定步长的搜索迭代。当目标函数f(X)是二次函数时，由于二次泰勒展开函数(X)与原目标函数f(X)不是近似而是完全相同的二次最优化课程设计7式，赫森矩阵H(X(k))是一个常数矩阵，用式(3)牛顿法从任一初始点出发，只需一步迭代即达f(X)的极小点X*，因此牛顿法也是一种具有二次收敛性的算法。对于非二次函数，若函数的二次性态较强，或迭代点已进入极小点的邻域，则其收敛速度也是很快的，这是牛顿法的主要优点。但牛顿法由于迭代公式中没有步长因子，而是定步长迭代，对于非二次型目标函数，有时会使函数值上升，即出现f(X(k+1）)f(X(k）)的情况，这表明牛顿法不能保证函数值稳定地下降，在严重的情况下甚至可能造成迭代点列的发散而导致一计算失败。2.3．阻尼牛顿法的基本思想阻尼牛顿法每次迭代方向仍与牛顿法的方向一致，即为负梯度方向S(k)，但每次迭代需沿此方向作一维搜索，求其最优步长因子α(k)。即：f[X(k)+α(k)S(k)]=minf[X(k)+αS(k)],即阻尼牛顿法的迭代公式为X(k+1）=X(k)-α(k)[H(X(k))]-1▽f(X(k))。式中α(k)又称为阻尼因子，是通过沿牛顿方向一维搜索寻优而得。当目标函数f(X*)的赫森矩阵H(X(k))处处正定时，阻尼牛顿法能保证每次迭代点的函数值均有所下降，从而保持了二次收敛的特性。迭代步骤如下：(l)给定初始点X(0)∈Rn，迭代精度ε，维数n。(2)置0=k。(3)计算迭代点X(k)的梯度▽f(X(k))和梯度的模||▽f(X(k))||。最优化课程设计8(4)检验是否满足迭代终止条件||▽f(X(k))||ε?若满足，停止迭代，输出最优解：(X(k）)=X*,f(X(k）)=f(X*)。否则进行下一步。(5)计算X(k）处的赫森矩阵H(X(k))，并求其逆矩阵[H(X(k))]-1。(6)确定牛顿方向S(k)=-[H(X(k))]-1▽f(X(k))，从X(k)点出发，沿S(k)方向进行一维搜索求最优步长，使f[X(k)+α(k)S(k)]=minf[X(k)+αS(k)]。(7)计算迭代新点X(k+1）=X(k)+α(k)S(k)。(8)置k+1=k，返回步骤(3)进行下一次迭代计算。三、阻尼牛顿法与牛顿法的比较3.1.牛顿法：牛顿法又称为牛顿-拉弗森方法（Newton-Raphsonmethod），它是一种在实数域和复数域上近似求解方程的方法,是求解无约束最优化问题最古老的算法之一。若用牛顿法求某二次目标函数的最优解，则构造的逼近函数与原始目标函数是完全相同的二次式，其等值线完全重合，故从任一点出发，一定可以一次达到目标函数的极小点。因此，牛顿法是具有二次收敛性的算法。其优点是：对于二次正定函数，迭代一次即可得到最优解，对于非二次函数，若函数二次性较强或迭代点已经进入最优点的较小领域，则收敛速度也很快。最优化课程设计9牛顿法的算法框图如图所示：例：用牛顿法求函数的极小值解：（1）取初始点=(2)计算牛顿方向=H=最优化课程设计10故=-=-=(3)极小值==故上述例子表明，牛顿法具有很好的局部收敛性质，对二次函数来说，进一步就达到优化点。但是对一般的函数来说，在一定的条件下，当初始点的选取充分接近目标函数的极小点时，有很快的收敛速度，但若初始点选取离最小点较远，就难保证收敛；牛顿法必须求一阶、二阶导数及求逆阵，这对比较复杂的目标函数来说是比较困难的。牛顿法主要存在以下两个缺点:1.对目标函数有较严格的要求。函数必须具有连续的一、二阶偏导数，赫森矩阵必须正定且非奇异。2.计算相当复杂。除需计算梯度而外，还需计算二阶偏导数矩阵和它的逆矩阵。计算量、存储量均很大，且均以维数平方比增加，维数高时这个问题更加突出。我们知道牛顿法的算法步骤迭代公式中没有步长因子，是一种定步长的搜索迭代。不能保证函数值稳定地下降，在严重的情况下甚至可能造成迭代点列的发散而导致计算失败。为了改正牛顿法的局限性，提出了阻尼牛顿法这一改进方法。3.2．阻尼牛顿法：阻尼牛顿法能保证每次迭代点的函数值均有所下降，从而保持了二次收敛的特性。最优化课程设计11阻尼牛顿法的算法框图如图所示：例：用阻尼牛顿法求目标函数的极小点和极小值，已知目标函数，设初始点=，迭代梯度精度=0.01。解：（1）目标函数的梯度为ff(2)H最优化课程设计12=(3)牛顿方向=-=-=（4）从出发经行一维搜索由X=+=，令=0化简得：解得：=1在