第四章 无约束非线性问题的解法 本章要点： >最速下降法的基本思想及特点 min f(x) x∈R” >牛顿方向 >Newton法基本思想及特点 >共轭方向、共轭方向法的基本定理 >共轭梯度法基本思想 >拟Newton法的基本思想
本章要点： ➢最速下降法的基本思想及特点 ➢牛顿方向 ➢Newton法基本思想及特点 ➢共轭方向、共轭方向法的基本定理 ➢共轭梯度法基本思想 ➢拟Newton法的基本思想 第四章 无约束非线性问题的解法 min ( ) n x R f x
学习的重要性： 1、直接用于无约束的实标问题； 2、其基本思想和逻辑结构可以推广到约束问题： 3、约束问题可以转化成无约束问题求解。 方法分类： 1、间接法：对简单问题，求解必要条件或充分条件； 零阶法：只需计算函数值x) 直接法 2、迭代算法： 一阶法：需计算Vfx) 梯度法 二阶法：需计算V2x)
学习的重要性： 1、直接用于无约束的实际问题； 2、其基本思想和逻辑结构可以推广到约束问题； 3、约束问题可以转化成无约束问题求解。 方法分类： 1、间接法：对简单问题，求解必要条件或充分条件； 2、迭代算法： 零阶法：只需计算函数值f(x) 一阶法：需计算▽f(x) 二阶法：需计算▽2 f(x) 直接法 梯度法
考虑无约束优化问题： min f(x) xERT 本章主要介绍无约束最优化方法，它的应用比较广泛，理论比较 成熟。另一方面，通常可以把一些约束优化问题转化为无约束问题来 处理，所以它是最优化方法中的基本方法。 这些方法通常要用到函数的一阶或二阶导数。 在实际问题中，也常遇到函数的解析表达式比较复杂，有的甚至 写不出明显的解析表达式，因而导数很难求出或无法求出，这时基于 梯度的方法不能用，需要采取另一种所谓的直接法（或直接搜索法）。 直接法是仅仅利用函数值的信息，去寻找最优解的一类方法。在后面 第九章有介绍
本章主要介绍无约束最优化方法，它的应用比较广泛，理论比较 成熟。另一方面，通常可以把一些约束优化问题转化为无约束问题来 处理，所以它是最优化方法中的基本方法。 这些方法通常要用到函数的一阶或二阶导数。 在实际问题中，也常遇到函数的解析表达式比较复杂，有的甚至 写不出明显的解析表达式，因而导数很难求出或无法求出，这时基于 梯度的方法不能用，需要采取另一种所谓的直接法（或直接搜索法）。 直接法是仅仅利用函数值的信息，去寻找最优解的一类方法。在后面 第九章有介绍。 考虑无约束优化问题： min ( ) n x R f x
直接搜索法收敛速度一般比较慢，需要计算大量的函数值。 梯度反映了函数值变化的规律，充分利用梯度信息构造算法， 能加速收敛。 使用函数的梯度（一阶导数）或Hesse矩阵 （二阶导数）的 优化算法统称为梯度法。 算法目标：求出平稳点（满足又fx)=O的x*)。 由于Vfx)=0一般是非线性方程组，解析法往往行不通 所以梯度法通常是逐次逼近的迭代法。 假定：7fx)和72fx)连续存在
直接搜索法收敛速度一般比较慢，需要计算大量的函数值。 梯度反映了函数值变化的规律，充分利用梯度信息构造算法， 能加速收敛。 使用函数的梯度（一阶导数）或Hesse矩阵（二阶导数）的 优化算法统称为梯度法。 算法目标：求出平稳点 （满足f(x)=0的x * ）。 由于 f(x)=0 一般是非线性方程组，解析法往往行不通， 所以梯度法通常是逐次逼近的迭代法。 假定： f(x)和 2 f(x)连续存在
§4.1最速下降法(Cauchy法) 1847年Cauchy提出。特点是直观易懂，但收敛速度慢。 (一)基本思想 多变量最优化迭代解法的一般迭代公式： xk+I)=x+以 关键是如何确定搜索方向d 可用一维搜索技术解决 瞎子下山：由于他看不到哪里 dk+)=一Vfxk+) 是山谷，不可能沿直接指向山 ? 谷的路线走，他只能在当前位 置上，靠手杖作局部探索，哪 里最陡就往哪里前进一步，然 后在新的位置上再用手杖寻找 d(k)=-Vf(x (k) 最陡方向，再下降一步。这就 是最速下降法的形象比喻。 最速下降法迭代公式xk+=xW一t7f(x)
§4.1 最速下降法(Cauchy法) （一）基本思想 x (k+1) = x(k) + tk d (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) －tk f(x(k) ) 1847年Cauchy提出。特点是直观易懂，但收敛速度慢
下面看一下理论推导： 设函数fx)在x*附近连续可微，且gk=Vfxk)0,由Taylor展式 f(x)=f(x")+(x-x*)"Vf(x")+o(x-x*) 可知，若记x-xk=tdk,则满足(dk)Tgk<0的方向dk是下降方向。当t取定后， (dk)Tgk的值越小，即-(dk)Tgk的值越大，函数下降的越快。由Cauchy Schwartz不等式 (d)'g之-dlg‖ 当且仅当dk=-gk时，(d)Tgk最小，从而-gk是最速下降方向。 最速下降法的迭代格式为： x(kD)=x()-tVf(x(k)
下面看一下理论推导： 设函数f(x)在x k附近连续可微，且gk= f(xk ) ≠0，由Taylor展式 ( ) ( ) ( ) ( ) ( ) k k T k k f x f x x x f x o x x = + − + − 可知，若记x-x k=tdk，则满足(dk ) Tgk<0的方向dk是下降方向。当t取定后， (dk ) Tgk的值越小，即- (dk ) Tgk的值越大，函数下降的越快。由CauchySchwartz不等式 当且仅当d k=-g k时，(dk ) Tg k 最小，从而-g k是最速下降方向。 ( ) T k k k k d g d g − 最速下降法的迭代格式为： ( 1) ( ) ( ) ( ) k k k k x x t f x + = −
(二)算法 开始 给定x0),M,81,82,令k=0 计算Vfx) ↓ I7fx4)川≤e1 是 x"=x(k) 结束 否到 是 否副 维搜索求t ←ts=argmin f(x-g) 精度为2 t>0 x&+)=x因一t7fx因) k=k+1
（二）算法 开始 给定x (0) , M , 1 , 2 , 令 k=0 计算f( x(k ) ) ||f( x(k ) )|| M x * =x 是 (k) 结束 是 一维搜索求tk 精度为 2 否 x (k+1) = x(k) －tk f(x(k) ) k=k+1 k k k t t f x tg 0 argmin ( ) = −
(三)最速下降法的搜索路径呈直角锯齿形 引理4.1设从点x)出发，沿方向dk作精确一维搜索，t为最优步长因子，即 f(x()+tg dk)min f(x()+t dk) >0 则成立Vf(x+tkd)Tdk=0,即新点处的梯度与前搜索方向垂直。 即 7f(x+)⊥Vf(x) Vf(x (k+1) d(k) fx)等值面 x(k+1) dk+1)
（三）最速下降法的搜索路径呈直角锯齿形 引理4.1 设从点x (k) 出发，沿方向d k作精确一维搜索，tk为最优步长因子，即 f(x(k) + tk d k ) = min f( x(k) + t dk ) 则成立 f(x(k) + tk d k ) T d k =0, 即新点处的梯度与前搜索方向垂直。 即 t>0 ( 1) ( ) ( ) ( ) k k f x f x + ⊥ x (k+1) d (k) x (k) f(x)等值面 f(x (k+1) ) tk d (k+1)
二维情形下最速下降法搜索路径： X(2 X(0 由此可以看出，最速下降法仅是算法的局部性质。对于许多问题，全 局看最速下降法并非“最速下降”，而是下降的较缓慢。数值试验表明， 当目标函数的等值线接近于一个圆（球）时，最速下降法下降较快，而当 目标函数的等值线是一个扁长的椭球时，最速下降法开始几步下降较快， 后来由于出现“锯齿”现象，下降就比较缓慢
二维情形下最速下降法搜索路径： 由此可以看出，最速下降法仅是算法的局部性质。对于许多问题，全 局看最速下降法并非“最速下降”，而是下降的较缓慢。数值试验表明， 当目标函数的等值线接近于一个圆（球）时，最速下降法下降较快，而当 目标函数的等值线是一个扁长的椭球时，最速下降法开始几步下降较快， 后来由于出现“锯齿”现象，下降就比较缓慢。 x (0) x (1) x (2)
其原因就是精确一维搜索（最优步长）满足 Vf(x(k+D))T dk=0, 即 Vf(x(k+D))T Vf(x(k))=dk+Tdk=0, 这表明在相邻的两个迭代点上函数x)的两个梯度方向是互相直交的，即， 两个搜索方向互相直交，这就产生了锯齿形状。当接近极小点时，步长愈 小，前进愈慢。 这就造成了最优步长的最速下降法逼近极小点过程是“之”字形，并且越 靠近极小点步长越小，移动越慢，以至在实际运用中在可行的计算时间内 得不到需要的结果。 这似乎与“最速下降”的名称矛盾。其实不然，因为梯度是函数局部性质， 从局部看，函数在这一点附近下降的很快，然而从整体看，则走过了许多 弯路，因此反而是不好的
f(x(k+1)) T dk =0， 即 f(x(k+1)) T f(x(k)) =dk+1 Tdk =0， 这表明在相邻的两个迭代点上函数f(x)的两个梯度方向是互相直交的，即， 两个搜索方向互相直交，这就产生了锯齿形状。当接近极小点时，步长愈 小，前进愈慢。 这就造成了最优步长的最速下降法逼近极小点过程是“之”字形，并且越 靠近极小点步长越小，移动越慢，以至在实际运用中在可行的计算时间内 得不到需要的结果。 这似乎与“最速下降”的名称矛盾。其实不然，因为梯度是函数局部性质， 从局部看，函数在这一点附近下降的很快，然而从整体看，则走过了许多 弯路，因此反而是不好的。 其原因就是精确一维搜索（最优步长）满足