西安交通大学：《工程优化方法及其应用》研究生课程教学课件（PPT讲稿）04-05 无约束规划方法

无约束规划方法迭代法的基本步骤下降算法类拟牛顿算法共轭方向算法类1/68

1/68 无约束规划方法 ◼ 迭代法的基本步骤 ◼ 下降算法类 ◼ 拟牛顿算法 ◼ 共轭方向算法类

一、迭代法的基本结构给定初始估计x,第k次迭代的基本结构为：p,（1）确定一个搜索方向(2）不确定步长αk使得维搜索问题f(xk +αph)<f(xk)(3) 置 x+1 =x* +αpk采用不同方法构造p和不同方法寻找α就对应不同算法。2/68

2/68 一、迭代法的基本结构 采用不同方法构造 和不同方法寻找 就对应不同算法。  k k p k k k 1 k x x p  + （3）置 = + 给定初始估计 第k次迭代的基本结构为： 1 x , , k （1）确定一个搜索方向 p （2）确定步长 使得 ( ) ( ) k k k k f x p f x +    k 一维搜索问题

（梯度法）二、最速下降法函数值增加最快的方向迭代公式：Vf(xk)xk+1 = xk +αkp如何选择下降方向？下降方向1、最速下降法（梯度法）-Vf(xk函数值下降最快的方向 搜索方向 dk=-Vf(x)(②)搜索步长：α取最优步长,即满足f(x* +αrp*)= min f(xk +α p) 。3/68

3/68 迭代公式： k k k k x = x + p +1 如何选择下降方向？ 函数值下降最快的方向 函数值增加最快的方向 下降方向 ( ) k f x ( ) k − f x k x 二、最速下降法（梯度法） 1、最速下降法（梯度法） 1 ( ) k k （）搜索方向 d = −f x 。 （）搜索步长 取最优步长 即满足 ( ) min ( ) 2 : , k k k k k k f x  p f x  p   + = +

2、最速下降法算法步骤给定初始点x'ER",允许误差ε>0,令k=1(②)计算搜索方向 p=-V f(x);(3)若LpkⅡ≤ε,则停止计算,x为所求极值点;否则，求最优步长α，使得f(x* +αrp*) = min f(x* +α p*)。Q() 令 xk+1 = xk +αpk,令k:= k+1,转2。4/68

4/68 （1）给定初始点 x 1  R n ,允许误差  0, 令k = 1。 2 ( ); k k （）计算搜索方向 p = − f x 否则，求最优步长 ，使得 （）若 则停止计算， 为所求极值点； k k k p x  3 || ||  , f (x k k p k ) min f (x k  p k )。  + = + （4）令 x k+1 = x k +k p k ,令k := k + 1,转2。 2、最速下降法算法步骤

例1 用最速下降法求解：min f(x)=x +3x2初始 x'=(2,1),求迭代一次后的选代点 x2。解: ： Vf(x)=(2x1,6x2)T. p'=-Vf(x)=(-4,-6).:: xl +αp'=(2-4α,1-6α).令 (α)= f(x' +αp)=(2-4α) +3(1-6α),求解min p(α)132令 (α) = -8(2 - 4α)-36(1-6α)= 0 =→αi62(36,-8) x = x' +αp =(31'31)5/68

5/68 2 2 1 2 1 : min ( ) 3 , (2,1) , T f x x x x = + = 用最速下降法求解 初始 求迭代一次后的迭代点 x 2 。 解： ( ) ( 2 ,6 ) , 1 2 T  f x = x x 1 1 ( ) ( 4, 6) . T  = − = − − p f x 1 1 (2 4 ,1 6 ) . T  + = − − x p    1 1 2 2 令      ( ) ( ) (2 4 ) 3(1 6 ) = + = − + − f x p ， 求解 min ( )    令     '( ) 8(2 4 ) 36(1 6 ) 0 = − − − − = 1 13 62  =  例１ T 2 1 1 1 36 8 , . 31 31 x x p    − = + =   

