優(yōu)化算法和梯度下降法ppt課件

局部?jī)?yōu)化算法之一：梯度下降法,李金屏濟(jì)南大學(xué)信息科學(xué)與工程學(xué)院2006年9月,.,2,優(yōu)化算法和運(yùn)籌學(xué),優(yōu)化算法許多實(shí)際問(wèn)題利用數(shù)學(xué)建模的方法得到下面常規(guī)的優(yōu)化形式：minf(x)，s.t.g(x)0,xD.其中，x是一個(gè)n維矢量，D是問(wèn)題的定義域，F(xiàn)可行域。關(guān)于f(x)：當(dāng)x=(x)時(shí)，f(x)是一條曲線；當(dāng)x=(x1,x2)時(shí)，f(x1,x2)是一個(gè)曲面；當(dāng)x=(x1,x2,x3)時(shí)，f(x1,x2,x3)是一個(gè)體密度（或類位勢(shì)函數(shù)）；當(dāng)x=(x1,x2,xn)時(shí)，f(x1,x2,xn)是一個(gè)超曲面。,.,3,優(yōu)化算法和運(yùn)籌學(xué),曲面，自然有許多極大值和極小值，必然各有一個(gè)全局最大值和全局最小值。超曲面，與上相同。有些算法，只能在自己的小范圍內(nèi)搜索極大值或極小值。這些算法稱為局部?jī)?yōu)化算法，常稱為經(jīng)典優(yōu)化算法。另有些算法，可以在整個(gè)超曲面取值范圍內(nèi)搜索最大值或最小值。這些算法稱為全局性優(yōu)化算法，又稱為現(xiàn)代優(yōu)化算法。,.,4,優(yōu)化算法和運(yùn)籌學(xué),一個(gè)簡(jiǎn)單二維曲面,通常的運(yùn)籌學(xué)，就是經(jīng)典的局部?jī)?yōu)化算法。全局性優(yōu)化算法通常是隨機(jī)性搜索。,.,5,局部?jī)?yōu)化算法之一：梯度下降法,見右圖。局部極小值是C點(diǎn)（x0）。梯度，即導(dǎo)數(shù)，但是有方向，是一個(gè)矢量。曲線情況下，表達(dá)式為,如果，f(x)0，則x增加，y也增加，相當(dāng)于B點(diǎn)；如果f(x)0，則x增加，y減小，相當(dāng)于A點(diǎn)。要搜索極小值C點(diǎn)，在A點(diǎn)必須向x增加方向搜索，此時(shí)與A點(diǎn)梯度方向相反；在B點(diǎn)必須向x減小方向搜索，此時(shí)與B點(diǎn)梯度方向相反。總之，搜索極小值，必須向負(fù)梯度方向搜索。,.,6,局部?jī)?yōu)化算法之一：梯度下降法,一般情況下分析：y=f(x1,x2,xn)假設(shè)只有一個(gè)極小點(diǎn)。初始給定參數(shù)為（x10,x20,xn0）。問(wèn)題：從這個(gè)點(diǎn)如何搜索才能找到原函數(shù)的極小值點(diǎn)？方法：1、首先設(shè)定一個(gè)較小的正數(shù)，;2、求當(dāng)前位置處的各個(gè)偏導(dǎo)數(shù)：dy/dx1,dy/dx2,dy/dxn;3、按照下述方式修改當(dāng)前函數(shù)的參數(shù)值：x10x10dy/dx1,x20x20dy/dx2,xn0xn0dy/dxn;4、如果超曲面參數(shù)變化量小于，退出；否則返回2。,.,7,局部?jī)?yōu)化算法之一：梯度下降法,舉例：y=x2/2-2x計(jì)算過(guò)程：任給一個(gè)初始出發(fā)點(diǎn)，設(shè)為x0=-4。(1)首先給定兩個(gè)參數(shù)：=1.5，=0.01；(2)計(jì)算導(dǎo)數(shù)：dy/dx=x-2(3)計(jì)算當(dāng)前導(dǎo)數(shù)值：y=-6(4)修改當(dāng)前參數(shù)：x0=-4x1=x0-*y=-4-1.5*(-6)=5.0;,(5)計(jì)算當(dāng)前導(dǎo)數(shù)值：y=3.0(6)修改當(dāng)前參數(shù)：x1=5.0x2=5.01.5*(3.0)=0.5;,.,8,局部?jī)?yōu)化算法之一：梯度下降法,(7)計(jì)算當(dāng)前導(dǎo)數(shù)值：y=-1.5(8)修改當(dāng)前參數(shù)：x2=0.5x3=0.5-1.5*(-1.5)=2.75;(9)計(jì)算當(dāng)前導(dǎo)數(shù)值：y=0.75(10)修改當(dāng)前參數(shù)：x3=2.75x4=2.75-1.5*(0.75)=1.625;(11)計(jì)算當(dāng)前導(dǎo)數(shù)值：y=-0.375,(12)修改當(dāng)前參數(shù)：x4=1.625x5=1.625-1.5*(-0.375)=2.1875;,.,9,局部?jī)?yōu)化算法之一：梯度下降法,可見，當(dāng)=1.5時(shí)，搜索呈現(xiàn)振蕩形式，在極值點(diǎn)附近反復(fù)搜索?？梢宰C明，當(dāng)2.0時(shí)，搜索將圍繞極值點(diǎn)逐漸發(fā)散，不會(huì)收斂到極值點(diǎn)。為了保證收斂，不應(yīng)當(dāng)太大。但如果過(guò)小，收斂速度將十分緩慢。可以采用自適應(yīng)調(diào)節(jié)的方法加快收斂而又不至于發(fā)散。問(wèn)題：為何當(dāng)很小時(shí)搜索總會(huì)成功？證明：（下頁(yè)）,.,10,局部?jī)?yōu)化算法之一：梯度下降法,y=f(x1,x2,xn)。假設(shè)只有一個(gè)極小點(diǎn)。假設(shè)當(dāng)前點(diǎn)為(x1,x2,xn)。下面修改當(dāng)前參數(shù)：x1x1+x1,x2x2+x2,xnxn+xn.顯然問(wèn)題在于xi(i=1,2,n)的確定。于是，當(dāng)前函數(shù)值為y=f(x1+x1,x2+x2,xn+xn).可以按照泰勒級(jí)數(shù)展開為：y=f(x1,x2,xn)+f其中f=x1*(dy/dx1)+x2*(dy/dx2)+xn*(dy/dxn)如何保證f0是個(gè)小的正數(shù)。代入前式，有f=-*(dy/dx1)*(dy/dx1)-*(dy/dx2)*(dy/dx2)-*(dy/dxn)*(dy/dxn)=-*(dy/dx1)2+(dy/dx2)2+(dy/dxn)20即f0。這樣就可以保證搜索到極小值。于是獲得梯度下降法的搜索策略：x1=-*(dy/dx1),x2=