《最速下降法基本原理分析綜述》2000字

最速下降法基本原理分析綜述(一)無約束問題的最優(yōu)性條件本文給出了一些關(guān)于求解非限制問題的最佳解決方案的基本前提和充分條件。定理1設(shè)f:Rn→R1在點(diǎn)X∈Rn處可微，如果有P∈Rn定理2設(shè)f:Rn→R1在點(diǎn)X?∈Rn上可微，如果X?是非約束問題的局部最優(yōu)解，那么X?就是函數(shù)上述定理指出，當(dāng)我們得到了一個局部最優(yōu)解時(shí)，且得到的梯度為0，那么就說明此時(shí)是該點(diǎn)的局部最優(yōu)解的必要條件。定理3設(shè)f:Rn→R1在點(diǎn)X?∈Rn上的Hesse矩陣?2f(定理4設(shè)f:Rn→R1，X?∈Rn，f是則X?(二)最速下降法的基本思想和迭代步驟最速下降法是1847年著名數(shù)學(xué)家柯西提出的，它是最早的一種分析方法。其它的分析方法不是由其變化就是由其所啟發(fā)，因此這是最優(yōu)化方法的基礎(chǔ)。這是一種最基本的算法，是實(shí)現(xiàn)最優(yōu)解的關(guān)鍵。該方法具有工作量小、存儲小、對起始點(diǎn)要求不高等特點(diǎn)；但其不足之處在于，其收斂速度較慢、效率較低，且往往無法達(dá)到最優(yōu)解。非線性規(guī)劃問題的主要目標(biāo)是求解非線性函數(shù)的最優(yōu)解。其理論與方法在軍事、經(jīng)濟(jì)、管理等領(lǐng)域有著廣闊的應(yīng)用前景。在多維無約束的條件下，最優(yōu)的解法應(yīng)該是最速下降法。最速下降法是只需要考察目前的下降速度，而無法得到全部體現(xiàn)，所以它又可以叫瞎子爬山法。最速下降迭代法這是一個用于解決非線性規(guī)劃問題的迭代法，其核心問題是如何求算出每個迭代的方向pk和步長t（1）搜索方向pk方向pk為單位量，pk=1，從X(k)按方向pkf可以得到在X(k)lim如果要使X(k+1)處的目標(biāo)函數(shù)值比X(k?θ為兩向量之間的夾角。為了使單位時(shí)間內(nèi)下降速度最快，即cosθ應(yīng)取得最小值，即cosθ=?1，即pk從上述我們可以確定最速下降法的搜索方向?yàn)閜k（2）求解搜索步長t。最速下降法采取的搜索步長的方法有兩種：a.最優(yōu)步長搜索法即：f通過求最小值求得步長。b.近似最佳步長法f對上述式子求導(dǎo)并等于0，可以得到步長t=?（3）算法步驟(a).選取初始點(diǎn)X0，設(shè)置終止誤差?(b).計(jì)算?fX(k)(c).計(jì)算搜索方向pk(d).通過對步長t的計(jì)算，可以得到X(k+1)最速下降法能夠有效的解決一些無約束最優(yōu)化問題。理論證明[10]，最速下降法在特定的條件之下是能夠收斂的。（三）最速下降法例題求證例1minf(x)=x1?解：由題可知?fx令搜索方向p(1)=??令步長為t，最優(yōu)步長為t1，則X于是有f令φ1't=2t?2=0可得繼續(xù)迭代得到：?fX則有：X故f令φ2't?fX綜上知，最優(yōu)解為X?=?11.5（四）Python實(shí)現(xiàn)最速下降法例2fx1,Python代碼如下：importmath

fromsympyimport*

#定義符號變量

x_1=symbols('x_1')

x_2=symbols('x_2')

#定義目標(biāo)函數(shù)

fun=2*x_1*x_2+2*x_2-x_1**2-2*x_2**2

fun

#求導(dǎo)數(shù)

grad_1=diff(fun,x_1)

grad_2=diff(fun,x_2)

#定義參數(shù)

MaxIter=100

epsilon=0.0001

#定義初始點(diǎn)

x_1_value=0.5

x_2_value=0.5

iter_cnt=0

current_step_size=10000

grad_1_value=(float)(grad_1.subs({x_1:x_1_value,x_2:x_2_value}).evalf())

grad_2_value=(float)(grad_2.subs({x_1:x_1_value,x_2:x_2_value}).evalf())

current_obj=fun.subs({x_1:x_1_value,x_2:x_2_value}).evalf()

print(

'itCnt:%2dcur_point(%3.2f,%3.2f)cur_Obj:%5.4fgrad_1:%5.4fgrad_2:%5.4fstep_size:%5.4f'%(

iter_cnt,x_1_value,x_2_value,current_obj,grad_1_value,grad_2_value,current_step_size))

#while(iter_cnt<=MaxIterandabs(grad_1_value)+abs(grad_2_value)>=epsilon):

while(abs(grad_1_value)+abs(grad_2_value)>=epsilon):

iter_cnt+=1

#findthestepsize

t=symbols('t')

x_1_updated=x_1_value+grad_1_value*t

x_2_updated=x_2_value+grad_2_value*t

Fun_updated=fun.subs({x_1:x_1_updated,x_2:x_2_updated})

grad_t=diff(Fun_updated,t)

t_value=solve(grad_t,t)[0]#解決grad_t==0

#更新x_1_valueandx_2_value

grad_1_value=(float)(grad_1.subs({x_1:x_1_value,x_2:x_2_value}).evalf())

grad_2_value=(float)(grad_2.subs({x_1:x_1_value,x_2:x_2_value}).evalf())

x_1_value=(float)(x_1_value+t_value*grad_1_value)

x_2_value=(float)(x_2_value+t_value*grad_2_value)

current_obj=fun.subs({x_1:x_1_value,x_2:x_2_value}).evalf()

current_step_size=t_value

print('itCnt:%2dcur_point(%3.2f,%3.2f)cur_Obj:%5.4fgrad_1:%5.4fgrad_2:%5.4fstep_size:%5.4