機(jī)器學(xué)習(xí)優(yōu)化課件

1、優(yōu)化這件小事內(nèi)容介紹你見(jiàn)過(guò)的優(yōu)化？無(wú)約束優(yōu)化梯度下降法牛頓法約束優(yōu)化二次規(guī)劃非線性規(guī)劃Example優(yōu)化問(wèn)題的表示不專業(yè)的“定義”最優(yōu)化，就是1. 構(gòu)造一個(gè)合適的目標(biāo)函數(shù)，使得這個(gè)目標(biāo)函數(shù)取得你想要的“最優(yōu)解”；2. 找到一個(gè)能讓這個(gè)目標(biāo)函數(shù)取得最優(yōu)解的方法；目標(biāo)函數(shù)問(wèn)題來(lái)了，我們?cè)趺辞蠼饽?？冰山一角梯度下降法、牛頓法梯度下降法梯度下降法10J(0,1)梯度下降法01J(0,1)梯度下降法梯度下降法梯度下降法小試牛刀-編程實(shí)現(xiàn)房屋價(jià)格預(yù)測(cè)問(wèn)題：請(qǐng)嘗試不同的步長(zhǎng)設(shè)置最佳步長(zhǎng)最速下降法最速下降法最速下降法最速下降法最速下降法Do you remember Hessian matrix?原來(lái)如此簡(jiǎn)單

