《最优化方法》课程教学资源（PPT课件）收敛性分析（刘二永）

理论部分 收敛性分析

理论部分 收敛性分析

无约束最优化算法的一般迭代格式 Step1:给出xo∈R",0≤E<<1,k:=0 step2:计算v/(x),如果Ⅳv(xk)≤a,停 step3:计算下降方向d step4:计算步长因子ak step5:令x1=xk+adk,转步2

无约束最优化算法的一般迭代格式 Step1: 给出 x0 R ,0  1, k := 0 n  Step2: 计算 ( ), k f x 如果  ( )   , k f x 停． Step3: 计算下降方向 . dk Step4: 计算步长因子 .  k Step5: 令 , k 1 k k dk x + = x + 转步２

精确线搜索方法的收敛性 设=(4k,-gk)表示向量d与-gk之间 的夹角,即:cos=- d klik k△k 定理1设4是下降方向&k是精确线搜索的 步长因子若存在常数M>0,使得对所有 a>0,|y2/(x+ak)≤M,Yk,则 f(xk)-f(+adk22Mskll cos Ow

精确线搜索方法的收敛性 设 k = dk −gk  , 表示向量 dk 与− gk 之间 的夹角，即： k k k T k k d g d g cos = − 定理1 设 dk 是下降方向，  k 是精确线搜索的 步长因子，若存在常数 M  0, 使得对所有 0, ( ) , , 2 f x d M k    k + k   则： ( ) ( ) cos . 2 1 2 k k k k gk k M f x − f x + d  

证:由假设可知对任意a>0有 (xk +adk)=f(x)+agk dk +a2dkvf(xk+adk dk, 0<0<1) f(xk)+agk dk +aDell 令:a kk M 由于α是精确线搜索步长,故有 f(x)-f(x+a44)≥/(x)-/(x+a)

证：由假设可知对任意   0 有： ( ) ( ) ( ) ,(0 1) 2 1 2 2 +  +   + = +      k k k T k k T k k k k d f x d d f x d f x g d ( ) 2 2 2 1 k k T  f xk +gk d +  M d 令： 2 k k T k M d g d  = − 由于  k 是精确线搜索步长，故有： ( ) ( ) ( ) ( ) k k k k k k dk f x − f x + d  f x − f x +

/(k-s(k+andk)2f(x)-(g+adk >-agkk Mlld k 2 Mdk kwk 2M lgkfldkI COS 2M

( ) ( ) ( ) ( ) k k k k k k dk f x − f x + d  f x − f x + 2 2 2 1 k k T  −gk d −  M d ( ) 2 2 2 1 k k T k M d g d = ( ) 2 2 2 2 2 1 k k k T k k g d g d g M = gk k M  2 2 cos 2 1 =

精确线搜索方法的收敛性 定理2设梯度g(x)在L={x∈R"/(x)≤f(x) 上存在且一致连续,采用精确线搜索算法 产生的方向dk与gk的夹角满足 n≤x-,对某个x>0 则或者对某个有限的k有gA=0,或者 f(xk)→>-∞,或者 8k->0

精确线搜索方法的收敛性 定理2 设梯度 g(x) 在 L x R f (x) f (x0 ) n =   上存在且一致连续，采用精确线搜索算法 产生的方向 dk 与− gk 的夹角  k 满足： , 2    k  − 对某个   0 则或者对某个有限的 k 有 = 0, gk 或者 ( )→ −, k f x 或者 → 0. gk

证:假定对所有的k,gk≠0,f(x)下有界 由于{(x)单调下降故极限存在,因而 f(xk)-f(x1)>0( 反证法:假定g4→>0不成立,则存在常数E>0 和一个子序列使得gk≥E,从而 k wk Igkcos 0k 28sin u==E,(2) k X: f(+adk)=f(x)+ag(sk)dk

证：假定对所有的 ( ) k k k , g  0, f x 下有界． 由于 f (xk ) 单调下降，故极限存在，因而： ( ) ( ) 0 (1) f xk − f xk+1 → 反证法：假定 gk → 0 不成立，则存在常数   0 和一个子序列使得   , gk 从而： cos sin (2) 1      − = k k  == k k T k g d g d 又： ( ) ( ) ( ) k T f xk +dk = f xk +g k d

f(x+adk)=f(xx+ag(ek)d f()+aged+alg(sk)-gITd ≤f(x)+a|lk+|g(5)-k(3) 其中在x kxk+ad k之间 由于g在水平集L上一致连续故存在a 使得当0≤a|dlA‖≤时 4

( ) ( ) ( ) k T f xk +dk = f xk +g k d ( )  ( )  k T k k k T = f xk +gk d + g  − g d ( ) ( ) (3)          + + k − k k k T k k k g g d g d f x  d  其中  k 在 k x 与 k dk x + 之间． 由于 g 在水平集 L 上一致连续，故存在  使得当 0  dk  时： ( ) (4) 2 1 1  −   g k gk

依次利用(2),(3,和(4)得 k t c.h (A)+a/ kdg,1 +- k ≤f(xk)-a1 从而由精确线搜索可得 k+1 ≤fxk+ (x2)1 ala 这与(1)矛盾,从而有gk→>0

依次利用(2),(3),和(4)得： ( )          + +         + 1 2 1    k k T k k k k k d g d f x d d f x ( ) 1 2 1  −  k f x 从而由精确线搜索可得： ( ) ( ) 1 1 2 1   −          +  + k k k k k f x d d f x f x 这与(1)矛盾，从而有 → 0. gk

不精确线搜索方法的收敛性 设O=(k,-g表示向量d与-gk之间 的夹角,即cosO k△k k k 定理3设函数f(x)连续可微,梯度g(x)满足 Lipschitz连续条件 g()-g(=)≤M|ly

不精确线搜索方法的收敛性 设 k = dk −gk  , 表示向量 dk 与− gk 之间 的夹角，即： k k k T k k d g d g cos = − 定理3 设函数 f (x) 连续可微，梯度 g(x) 满足 Lipschitz连续条件： g(y)− g(z)  M y − z , (5)