《最优化》课程设计题目：牛顿法与阻尼牛顿法算法分析学院: 数学与计算科学学院专业：数学与应用数学姓名学号：廖丽红 1000730105欧艳 1000730107骆宗元 1000730122沈琼赞 1000730127指导教师：李向利日期：2012年11月08日摘要本文基于阻尼牛顿法在解决无约束最优化问题中的重要性，对其原理与算法予以讨论。
论文主要是参阅大量数学分析和最优化理论方法，还有最优化方法课程以及一些学术资料，结合自己在平时学习中掌握的知识，并在指导老师的建议下，拓展叙述牛顿法和其改进方法——阻尼牛顿法的优缺点，同时针对阻尼牛顿法的基本思路和原理进行研究，其搜索方向为负梯度方向，改善了牛顿法的缺点，保证了下降方向。
关键词：无约束牛顿法下降方向阻尼牛顿法最优解AbstractThis thesis is based on the importance of the damping Newton's method to solve unconstrained optimization problems, we give the discussion about its principles and algorithms. We search a large number of mathematical analysis and optimization theory methods, optimization methods courses, as well as some academic information ,and at the same time combined with knowledge we have learning in peacetime and thanks to the instructor's advice, we also give an expanding narrative for the Newton's method and the improved method -- damping Newton method's advantages and disadvantages, and make a study of the basic ideas and principles for damping Newton method at the same time , we find that a negative gradient direction is for the search direction of the damping Newton method, this method improves the shortcomings of the Newton method which can ensure the descent direction.Keywords: unconstrained , Newton's method , descent direction , damping Newton's method ,optimal solution目录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一、引言最优化方法是近几十年形成的，它主要运用数学方法研究各种系统各种问题的优化途径及方案，为决策者提供科学决策的依据。
而无约束优化问题是最优化问题的基础，是数值计算领域中十分活跃的研究课题之一。
其中非线性无约束最优化方法在科学计算和工程分析中起着越来越重要的作用。
对于无约束优化问题min f(x) (其中x∈R n，f:R n->R是一个连续可微函数)，牛顿法则是解决最优化问题的有效方法之一。
然而牛顿法虽具有较好的局部收敛性质，但却存在有一定的局限性的，只在初始点充分接近目标函数极小点时收敛速度才相对较快，对目标函数要求严格，也不能保证下降方向。
是以，在解决非线性无约束优化问题的过程中，我们改用牛顿法的改进方法——阻尼牛顿法来解决问题。
并详细分析其过程且对结果进行讨论研究。
二、基本原理2.1、无约束问题的最优性条件无约束问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据，为此我们有以下几个定理。
定理1：设f:R n→R1在点X*∈R n处可微。
若存在p∈R n，使∇f(x*)T p < 0,则向量p是f在点X*的下降方向。
定理2：设设f:R n→R1在点X*∈R n处可微。
若X*是无约束问题的局部最优解，则∇f(x*) =0。
由上课所学知识我们知道，使∇f(x)=0的点x为函数f的平稳点。
函数f的稳定点。
函数f的一个稳定点可以是极小点，也可以是极大点，甚至两者都不是。
若是最后一种情况，则成它为函数f的鞍点。
以上定理告诉我们，X*是无约束问题的局部最优解的必要条件是：X*是目标函数f的稳定点。
现给出无约束问题局部最优解的充分条件。
定理3：设f:R n→R1在点X*∈R n处的Hesse阵∇2f((x*)存在可微。
若∇f(x*) =0，并且∇2f((x*)正定，则X*是无约束问题的严格局部最优解。
一般而言，无约束问题的目标函数的稳定点不一定是无约束问题的最优解。
但对于其目标函数是凸函数的无约束凸规划，下面定理证明了，它的目标函数的稳定点就是它的整体最优解。
定理4：设f:R n→R1，X*∈R n，f是R n上的可微凸函数。
若有∇f(x*) =0，则X*无约束问题的整体最优解。
2.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)]T H(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)不是近似而是完全相同的二次式，赫森矩阵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)]= min f[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)∈R n，迭代精度ε，维数n。
(2)置0 =>k。
(3)计算迭代点 X(k)的梯度▽f(X(k))和梯度的模|| ▽f(X(k))||。
(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)]= min f[X(k)+αS(k)]。
(7)计算迭代新点X(k+1）=X(k)+α(k)S(k)。
(8)置k+1=> k，返回步骤(3)进行下一次迭代计算。
三、阻尼牛顿法与牛顿法的比较3.1.牛顿法：牛顿法又称为牛顿-拉弗森方法（Newton-Raphson method），它是一种在实数域和复数域上近似求解方程的方法,是求解无约束最优化问题最古老的算法之一。
若用牛顿法求某二次目标函数的最优解，则构造的逼近函数与原始目标函数是完全相同的二次式，其等值线完全重合，故从任一点出发，一定可以一次达到目标函数的极小点。