本章要点:最速下降法的基本思想及特点牛顿方向Newton法基本思想及特点共轭方向、共轭方向法的基本定理共轭梯度法基本思想拟Newton法的基本思想

第四章无约束非线性问题的解法学习的重要性:1、直接用于无约束的实际问题;2、其基本思想和逻辑结构可以推广到约束问题;3、约束问题可以转化成无约束问题求解.
方法分类:1、间接法:对简单问题,求解必要条件或充分条件;2、迭代算法:零阶法:只需计算函数值f(x)一阶法:需计算f(x)二阶法:需计算2f(x)直接法梯度法本章主要介绍无约束最优化方法,它的应用比较广泛,理论比较成熟.
另一方面,通常可以把一些约束优化问题转化为无约束问题来处理,所以它是最优化方法中的基本方法.
这些方法通常要用到函数的一阶或二阶导数.
在实际问题中,也常遇到函数的解析表达式比较复杂,有的甚至写不出明显的解析表达式,因而导数很难求出或无法求出,这时基于梯度的方法不能用,需要采取另一种所谓的直接法(或直接搜索法).
直接法是仅仅利用函数值的信息,去寻找最优解的一类方法.
在后面第九章有介绍.

考虑无约束优化问题:直接搜索法收敛速度一般比较慢,需要计算大量的函数值.
梯度反映了函数值变化的规律,充分利用梯度信息构造算法,能加速收敛.
使用函数的梯度(一阶导数)或Hesse矩阵(二阶导数)的优化算法统称为梯度法.
算法目标:求出平稳点(满足f(x)=0的x*).
由于f(x)=0一般是非线性方程组,解析法往往行不通,所以梯度法通常是逐次逼近的迭代法.
假定:f(x)和2f(x)连续存在§4.
1最速下降法(Cauchy法)(一)基本思想x(k+1)=x(k)+tkd(k)x(k)x*d(k)=-f(x(k))x(k+1)d(k+1)=-f(x(k+1))瞎子下山:由于他看不到哪里是山谷,不可能沿直接指向山谷的路线走,他只能在当前位置上,靠手杖作局部探索,哪里最陡就往哪里前进一步,然后在新的位置上再用手杖寻找最陡方向,再下降一步.
这就是最速下降法的形象比喻.

多变量最优化迭代解法的一般迭代公式:可用一维搜索技术解决关键是如何确定搜索方向d(k)最速下降法迭代公式x(k+1)=x(k)-tkf(x(k))1847年Cauchy提出.
特点是直观易懂,但收敛速度慢.
下面看一下理论推导:设函数f(x)在xk附近连续可微,且gk=f(xk)≠0,由Taylor展式可知,若记x-xk=tdk,则满足(dk)TgkMx*=x(k)是结束是一维搜索求tk精度为2否x(k+1)=x(k)-tkf(x(k))k=k+1(三)最速下降法的搜索路径呈直角锯齿形定理4.
1设从点x(k)出发,沿方向d作精确一维搜索,tk为最优步长因子,即f(x(k)+tkdk)=minf(x(k)+tdk)则成立f(x(k)+tkd)Td=0,即新点处的梯度与搜索方向垂直.
即t>0x(k+1)d(k)x(k)f(x)等值面f(x(k+1))tkd(k+1)二维情形下最速下降法搜索路径:由此可以看出,最速下降法仅是算法的局部性质.
对于许多问题,全局看最速下降法并非"最速下降",而是下降的较缓慢.
数值试验表明,当目标函数的等值线接近于一个圆(球)时,最速下降法下降较快,而当目标函数的等值线是一个扁长的椭球时,最速下降法开始几步下降较快,后来由于出现"锯齿"现象,下降就比较缓慢.