Wolfe準(zhǔn)則

Wolfe 準(zhǔn)則是指: 給定ρ∈(0,0.5),σ∈(ρ,1),求αk使得下面兩個(gè)不等式同時(shí)成立:

f(xk+αkdk)≤f(xk)+ραkgTkdk▽f(xk+αkdk)Tdk≥σgTkdk(1)(2)
式中： gk=g(xk)=▽f(xk).

式（2）有時(shí)也用另一個(gè)更強(qiáng)的條件

∥∥▽f(xk+αkdk)Tdk∥∥≤?σgTkdk(3)
來(lái)代替. 這樣, 當(dāng) σ>0充分小時(shí)，可保證式（3)變成近似精確線性搜索。條件（1）和條件（3）也稱(chēng)為強(qiáng) Wolfe準(zhǔn)則。

強(qiáng)Wolfe 準(zhǔn)則表明, 由該準(zhǔn)則得到的新的迭代點(diǎn)xk+1=xk+αkdk在xk的某一鄰域內(nèi)且使目標(biāo)函數(shù)值有一定的下降量.

由于gTkdk<0,可以證明Wolfe 準(zhǔn)則的有限終止性, 即步長(zhǎng)αk的存在性. 我們有下面的定理.

設(shè)f(x) 有下界且gTkdk<0, 令ρ∈(0,0.5),σ∈(ρ,1). 則存在一個(gè)區(qū)間[a,b](0<a<b) 均滿足(1) 和(3).

Armijo 準(zhǔn)則

Armijo 準(zhǔn)則是指: 給定β∈(0,1),σ∈(0,0.5). 令步長(zhǎng)因子αk=βmk,其中mk是滿足下列不等式的最小非負(fù)整數(shù):

f(xk+βmdk)≤f(xk)+σβmgTkdk(4)
可以證明, 若 f(x)是連續(xù)可微的且滿足 gTkdk<0, 則 Armijo 準(zhǔn)則是有限終止的, 即存在正數(shù) σ, 使得對(duì)于充分大的正整數(shù) m, (4) 式成立.

為了程序?qū)崿F(xiàn)的方便, 我們將Armijo 準(zhǔn)則寫(xiě)成下列詳細(xì)的算法步驟.

算法4（Armijo準(zhǔn)則）

步0 給定β∈(0,1), σ∈(0,0.5). 令 m=0.

步1 若不等式

f(xk+βmdk)≤f(xk)+σβmgTkdk
成立, 置 mk=m,xk+1=xk+βmkdk 停算. 否則, 轉(zhuǎn)步2.

步2 令m=m+1, 轉(zhuǎn)步1.

下面給出Armijo 準(zhǔn)則的Matlab 程序

MATLAB程序

Armijo 搜索規(guī)則是許多非線性優(yōu)化算法都必須執(zhí)行的步驟, 把它編制成可重復(fù)利用的程序模塊是很有意義的.

amj.m

function [mk,newxk,newfk]=amj(xk,dk,beta,sigma) %%Armijo 搜索規(guī)則 %input:xk,dk; % beta,sigma %output:mk,xk+1,f(xk+1)m=0;maxm=20; while(m<=maxm)if(fun(xk+beta^m*dk)<=fun(xk)+sigma*beta^m*gfun(xk)'*dk)mk=m;break;endm=m+1; end; alpha=beta^mk; newxk=xk+alpha*dk; fk=fun(xk); newfk=fun(newxk); %fun為輸入函數(shù)，gfun為對(duì)應(yīng)梯度函數(shù)，均在別處定義

fum.m

function f = fun(x) f=100*(x(1)^2-x(2))^2+(x(1)-1)^2;

gfun.m

function gf =gfun(x) gf=[400*x(1)*(x(1)^2-x(2))+2*(x(1)-1);-200*(x(1)^2-x(2))];

實(shí)驗(yàn)結(jié)果

>> xk=[-1,1]'; >> dk=[1,-2]'; >> beta=0.5; >> sigma=0.2; >> [mk,newxk,newfk]=amj(xk,dk,beta,sigma) mk =2 newxk =-0.750.5 newfk =3.453125

總結(jié)

以上是生活随笔為你收集整理的非精确线搜索的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。