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