《最优化方法》课程教学资源（PPT课件）第四章 无约束最优化方法（刘二永）

第四章 无约束最优化方法

第四章 无约束最优化方法

§4.1最速下降法

§ 4.1 最速下降法

问题提出 问题在点x处沿什么方向d2(x)下降最快? 分析:/(x2+ad)=(x)+gd+0(a4a>0) 考查:gdk= ged cos 显然当cos9=-1时,g4d4取极小值 因此 gk 结论负梯度方向使f(x)下降最快亦即最速 下降方向

问题提出 问题：在点 k x 处，沿什么方向 , k d f (x) 下降最快? 分析： ( + ) = ( )+ + ( )(  0) k k T k k k k f x d f x g d o d 考查： k k k cos T k g d = g d 显然当 cos = −1 时， k T k g d 取极小值． 因此： k k d = −g 结论：负梯度方向使 f (x) 下降最快，亦即最速 下降方向．

最速下降法算法 Step1:给出x∈R",O≤E<<1,k:=0 step2:计算v(x),如果V(xk)川≤e,停 Step3:计算下降方向dk=-gk Sep4:计算步长因子ak step5:令xk1=xk+adk,转步2

最速下降法算法 Step1: 给出 x0 R ,0  1, k := 0 n  Step2: 计算 ( ), k f x 如果  ( )   , k f x 停． Step3: 计算下降方向 . dk = −gk Step4: 计算步长因子 .  k Step5: 令 , k 1 k k dk x + = x + 转步２

分析设f(x)=xGx+b7x+c是正定二次函数, 由精确的线搜索确定的∝=? dk Gd 特别当:dk=-gA sk6k

分析：设 f (x) x Gx b x c T T = + + 2 1 是正定二次函数, 由精确的线搜索确定的 = ? k k T k k T k k d Gd g d  = − 特别当： dk = −gk k T k k T k k g Gg g g  =

例1:用最速下降法求解 m/(x)=1x2+9x2 (9,1) 解 G(x)= x=(00) 9 09 =(9,1)go=Vf(x0)=(9,9) 7.2 080 0 0.8 7.2 0 0 2 9×0.8 g1(-1)2×0

例1：用最速下降法求解： ( ) ( ) T f x x x x 9,1 2 9 2 1 min 0 2 2 2 = 1 + = 解： ( ) ( ) ( ) T G x x x x g x 0,0 0 9 1 0 9 * 2 1 =         =         = ( ) ( ) ( ) T T x0 = 9,1 g0 = f x0 = 9,9         − = − = 0.8 7.2 0 0 0 0 0 1 0 g g Gg g g x x T T         − = 7.2 7.2 g1 ( )         −   = − = 2 2 2 1 1 1 1 1 2 1 1 0.8 9 0.8 g g Gg g g x x T T

((-1)y O.8),k 分析(1)lm lim k+1 0.8 k 因此:最速下降法是整体收敛的, 且是线性收敛的 (2)两个相邻的搜索方向是正交的 (9,9)d1=-(7.2,-7.2)dba1=0

( ) (0.8) , 1,2, 1 9 =         − x = k k k k 分析：(1) lim lim 0.8 1 * * 1 = = − − + → + → k k k k k k x x x x x x 因此：最速下降法是整体收敛的， 且是线性收敛的． (2) 两个相邻的搜索方向是正交的． d0 = −(9,9) d1 = −(7.2,−7.2) d0 d1 = 0 T T T

0 十大 0000 86420246 5

收敛性分析 定理1:设v(x)在L={x∈R(x)≤f(xo) 上存在且一致连续,则最速下降法产生的序列 满足或者对某个k有gk=0,或者f(x)→>-∞, Sk->0. 证明:对于最速下降法=0由以上定理立得

收敛性分析 定理1: 设 f (x) 在 L x R f (x) f (x0 ) n =   上存在且一致连续，则最速下降法产生的序列 满足或者对某个 k 有 = 0, gk 或者 ( )→ −, xk f → 0. gk 证明：对于最速下降法， = 0,  k 由以上定理立得．

收敛性分析 定理2:设/(x)二次连续可微且|y2(x米≤M, 其中M是个正常数,对任何给定的初始点x0, 最速下降算法或有限终止,或者lmnf(xk)=-∞, 或者ingk=0. 证明:用以上的结论 f(xk)-f(xk+)≥‖ 2M

收敛性分析 定理2: 设 f (x) 二次连续可微，且 ( ) ,  2 f x  M 其中 M 是个正常数，对任何给定的初始点 , x0 最速下降算法或有限终止，或者 lim ( ) = −, → k k f x 或者 lim = 0. → k k g 证明：用以上的结论： ( ) ( ) 2 1 2 1 k k gk M f x − f x + 