理论部分 收敛性分析
理论部分 收敛性分析
无约束最优化算法的一般迭代格式 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)