3、最速下降法的总体收敛性定理设f eC，在最速下降法中采用精确一维定理1讠则产生的迭代点列x搜索或不精确一维搜索的每一个聚点是驻点。定理2 设f eC，且2f(x)≤M.对任何给定的的初始值x和ε>0,采用精确一维搜索最速下降法或者有限终止，或lim f(x）=-0,或limVf(x)=0k-→>00k→80遗感的是最速下降法的整体收敛性并不能保证它是一个有效的方法。6/68

6/68 3、最速下降法的总体收敛性定理 的每一个聚点是驻点。 搜索或不精确一维搜索，则产生的迭代点列 设 ，在最速下降法中采用精确一维 { } 1 k x 定理1 f C 定理2 lim ( ) , lim ( ) 0 0, ( ) . 0 2 2 = −  =     → → k k k k f x f x x f C f x M 或者有限终止，或 或 的初始值 和 采用精确一维搜索最速下降法 设 ， 且 对任何给定的  遗憾的是最速下降法的整体收敛性并不能保 证它是一个有效的方法

4、最速下降法的性质性质．设f(x)有一阶连续偏导数，若步长 α,满足f(x* +αup) = min f(x* +αp*)2则有 Vf(x*+αp)’ p = 0 。证明:令 (α)= f(x+αp"),则 β'(α)=Vf(x* +αp*) pk.: f(x* +αrp*)=min f(x* +αp*)a.. p'(α)=Vf(xk +αrph)T pk =0 .注:因为梯度法的搜索方向 pk+1=-Vf(x +αμp"),所以(p*+1) p* = 0= p*+I p* 。7/68

7/68 ( ) min ( ) k k k k k f x  p f x  p  + = + 则有 f (x k +k p k ) T p k = 0。 性质. 证明：令 () = f (x k + p k )， ( ) ( ) . k k T k 则   = f x + p p ( ) min ( ) k k k k k f x  p f x  p   + = +  ( ) =  ( + ) = 0 . k T k k k  k f x  p p 设 f (x) 有一阶连续偏导数，若步 长 k 满 足 注： ( p k+1 ) T p k = 0  p k+1 ⊥ p k 。 因为梯度法的搜索方向 p k+1 = − f (x k +k p k )，所以 4、最速下降法的性质

最速下降法的锯齿现象+数值实验表明，当目标函数的等值线接近于一个圆（球）时，最速下降法下降较快，而当目标函数的等值线接近于一个扁长的椭球时，最速下降法开始几步下降较快，后来就出现锯齿现象，下降十分缓慢，8/68

8/68 1 x * x 2 x 3 x  最速下降法的锯齿现象 数值实验表明，当目标函数的等值线接近于一个 圆（球）时，最速下降法下降较快，而当目标函 数的等值线接近于一个扁长的椭球时，最速下降 法开始几步下降较快，后来就出现锯齿现象，下 降十分缓慢

三、Newton法minf(x)问题：XER"s.t.选代公式：x+1=x+αpf(xk +αrph)< f(x*)要求1.Newton法的基本思想：利用f(x）在xk处的二阶Taylor展开式的极小值点作为xk+19/68

9/68 三、Newton 法 利用 f(x) 在x k处的二阶Taylor展开式的 极小值点作为x k+1 1. Newton法的基本思想： n s t x R f x . .  min ( ) k k k 1 k x x p  + 迭代公式： = + ( ) ( ) k k k k f x p f x +   问题： 要求

将f(x)在x*处二阶Taylor展开f(x) ~ Q(x)= f(x)+Vf(xk) (x -x*)++;(x-x*)v"f(x")(x-x*)记 gk=Vf(xh),G,=V"f(x*)。则 Q(x)= f(x*)+gl (x-x*)+=(x-xh)'G(x-xh)令 VQ(x)=gk +G;(x-x)=0若Hesse矩阵G,正定，即G,>0，则G=l>0，此时有k+1 = xk - GrgkXNewton迭代公式10/68

10/68 ( ) ( )( ) 21 ( ) ( ) ( ) ( ) ( ) k T 2 k k k k T k x x f x x x f x Q x f x f x x x + −  −  = +  − + ( ) ( ) 21 ( ) ( ) ( ) k k T k k T k k 则 Q x = f x + g  x − x + x − x G x − x 记 gk = f (xk ) ,Gk = 2 f (xk )。  ( ) = + ( − ) = 0 k k k Q x g G x x 将f (x)在xk处二阶Taylor展 开 令 若Hesse矩阵Gk正定，即Gk  0，则Gk−1  0，此时有 k k k k x x G g +1 −1 = − Newton迭代公式