2、最佳步長(zhǎng)計(jì)算-編程試試看吧！計(jì)算最佳步長(zhǎng)計(jì)算-試試看Slide No. 28clearsyms x1 x2; %定義符號(hào)變量fx=2*x12+x22; %定義符號(hào)函數(shù)X0=1,1; %初值g=jacobian(fx,x1,x2); %求符號(hào)函數(shù)的梯度H=jacobian(g,x1,x2); %求符號(hào)函數(shù)的Hession矩陣x1=X0(1,1);x2=X0(1,2); %賦初值g0=eval(g);H0=eval(H); %求符號(hào)函數(shù)在x1=1、x2=1梯度、Hession矩陣k=0;fprintf(n)while norm(g0)eps %停機(jī)判斷條件 lamda=g0*g0/(g0*H0*g

3、0); %求lamda fprintf( k=%2d, lamda=%19.16f, x1=%19.16f, x2=%19.16f, fx=%19.16f, norm(p)=%19.16fn, k,lamda,x1,x2,eval(fx),norm(g0) X0=X0-lamda*g0; x1=X0(1,1);x2=X0(1,2); g0=eval(g);H0=eval(H); k=k+1;end參考例子：Matlab代碼實(shí)現(xiàn)你發(fā)現(xiàn)了嗎？這個(gè)算法的優(yōu)缺點(diǎn)？梯度下降-遠(yuǎn)不止如此（1）批量梯度下降速度比較慢，受內(nèi)存的限制，不能再運(yùn)行中加入新的樣本進(jìn)行運(yùn)算（2）隨機(jī)梯度下降隨機(jī)梯度下降是通過(guò)每個(gè)樣本

4、來(lái)迭代更新一次（3）小批量梯度下降將批量梯度下降法中m替換成mini-batch，在此將mini-bach的size遠(yuǎn)小于m的大小，循環(huán) m/b次直到收斂或是循環(huán)次數(shù)達(dá)到并沒(méi)有結(jié)束前沿算法梯度下降的各種變體1.Momentum法2.Nesterov加速梯度法3.Adagrad法4.Adadelta法5.RMSprop法6.適應(yīng)性動(dòng)量估計(jì)法（Adam）其他手段：1.對(duì)SGD進(jìn)行平行或分布式運(yùn)算2.重排和遞進(jìn)學(xué)習(xí)3.批量標(biāo)準(zhǔn)化4.梯度噪聲.休息一下牛頓法“牛頓法”與牛頓的關(guān)系？牛頓法最初由艾薩克牛頓在流數(shù)法（Method of Fluxions，1671年完成，在牛頓去世后的1736年公開發(fā)表）中

5、提出。牛頓法Do you remember 泰勒展開?Do you remember Hessian matrix?簡(jiǎn)單的計(jì)算步驟再現(xiàn)房屋價(jià)格預(yù)測(cè)問(wèn)題這個(gè)算法的特點(diǎn)？牛頓法牛頓法優(yōu)點(diǎn)：牛頓法具有二階收斂速度。對(duì)二次正定函數(shù)，僅需一步迭代即可達(dá)到最優(yōu)解，具有二次終結(jié)性。牛頓法缺點(diǎn)：（1）牛頓法是局部收斂的，即初始點(diǎn)選擇不當(dāng)，可能會(huì)導(dǎo)致不收斂；（2）牛頓法不是下降算法，當(dāng)二階Hesse陣非正定時(shí)，不能保證是下降方向；（3）二階Hesse陣必須可逆，否則算法將無(wú)法進(jìn)行下去；（4）對(duì)函數(shù)分析性質(zhì)要求苛刻，計(jì)算量大，僅適合小規(guī)模優(yōu)化問(wèn)題。改進(jìn)算法1.阻尼牛頓法：增加沿牛頓方向的一維搜索2.Goldste

6、in-Price方法:將牛頓方法與最速下降法結(jié)合3.其他改進(jìn)總結(jié)作業(yè)場(chǎng)景描述：一組登山運(yùn)動(dòng)員，為到達(dá)山谷最低處尋找水源，通過(guò)GPS定位當(dāng)前位置的坐標(biāo)為（0,1），海拔為2km。專家分析，此山走勢(shì)可用函數(shù) z = (x-1)4+y2近似表達(dá)，請(qǐng)幫助登上運(yùn)動(dòng)員確定行走路線，快速找到水源。考察：分別運(yùn)用最速下降法與牛頓法，比較收斂性。 牛頓法繼續(xù)努力！二次規(guī)劃最簡(jiǎn)單的約束非線性規(guī)劃問(wèn)題. 二次規(guī)劃二次規(guī)劃:帶有二次目標(biāo)函數(shù)和線性約束的最優(yōu)化問(wèn)題.Slide No. 52二次規(guī)劃Matlab中求解二次規(guī)劃二次規(guī)劃二次規(guī)劃 定義 如果目標(biāo)函數(shù)或約束條件中至少有一個(gè)是非線性函數(shù),則最優(yōu)化問(wèn)題就叫做非線性規(guī)

7、劃問(wèn)題 一般形式: （1） 其中 ， 是定義在 Rn 上的實(shí)值函數(shù)()n TnRxxxX=,21L()()=.,.,2,1 0 m;1,2,., 0. ljXhiXgtsji非線性規(guī)劃的基本概念Slide No. 57 罰函數(shù)法 罰函數(shù)法基本思想是通過(guò)構(gòu)造罰函數(shù)把約束問(wèn)題轉(zhuǎn)化為一系列無(wú)約束最優(yōu)化問(wèn)題，進(jìn)而用無(wú)約束最優(yōu)化方法去求解這類方法稱為序列無(wú)約束最小化方法簡(jiǎn)稱為SUMT法 其一為SUMT外點(diǎn)法（懲罰函數(shù)法） 其二為SUMT內(nèi)點(diǎn)法（障礙函數(shù)法） 懲罰函數(shù)法PK障礙函數(shù)法障礙函數(shù)法核心：在可行域X的內(nèi)部與邊界面較遠(yuǎn)的點(diǎn)上，障礙函數(shù)與原目標(biāo)函數(shù)應(yīng)盡可能的接近，而在接近邊界面的點(diǎn)上，障礙函數(shù)取相當(dāng)大的數(shù)值。 近似規(guī)劃法的基本思想：將問(wèn)題中的目標(biāo)函數(shù) 和約束條件 近似為線性函數(shù)，并對(duì)變量的取值范圍加以限制，從而得到一個(gè)近似線性規(guī)劃問(wèn)題，再求解，把其符合原始條件的最優(yōu)解作為解的近似近似規(guī)劃法Matlab求解非線性規(guī)劃問(wèn)題 其中X為n維變?cè)蛄?，G(