使用導(dǎo)數(shù)的最優(yōu)化方法學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1使用使用(shyng)導(dǎo)數(shù)的最優(yōu)化方法導(dǎo)數(shù)的最優(yōu)化方法第一頁，共73頁。一一. 無約束最優(yōu)化問題無約束最優(yōu)化問題(wnt)無約束最優(yōu)化問題無約束最優(yōu)化問題nRxtsxf .)(min有有一一階階連連續(xù)續(xù)偏偏導(dǎo)導(dǎo)數(shù)數(shù)。其其中中)(xf 無約束非線性規(guī)劃問題的求解方法分為(fn wi)解析法和直接法兩類。解析法解析法 需要計(jì)算函數(shù)的梯度，利用函數(shù)的解析性質(zhì)需要計(jì)算函數(shù)的梯度，利用函數(shù)的解析性質(zhì)構(gòu)造迭代公式使之收斂到最優(yōu)解。本節(jié)介紹最速下降構(gòu)造迭代公式使之收斂到最優(yōu)解。本節(jié)介紹最速下降法、共軛梯度法、牛頓法、共軛梯度法、牛頓(ni dn)法、變尺度法等解析法、變尺度法等解析方法方法 直接法直

2、接法 僅通過比較目標(biāo)函數(shù)值的大小來移動(dòng)迭代點(diǎn)。下一章主要介紹模式搜索法等直接方法。第1頁/共72頁第二頁，共73頁。 無約束非線性規(guī)劃問題的求解方法分為(fn wi)解析法和直接法兩類。 一般來說，無約束非線性規(guī)劃問題的求解是通過一系列一維搜索來實(shí)現(xiàn)。因此，如何選擇搜索方向(fngxing)是解無約束非線性規(guī)劃問題的核心問題，搜索方向(fngxing)的不同選擇，形成不同的求解方法。本章主要介紹解析法;另一類只用到目標(biāo)函數(shù)值,不必(bb)計(jì)算導(dǎo)數(shù),通常稱為直接方法,放在第11章討論.第2頁/共72頁第三頁，共73頁。nExxf)(min本章考慮如下的下降本章考慮如下的下降(xijing)算法：

3、算法：; 1,) 1 ()1()1(kdx令選定搜索方向給定初始點(diǎn))()(min)()()2()()(0)()(kkkkdxfdxf，求一維搜索問題令：.k得到解為步；轉(zhuǎn)第令處的搜索方向否則，選取在是最優(yōu)解，停；若令：2, 1,)3()1()1()1()()()1(kkdxxdxxkkkkkkk算法。選取不同，得到不同的搜索方向)(kd主要(zhyo)介紹最速下降法、牛頓法，共軛梯度法，擬牛頓法等第3頁/共72頁第四頁，共73頁。10.1 最速下降法最速下降法 10.1.1 最速下降方向最速下降方向 考慮無約束問題nExxf)(min(6.1.2)其中函數(shù) 具有一階連續(xù)偏導(dǎo)數(shù). 人們?cè)谔幚磉@類

4、問題時(shí),總希望從某一點(diǎn)出發(fā),選擇一個(gè)目標(biāo)函數(shù)值下降最快的方向,以利于盡快達(dá)到極小點(diǎn).正是(zhn sh)基于這樣一種愿望,早在1847年法國著名數(shù)學(xué)家Cauchy提出了最速下降法.后來,Curry等人作了進(jìn)一步的研究.現(xiàn)在最速下降法已經(jīng)成為眾所周知的一種最基本的算法,它對(duì)其他算法的研究也很有啟發(fā)作用,因此在最優(yōu)化方法中占有重要地位.下面我們先來討論怎樣選擇最速下降方向. )(xf第4頁/共72頁第五頁，共73頁。 人們?cè)谔幚磉@類問題時(shí),總希望從某一點(diǎn)出發(fā),選擇一個(gè)目標(biāo)函數(shù)值下降最快的方向,以利于盡快達(dá)到極小點(diǎn).正是基于這樣一種愿望,早在1847年法國著名數(shù)學(xué)家Cauchy提出了最速下降法最速下

5、降法.后來,Curry等人作了進(jìn)一步的研究.現(xiàn)在最速下降法已經(jīng)成為眾所周知的一種最基本的算法,它對(duì)其他算法的研究也很有啟發(fā)作用,因此在最優(yōu)化方法中占有重要地位.下面我們先來討論怎樣選擇最最速下降方向速下降方向. 我們知道,函數(shù) 在點(diǎn) 處沿方向 的變化率可用方向?qū)?shù)來表達(dá),對(duì)于可微函數(shù),方向?qū)?shù)等于梯度與方向的內(nèi)積,即)(xfxddxfdxDfT)();(6.1.2)因此,求函數(shù) 在點(diǎn) 處的下降最快的方向,可歸結(jié)為求解下列非線性規(guī)劃:)(xfx1.)(mindtsdxfT(6.1.3)第5頁/共72頁第六頁，共73頁。根據(jù)Schwartz不等式,有)()()(xfdxfdxfT去掉絕對(duì)值符號(hào),可

6、以得到)()(xfdxfT(6.1.4)由上式可知,當(dāng))()(xfxfd(6.1.5)時(shí)等號(hào)成立.因此,在點(diǎn) 處沿(6.1.5)所定義的方向變化率最小,即負(fù)梯度方向?yàn)樽钏傧陆捣较蜇?fù)梯度方向?yàn)樽钏傧陆捣较? 這里要特別指出,在不同尺度下最速下降方向是不同的.前面定義的最速下降方向,是在向量 的毆氏范數(shù) 不大于1的限制得到的,屬于毆氏度量意義下的最速下降方向.如果改用其他度量,比xd2d第6頁/共72頁第七頁，共73頁。如,設(shè) 為對(duì)稱正定矩陣,在向量 的 范數(shù) 不大于1的限制下,極小化 ,則得到的最速下降方向與前者不同.AdA21)(AdddTAdxfT)( 10.1.2 最速下降算法最速下降算法

7、 最速下降法的迭代公式是)()() 1(kkkkdxx(10.1.6)其中 是從 出發(fā)的搜索方向,這里取在點(diǎn) 處的最速下降方向,即)()()(kkxfd)(kd)(kx 是從 出發(fā)沿方向 進(jìn)行一維搜索的步長,即 滿足k)(kx)(kdk)(min)()()(0)()(kkkkkdxfdxf(10.1.11)(kx第7頁/共72頁第八頁，共73頁。 計(jì)算步驟計(jì)算步驟如下: 1.給定初點(diǎn) ,允許誤差 ,置 .nEx) 1 (01k 2.計(jì)算搜索方向)()()(kkxfd 3.若 ,則停止計(jì)算;否則,從 出發(fā),沿 進(jìn)行一維搜索,求 ,使)(kd)(kx)(kdk)(min)()()(0)()(kkk

8、kkdxfdxf 4.令 ,置 ,轉(zhuǎn)步2.)()() 1(kkkkdxx1: kk 例例10.1.1 用最速下降法解下列問題:22212)(minxxxf.101,) 1 , 1 () 1 (Tx初點(diǎn)第8頁/共72頁第九頁，共73頁。解：解：,)2,4()(21Txxxf.)2,4()()1(1Txfd.)21 ,41()1()1(Tdx，令22)1()1()21()41 (2)()(dxf)(min求解0)21(4)41(16)(令1851Tdxx)94,91()1(1)1()2(22212)(minxxxf) 1 , 1 ()1(x第二次迭代(di di)：.)9/8,9/4()()2()

9、2(Txfd1 . 0789. 15/54)9/8()9/4(22)2(dTdx984941)2()2(，令81)21 (1681)41(2)()(22)2()2(dxf第9頁/共72頁第十頁，共73頁。Tdx984941)2()2(，令81)21 (1681)41(2)()(22)2()2(dxf)(min求解，令081)21 (6481)41(16)(1252Tdxx11272)2(2)2()3(第三次迭代(di di)：.)27/4,27/8()()3()3(Txfd1 . 03313. 027/54)27/4()27/8(22)3(d進(jìn)行一維搜索：沿從)3()3(dx)()(min)3

10、()3(dxf求解21412721227411272)3()3(dx第10頁/共72頁第十一頁，共73頁。21412721227411272)3()3(dx，令2222)3()3(27)21 (427)41(8)()(dxf22212)(xxxf，027)21 (1627)41(64)(2218528880341243241912721227418511272)3(3)3()4(dxx212438842432)()4(xf,)2,4()(21Txxxf0736. 052438)()4(xf412432x似解滿足精度要求，得到近00*x精確解第11頁/共72頁第十二頁，共73頁。)()(min)

11、()(kkdxf求解在最速下降(xijing)法的一位搜素中0)()()(T)()(kkkddxf由k解得步長滿足：故步長k0)()(T)()(kkkkddxf)()()1(kkkkdxx0)()(T)1(kkdxf)()()(kkxfd其中0)(T)1(kkdd即在最速下降(xijing)法中相鄰兩次搜索方向是正交的。第12頁/共72頁第十三頁，共73頁。)()(min)()(kkdxf對(duì)于一維搜索cxbAxxxfTT21)(對(duì)于(duy)二次嚴(yán)格凸函數(shù)其中A為n維對(duì)稱(duchn)正定矩陣可以(ky)求出步長因子k)()()(kkxfd其中滿足：由步長k0)()(T)()(kkkkddxf

12、bAx)(xf由0)()()()(kTkkkdbdxA解得：)()()()()()()()()()()(kTkkTkkTkkTkkAdddxfAdddbAx)()()1( kkxfxf）（)()(2)()()()()(21kTkkTkAddxfxf（本章習(xí)題7）第13頁/共72頁第十四頁，共73頁。鋸齒鋸齒(jch)現(xiàn)象現(xiàn)象 最速下降法的迭代點(diǎn)在向極小點(diǎn)靠近(kojn)的過程中，走的是曲折的路線：后一次搜索方向d(k+1)與前一次搜索方向 d(k)總是相互垂直的，稱它為鋸齒現(xiàn)象。這一點(diǎn)在前面的例題中已得到(d do)驗(yàn)證。除極特殊的目標(biāo)函數(shù)（如等值面為球面的函數(shù)）和極特殊的初始點(diǎn)外，這種現(xiàn)象一

13、般都要發(fā)生。 最速下降法的收斂性第14頁/共72頁第十五頁，共73頁。 從直觀上可以看到，在遠(yuǎn)離極小點(diǎn)的地方，每次迭代都有可能使目標(biāo)函數(shù)值有較多的下降，但在接近極小點(diǎn)的地方，由于鋸齒現(xiàn)象，每次迭代行進(jìn)的距離開始(kish)逐漸變小。因而收斂速度不快。 已有結(jié)論表明，最速下降法對(duì)于正定二次函數(shù)關(guān)于任意初始點(diǎn)都是收斂(shulin)的(定理10.1.2)，而且恰好是線性收斂(shulin)的。第15頁/共72頁第十六頁，共73頁。鋸齒現(xiàn)象鋸齒現(xiàn)象，其其等等值值面面近近似似數(shù)數(shù)可可以以用用二二次次函函數(shù)數(shù)近近似似在在極極小小點(diǎn)點(diǎn)附附近近，目目標(biāo)標(biāo)函函橢球面。橢球面。1x*x2x3x它它只只是是。標(biāo)標(biāo)

14、函函數(shù)數(shù)的的一一種種局局部部性性質(zhì)質(zhì)最最速速下下降降方方向向反反映映了了目目快的方向?？斓姆较颉＞植磕繕?biāo)函數(shù)值下降最局部目標(biāo)函數(shù)值下降最注注的的算算法法。最最速速下下降降法法是是線線性性收收斂斂第16頁/共72頁第十七頁，共73頁。10.2 牛頓法牛頓法 6.2.1 牛頓法牛頓法 設(shè) 是二次可微實(shí)函數(shù), .又設(shè) 是 的極小點(diǎn)的一個(gè)估計(jì),我們把 在 展成Taylor級(jí)數(shù),并取二階近似:)(xfnEx)(kx)(xf)(xf)(kx)()(21)()()()()()()(2)()()()(kkTkkTkkxxxfxxxxxfxfxxf其中 是 在 處的Hessian矩陣.為求 的平穩(wěn)點(diǎn),令)()(

15、2kxf)(xf)(kx)(x0)(x0)()()()(2)(kkkxxxfxf即(10.2.1)第17頁/共72頁第十八頁，共73頁。設(shè) 可逆,有(10.2.1)得到牛頓法的迭代公式)()(2kxf)()()(1)(2)()1(kkkkxfxfxx(10.2.2)其中 是Hessian矩陣 的逆矩陣. 這樣, 知道 后,算出在這一點(diǎn)處目標(biāo)函數(shù)的梯度和Hessian矩陣的逆,代人(10.2.2),便得到后繼點(diǎn) ,用 代替 ,再用(10.2.2)計(jì)算,又得到 的后繼點(diǎn).依此類推,產(chǎn)生序列 .在適當(dāng)?shù)臈l件下,這個(gè)序列收斂.1)(2)(kxf)()(2kxf)(kx)1( kx1kk)1( kx)(

16、kx 第18頁/共72頁第十九頁，共73頁。22112)()()(. 2)(. 1kxxxxxfxfxfkxf則牛頓法產(chǎn)生(chnshng)的序列收斂于 .x 實(shí)際上,當(dāng)牛頓法收斂時(shí),有下列(xili)關(guān)系:2)()1(xxcxxkk其中 C 是某個(gè)常數(shù).因此,牛頓法至少2級(jí)收斂,參看文獻(xiàn)(wnxin)19.可見牛頓法的收斂速率是很快的.第19頁/共72頁第二十頁，共73頁。例例 用牛頓用牛頓(ni dn)法解下列問題法解下列問題:2241) 1(minxx.) 1 , 0()1(Tx 我們(w men)取初點(diǎn)解：)()()(1)(2)()1(kkkkxfxfxx2312) 1(4)(xxxf

17、24)()1(xf200) 1(12)(212xxf20012)(2xf)()()1(1)1(2)1()2(xfxfxx242/10012/11003/113/110第2次迭代(di di)：027/32)()2(xf2009/48)()2(2xf第20頁/共72頁第二十一頁，共73頁。第2次迭代(di di)：027/32)()2(xf2009/48)()2(2xf)()()2(1)2(2)2()3(xfxfxx027/322/10048/903/103/1)2(x09/5繼續(xù)迭代(di di)，得到,.081/65,027/19)5()4(xx最終(zu zhn)收斂到最優(yōu)解x*=(1,0

18、)T第21頁/共72頁第二十二頁，共73頁。我們(w men)先用極值條件求解.令0)(bAxxf下面用牛頓法求解. 任取初始(ch sh)點(diǎn)x(1) , 根據(jù)牛頓法的迭代公式：特別(tbi)地,對(duì)于二次凸函數(shù),用牛頓法求解,經(jīng)1次迭代即達(dá)極小點(diǎn).設(shè)有二次凸函數(shù)cxbAxxxfTT21)(其中A是對(duì)稱正定矩陣。)()()(1)(2)()1(kkkkxfxfxx求迭代點(diǎn)x(2) bAx1得到是最小值點(diǎn)嗎？bAx1為什么？xbAbAxAxxfAxx1)1(1)1()1(1)1()2()()(即1次迭代達(dá)到極小點(diǎn).第22頁/共72頁第二十三頁，共73頁。)()(12xfxfd不一定是下降方向,經(jīng)迭代

19、,目標(biāo)函數(shù)值可能上升.此外,即使目標(biāo)函數(shù)值下降,得到的點(diǎn) 也不一定是沿牛頓方向的最好點(diǎn)或極小點(diǎn).因此,人們對(duì)牛頓法進(jìn)行修正,提出了阻尼牛頓法. 值得注意,當(dāng)初始點(diǎn)遠(yuǎn)離極小點(diǎn)時(shí),牛頓法可能不收斂.原因之一,牛頓方向 以后還會(huì)遇到一些算法,把它們用于二次凸函數(shù)時(shí),類似于牛頓法,經(jīng)有限次迭代必達(dá)到極小點(diǎn).這種性質(zhì)稱為二次終止性二次終止性. )1( kx對(duì)于二次凸函數(shù),用牛頓法求解,經(jīng)1次迭代(di di)即達(dá)極小點(diǎn)第23頁/共72頁第二十四頁，共73頁。 10.2.2 阻尼牛頓法阻尼牛頓法 阻尼牛頓法與原始牛頓法的區(qū)別在于增加了沿牛頓方向的一維搜索,其迭代公式是)()()1(kkkkdxx(6.2.

20、6)其中 為牛頓方向, 是由一維搜索得到的步長,即滿足)(min)()()()()(kkkkkdxfdxfk)()()(1)(2)(kkkxfxfd 阻尼牛頓法的計(jì)算步驟計(jì)算步驟如下: 1.給定初始點(diǎn) ,允許誤差 ,置 . 2.計(jì)算 )1 (x01k1)(2)()(),(kkxfxf第24頁/共72頁第二十五頁，共73頁。 3.若 ,則停止迭代;否則,令)()(kxf)()()(1)(2)(kkkxfxfd 4.從 出發(fā),沿方向 作一維搜索:)(kx)(kd)()(min)()()()(kkkkkdxfdxf令 .)()()1(kkkkdxx 5.置 ,轉(zhuǎn)步2.1: kk 由于阻尼牛頓法含有一

21、維搜索,因此每次迭代目標(biāo)函數(shù)值一般有所下降(決不會(huì)上升).可以證明,阻尼牛頓法在適當(dāng)?shù)臈l件下具有全局收斂性,且為2級(jí)收斂.第25頁/共72頁第二十六頁，共73頁。、共軛梯度、共軛梯度(t d)(t d)法法第26頁/共72頁第二十七頁，共73頁。10.3.1 共軛方向共軛方向(fngxing)法法1. 共軛方向共軛方向(fngxing)和共軛方和共軛方向向(fngxing)法法定義定義共軛。共軛。關(guān)于關(guān)于和和，則稱，則稱若有若有AddAddT21210 ARdddnk它它們們兩兩兩兩關(guān)關(guān)于于中中一一組組非非零零向向量量，如如果果是是設(shè)設(shè),21。共共軛軛，即即kjijiAddjTi,2,1,0

22、共軛方向。共軛方向。組組共軛的，也稱它們是一共軛的，也稱它們是一則稱這組方向是關(guān)于則稱這組方向是關(guān)于AA注：注：002121 dddIdTT21dd 共軛是正交的推廣共軛是正交的推廣(tugung)。，和和中中的的兩兩個(gè)個(gè)非非零零向向量量的的對(duì)對(duì)稱稱正正定定矩矩陣陣，對(duì)對(duì)于于是是設(shè)設(shè)21ddRnnAn 是是單單位位矩矩陣陣，則則如如果果 A第27頁/共72頁第二十八頁，共73頁。幾何幾何(j h)意義意義設(shè)有二次函數(shù)設(shè)有二次函數(shù))()(21)(xxAxxxfT 對(duì)對(duì)稱稱正正定定矩矩陣陣，是是其其中中nnA 是一個(gè)定點(diǎn)。是一個(gè)定點(diǎn)。x的的等等值值面面則則函函數(shù)數(shù))(xfcxxAxxT )()(2

23、1為中心的橢球面。為中心的橢球面。是以是以 x由于由于,0)()( xxAxf,0)(2 AxfA所所以以正正定定，因因?yàn)闉榈牡臉O極小小點(diǎn)點(diǎn)。是是因因此此)(xfxx,)(2Axf 而而第28頁/共72頁第二十九頁，共73頁。幾何幾何(j h)意義意義設(shè)有二次函數(shù)設(shè)有二次函數(shù))()(21)(xxAxxxfT 對(duì)對(duì)稱稱正正定定矩矩陣陣，是是其其中中nnA 是一個(gè)定點(diǎn)。是一個(gè)定點(diǎn)。x的的等等值值面面則則函函數(shù)數(shù))(xfcxxAxxT )()(21為中心的橢球面。為中心的橢球面。是以是以 x由于由于,0)()( xxAxf,0)(2 AxfA所所以以正正定定，因因?yàn)闉榈牡臉O極小小點(diǎn)點(diǎn)。是是因因此此)

24、(xfxx,)(2Axf 而而第29頁/共72頁第三十頁，共73頁。點(diǎn)，點(diǎn)，是在某個(gè)等值面上的一是在某個(gè)等值面上的一設(shè)設(shè))0(x處的法向量為處的法向量為該等值面在點(diǎn)該等值面在點(diǎn))1(x. )()()1()1(xxAxf o1x2xx)1(d)0(x中的一個(gè)方向，中的一個(gè)方向，是是nRd)1(。以以最最優(yōu)優(yōu)步步長長搜搜索索得得到到點(diǎn)點(diǎn)沿沿著著)1()1()0(xdx所所在在等等值值面面的的切切向向量量。是是點(diǎn)點(diǎn)則則)1()1(xd正交，正交，與與則則)()1()1(xfd , 0)()1()1( xfdT即即,)1()2(xxd 令令)1(x所以所以, 0)2()1( AddT共共軛軛。小小點(diǎn)點(diǎn)

25、的的向向量量關(guān)關(guān)于于向向量量與與由由這這一一點(diǎn)點(diǎn)指指向向極極即即等等值值面面上上一一點(diǎn)點(diǎn)處處的的切切A)2(dcxxAxxxfT)()(21)(第30頁/共72頁第三十一頁，共73頁。共共軛軛的的非非零零個(gè)個(gè)是是階階對(duì)對(duì)稱稱正正定定矩矩陣陣，是是設(shè)設(shè)AkdddnAk,21性無關(guān)。性無關(guān)。向量，則這個(gè)向量組線向量，則這個(gè)向量組線. 1 . 3 .10定理證明證明，使使得得設(shè)設(shè)存存在在實(shí)實(shí)數(shù)數(shù)k ,21,01 kiiid ，則則有有上上式式兩兩邊邊同同時(shí)時(shí)左左乘乘AdTj,01 kiiTjiAdd 可化簡(jiǎn)為可化簡(jiǎn)為共軛的向量，所以上式共軛的向量，所以上式個(gè)個(gè)是是因?yàn)橐驗(yàn)锳kdddk,21.0 jT

26、jjAdd ，是正定矩陣，所以是正定矩陣，所以而而因?yàn)橐驗(yàn)?,0 jTjjAddAd所以所以。kjj,2,1,0 線性無關(guān)。線性無關(guān)。因此因此kddd,21第31頁/共72頁第三十二頁，共73頁。2 . 3 .10定理，設(shè)設(shè)有有函函數(shù)數(shù)cxbAxxxfTT 21)(共共軛軛向向量量。一一組組是是階階對(duì)對(duì)稱稱正正定定矩矩陣陣。是是其其中中AdddnAk)()2()1(,進(jìn)進(jìn)行行搜搜索索，為為初初始始點(diǎn)點(diǎn)，依依次次沿沿以以任任意意的的)()2()1()1(,kndddRx 上上的的在在是是函函數(shù)數(shù)則則得得到到點(diǎn)點(diǎn)kkkBxxfxxxx )1()1()1()3()2()(,極小點(diǎn)，其中極小點(diǎn)，其中,

27、|1)(RdxxBikiiik 是是時(shí)時(shí)，當(dāng)當(dāng)，生生成成的的子子空空間間。特特別別地地是是由由)1()()2()1(, nkxnkddd上上的的唯唯一一極極小小點(diǎn)點(diǎn)。在在nRxf)(推論推論有有在上述定理?xiàng)l件下，必在上述定理?xiàng)l件下，必。kidxfiTk,2,1,0)()()1( 第32頁/共72頁第三十三頁，共73頁。)(*)1(*1)1(*1)1()(*)1(*1)1()(*)()1(.kkkkkkkkkkkkkdddxddxdxx), 1()(*)()1(kidxxiiii證：設(shè)), 1 , 0(0)()()1(kidxfiTk若上的極小點(diǎn)。在是函數(shù)要證kkBxxfx)1()1()(,|1

28、)(RdxxBikiiik ,)1(kBxx對(duì)于)()1(1)1 (1)1 (kkkkdddxx)()()1( kxfxf要證)()()()()1()1()1(kTkkxxxfxfxf)(1)1(*)1()()()(ikiTkiikdxfxf則必有)()()1( kxfxf,)1(kBxx對(duì)于), 1 , 0(0)()()1(kidxfiTk下證第33頁/共72頁第三十四頁，共73頁。), 1 , 0(0)()()1(kidxfiTk下用歸納法證的極小點(diǎn)，沿方向在為由), 1 , 0()()()()1(kidxxfxiii為問題中的即*)(*)()1(iiiiidxx的解。)()(min)()

29、(iidxf0)()(T)(*)(iiiiddxf.,.,2 , 1, 0)()(T)1(kidxfii顯然成立。時(shí)當(dāng)0)(,1)()1(kTkdxfk. 1,.,2 , 1,0)(,)()(midxfnmkiTm成立有時(shí)假設(shè)當(dāng).,.,2 , 1,0)(,1)()1(midxfmkiTm成立證時(shí)則當(dāng))(*)()1()1()(mkmmmAdbAxbAxxf)(*)()(mkmAdxf)()(*)()()(T)1()()()(iTmkiTmimAdddxfdxfmi時(shí)，故當(dāng)，由歸納假設(shè)，0)()()(iTmdxf0)()()(iTmAdd又, 0)()(T)1(imdxfmi時(shí)，故當(dāng)0)()(T)

30、1(mmdxf而.,.,2 , 1,0)()()1(midxfiTm成立故第34頁/共72頁第三十五頁，共73頁。，設(shè)設(shè)有有函函數(shù)數(shù)cxbAxxxfTT 21)(共共軛軛向向量量。一一組組是是階階對(duì)對(duì)稱稱正正定定矩矩陣陣。是是其其中中AdddnAk)()2()1(,推論(tuln)：進(jìn)進(jìn)行行搜搜索索，為為初初始始點(diǎn)點(diǎn)，依依次次沿沿以以任任意意的的)()2()1()1(,kndddRx 上上的的在在是是函函數(shù)數(shù)則則得得到到點(diǎn)點(diǎn)kkkBxxfxxxx )1()1()1()3()2()(,|1)(RdxxBikiiik 上上的的唯唯一一極極小小點(diǎn)點(diǎn)。在在nRxf)(nkkidxfiTk，且有), 1

31、 , 0(0)()()1(0)()1(nxf時(shí)，當(dāng)，特別地nk 極小點(diǎn)，其中極小點(diǎn)，其中點(diǎn)。經(jīng)有限次迭代必得極小沿一組共軛方向搜索，即對(duì)于二次凸函數(shù)，若第35頁/共72頁第三十六頁，共73頁。共軛方向(fngxing)法對(duì)對(duì)于于極極小小化化問問題題:法法為為共共軛軛方方向向法法是是正正定定矩矩陣陣，稱稱下下述述算算其其中中 A,21)(mincxbAxxxfTT ；共軛方向共軛方向取定一組取定一組)()2()1(,)1(ndddA,)2()1()()1( kkxxx確確定定點(diǎn)點(diǎn)依依次次按按照照下下式式由由任任取取初初始始點(diǎn)點(diǎn) )(min)()()()()()()()1(kkkkkkkkkdxf

32、dxfdxx 。滿足滿足直到某個(gè)直到某個(gè)0)()()( kkxfx注注至多經(jīng)過至多經(jīng)過求解上述極小化問題，求解上述極小化問題，可知，利用共軛方向法可知，利用共軛方向法由定理由定理2。次次迭迭代代必必可可得得到到最最優(yōu)優(yōu)解解n第36頁/共72頁第三十七頁，共73頁。 )(min)()()()()()()()1(kkkkkkkkkdxfdxfdxx ；共軛方向取定一組)()2()1 (,ndddA對(duì)于上述(shngsh)正交方向法，它是下降算法嗎？不難得到(d do)：, 0)()(T)1(kkdxf由)()()()()()(kTkkTkkAdddxfcxbAxxxfTT21)()()(21)()

33、()()(yxAyxyxyfyfxfTT由)()(21)()()()()()1()()1()()1()()1(kkTkkkkTkkkxxAxxxxxfxfxf）（)()(2)()()()(21kTkkTkAdddxf, 0)()()1(kkxfxf）（，若0)()()(kTkdxf).()()1( kkxfxf）（則故正交方向法，它是下降(xijing)算法。第37頁/共72頁第三十八頁，共73頁。？共軛方向如何構(gòu)造一組)()2()1 (,ndddA可由一組線性無關(guān)向量組，類似(li s)于schmidt正交化過程，。共軛方向構(gòu)造一組)()2()1(,ndddA.13具體步驟見本章習(xí)題共軛方向

34、的方法。下一節(jié)介紹另一種構(gòu)造cxbAxxxfTT21)(min化問題對(duì)于二次凸函數(shù)的極小第38頁/共72頁第三十九頁，共73頁。10.3 共軛梯度法共軛梯度法 10.3.2 共軛梯度法共軛梯度法 共軛梯度法最初由Hesteness和Stiefel于1952年為求解線性方程組而提出.后來,人們把這種方法用于求解無約束最優(yōu)化問題,使之成為一種重要的最優(yōu)化方法. 下面,重點(diǎn)介紹Fletcher-Reeves共軛梯度法共軛梯度法,簡(jiǎn)稱FR法法. 共軛梯度法的基本思想基本思想是把共軛性與最速下降方法相結(jié)合,利用已知點(diǎn)處的梯度構(gòu)造一組共軛方向,并沿這組方向進(jìn)行搜索,求出目標(biāo)函數(shù)的極小點(diǎn).根據(jù)共軛方向的基本

35、性質(zhì),這種方法具有二次終止性. 我們先討論對(duì)于二次凸函數(shù)的共軛梯度法,然后再把這種方法推廣到極小化一般函數(shù)的情形.第39頁/共72頁第四十頁，共73頁。. 共軛梯度(t d)法 如何選取如何選取(xunq)一組共軛方向？一組共軛方向？:共軛梯度法共軛梯度法eevesRFletcher 代點(diǎn)代點(diǎn)向相結(jié)合，利用已知迭向相結(jié)合，利用已知迭將共軛性和最速下降方將共軛性和最速下降方基本思想：基本思想：進(jìn)行搜索，求出進(jìn)行搜索，求出共軛方向，并沿此方向共軛方向，并沿此方向處的梯度方向構(gòu)造一組處的梯度方向構(gòu)造一組函數(shù)的極小點(diǎn)。函數(shù)的極小點(diǎn)。以下分析以下分析(fnx)算法的具體步驟。算法的具體步驟。cxbAxx

36、xfTT 21)(min是是常常數(shù)數(shù)。，是是對(duì)對(duì)稱稱正正定定矩矩陣陣，其其中中cRbARxnn ,我們先討論對(duì)于二次凸函數(shù)的共軛梯度法,然后再把這種方法推廣到極小化一般函數(shù)的情形第40頁/共72頁第四十一頁，共73頁。；，第一個(gè)搜索方向取為，第一個(gè)搜索方向取為任取初始點(diǎn)任取初始點(diǎn))()1()1()1()1(xfdx ，令令，若若，設(shè)設(shè)已已求求得得點(diǎn)點(diǎn))(0)()2()1(1)1()1( kkkkxfgxfx:)1(按按如如下下方方式式確確定定則則下下一一個(gè)個(gè)搜搜索索方方向向 kd)1()(1)1(kkkkdgd 令令共軛。共軛。關(guān)于關(guān)于和和要求要求Addkk)()1( ？如如何何確確定定k ，

37、得，得）式兩邊同時(shí)左乘）式兩邊同時(shí)左乘則在（則在（AdTk)(1)()(1)()1()(0kTkkkTkkTkdAdAgdAdd )2()()(1)(kTkkTkkdAdgAd 解解得得cxbAxxxfTT 21)(min初始搜索方向(fngxing)為最速下降方向(fngxing)第41頁/共72頁第四十二頁，共73頁。:)3(搜搜索索步步長長的的確確定定，步步長長利利用用一一維維搜搜索索確確定定最最優(yōu)優(yōu)和和搜搜索索方方向向已已知知迭迭代代點(diǎn)點(diǎn)kkkdx ,)()(。即求解即求解)(min)()(kkdxf , )()()()(kkdxf 記記，令令0)()()()()( kTkkddxf

38、，即即有有0)()()()( kTkkdbdxA ，則則有有令令bAxxfgkkk )()()(，0)()( kTkkdAdg )3()()()(kTkkTkkAdddg 解解得得第42頁/共72頁第四十三頁，共73頁。3 . 3 .10定理次次算法在算法在，對(duì)于正定二次函數(shù)對(duì)于正定二次函數(shù)nmFRcxbAxxxfTT 21)(），下下列列關(guān)關(guān)系系成成立立（且且對(duì)對(duì)所所有有的的一一維維搜搜索索后后即即終終止止，并并mii 1;1,2,1,0)1()()( ijAddjTi;1,2,1,0)2( ijggjTi。iTiiTiggdg )()3(注注共共軛軛的的。是是可可知知搜搜索索方方向向）由由

39、定定理理（Adddm)()2()1(,31則則構(gòu)構(gòu)造造的的搜搜索索必必須須取取負(fù)負(fù)梯梯度度方方向向，否否算算法法中中第第一一個(gè)個(gè)搜搜索索方方向向)2(方方向向不不能能保保證證共共軛軛性性。）可可知知，的的（由由定定理理33)3(,0|2)( iiTiiTigggdg處處的的下下降降方方向向。是是迭迭代代點(diǎn)點(diǎn)所所以以)()(iixd第43頁/共72頁第四十四頁，共73頁。的的計(jì)計(jì)算算公公式式可可以以簡(jiǎn)簡(jiǎn)化化。算算法法中中，由由定定理理iFR 3)4()()(1)(iTiiTiiAddgAd )()()(1iTiiTiAdddAg / )( / )( )()1()()()1(1iiiTiiiiTi

40、xxAdxxAg .)()()(bxAxfgiii )()(1)(11iiTiiiTiiggdggg iTiigdg)(21| )4(|221iigg )1964,Re(|221evesFletcherggiii第44頁/共72頁第四十五頁，共73頁。)1964,Re(|221evesFletcherggiii式：外，還有下列等價(jià)表達(dá)除表達(dá)式有多個(gè)等價(jià)式，定理中，對(duì)于二次凸規(guī)劃，上述221|iiiigg)1972,()()(1)(11wolfeseensenggdgggiiTiiiTii)1967,()()()(1DanielAddAdgiTiiTii)()(11dixongdggiTiiTi

41、i)1969,()()(11PPRgggggiTiiiTii常用兩個(gè)公式(gngsh):著名的FR和PPR公式(gngsh)第45頁/共72頁第四十六頁，共73頁。算算法法步步驟驟：FR。，令，令精度要求精度要求，任取初始點(diǎn)任取初始點(diǎn)1. 1)1( kx 為為所所求求極極小小點(diǎn)點(diǎn)；停停止止，若若令令)1(1)1(1,|, )(. 2xgxfg 。令令，）計(jì)計(jì)算算利利用用公公式式（否否則則，令令)1(1)1()2(11)1(3,dxxgd 為所求極小點(diǎn)；為所求極小點(diǎn)；停止，停止，若若令令)1(1)1(1,|, )(. 3 kkkkxgxfg ）計(jì)計(jì)算算。用用公公式式（其其中中否否則則，令令4,)

42、(1)1(kkkkkdgd 。轉(zhuǎn)轉(zhuǎn)，令，令）計(jì)算）計(jì)算利用公式（利用公式（3,3. 4)()()1(kkkkkdxx 。令令1: kk)3()()()(kTkkTkkAdddg)4(|221iiiggcxbAxxxfTT21)(min求解二次凸規(guī)劃(guhu)的FR 共軛梯度法求解二次凸規(guī)劃的FR 共軛梯度法迭代(di di)多少次才可以達(dá)到最優(yōu)解？第46頁/共72頁第四十七頁，共73頁。算算法法求求解解下下述述問問題題：用用例例FR22212)(minxxxf 。初初始始點(diǎn)點(diǎn)取取為為Tx)2,2()1( 解：解：.)2,4()(21Txxxf 次迭代：次迭代：第第1,)4,8(1)1(Tgd

43、 令令)1()1()1(11AdddgTT ,2004),(21)(2121 xxxxxf.2004 A而而 482004)4,8(48)4,8(185 .2004A，或利用0)()()()()(kTkkddxfk求出, )()()()(kkdxf 記記第47頁/共72頁第四十八頁，共73頁。)1(1)1()2(dxx 所以所以TT)4,8(185)2,2( T)98,92( 次迭代：次迭代：第第 2.)916,98(2Tg 21221|gg .81448)916()98(2222 )1(12)2(dgdTT)4,8(814)916,98( T)4,1(8140 .)2,4()(21Txxxf

44、 ,)4,8(1)1(Tgd)1(12)2(dgd第48頁/共72頁第四十九頁，共73頁。)2()2()2(22AdddgTT 412004)4,1()8140(41)916,98(81402209 )2(2)2()3(dxx TT)4,1(8140209)98,92( T)0,0( Tg)0,0(3 即為所求極小點(diǎn)。即為所求極小點(diǎn)。)3(x第49頁/共72頁第五十頁，共73頁。. 用于一般(ybn)函數(shù)的共軛梯度法nRxtsxf .)(min共軛梯度法進(jìn)行修改：共軛梯度法進(jìn)行修改：對(duì)用于正定二次函數(shù)的對(duì)用于正定二次函數(shù)的確確定定。）計(jì)計(jì)算算，需需由由一一維維搜搜索索不不能能利利用用公公式式（

45、搜搜索索步步長長3)2(i 。速下降方向，即第一個(gè)搜索方向仍取最)() 1 ()1()1(xfd算算：其其它它搜搜索索方方向向按按下下式式計(jì)計(jì),)()()1()1(iiiidxfd 。其其中中2)(2)1(|)(|)(|iiixfxf )3()()()(kTkkTkkAdddg第50頁/共72頁第五十一頁，共73頁。）計(jì)算。用公式（其中令4, 1)(1)1(kkkkkdgdk. 用于一般函數(shù)(hnsh)的共軛梯度法nRxtsxf .)(min。速下降方向，即第一個(gè)搜索方向仍取最)() 1 ()1()1(xfd)4(|221iiigg)(min)2()()(kkdxf但求解一維搜索問題確定。）計(jì)

46、算，需由一維搜索不能利用公式（搜索步長3i)3()()()(kTkkTkkAdddg第51頁/共72頁第五十二頁，共73頁。此此時(shí)時(shí)可可采采取取一一定定能能滿滿足足停停止止條條件件，算算法法在在有有限限步步迭迭代代后后不不)3(如如下下措措施施：沒沒有有求求成成一一輪輪搜搜索索后后，如如果果還還次次迭迭代代為為一一輪輪，每每次次完完以以n新的初始點(diǎn)，新的初始點(diǎn)，的最后一個(gè)迭代點(diǎn)作為的最后一個(gè)迭代點(diǎn)作為得極小點(diǎn)，則以上一輪得極小點(diǎn)，則以上一輪一輪搜索。一輪搜索。一個(gè)搜索方向，開始下一個(gè)搜索方向，開始下取最速下降方向作為第取最速下降方向作為第注注，如如算算采采用用其其它它形形式式的的公公式式計(jì)計(jì)在

47、在共共軛軛梯梯度度法法中中，也也可可i 。）共軛梯度法共軛梯度法PRPgggggiTiiiTii()(11 第52頁/共72頁第五十三頁，共73頁。10.3 共軛梯度法共軛梯度法 10.3.2 共軛梯度法共軛梯度法 共軛梯度法最初由Hesteness和Stiefel于1952年為求解線性方程組而提出.后來,人們把這種方法用于求解無約束最優(yōu)化問題,使之成為一種重要的最優(yōu)化方法. 下面,重點(diǎn)介紹Fletcher-Reeves共軛梯度法共軛梯度法,簡(jiǎn)稱FR法法. 共軛梯度法的基本思想基本思想是把共軛性與最速下降方法相結(jié)合,利用已知點(diǎn)處的梯度構(gòu)造一組共軛方向,并沿這組方向進(jìn)行搜索,求出目標(biāo)函數(shù)的極小點(diǎn)

48、.根據(jù)共軛方向的基本性質(zhì),這種方法具有二次終止性. 我們先討論對(duì)于二次凸函數(shù)的共軛梯度法,然后再把這種方法推廣到極小化一般函數(shù)的情形. 考慮問題第53頁/共72頁第五十四頁，共73頁。cxbAxxxfTT21)(min其中 , 是對(duì)稱正定矩陣, 是常數(shù).nExAc 具體求解方法如下: 首先,任意給定一個(gè)初始點(diǎn) ,計(jì)算出目標(biāo)函數(shù) 在這點(diǎn)的梯度,若 ,則停止計(jì)算;否則,令)1(x)(xf01g1)1()1()(gxfd(10.3.12)沿方向 搜索,得到點(diǎn) .計(jì)算在 處的梯度,若 ,則利用 和 構(gòu)造第2個(gè)搜索方向 ,再沿 搜索.)1(d)2(x)2(x02g2g)1(d)2(d)2(d 一般地,若

49、已知點(diǎn) 和搜索方向 ,則從 出發(fā),沿 進(jìn)行搜索,得到)(kx)(kd)(kx)(kd)()()1(kkkkdxx(10.3.14)第54頁/共72頁第五十五頁，共73頁。其中步長 滿足k)(min)()()()()(kkkkkdxfdxf我們可以求出 的顯式表達(dá).令k)()()()(kkdxf求 的極小點(diǎn),令)(0)()()()1(kTkdxf(10.3.15)根據(jù)二次函數(shù)的梯度的表達(dá)式,(6.3.15)即00(0)()()()()()()()1(kTkkkkTkkkkTkdAdgdbdxAdbAx(10.3.16)第55頁/共72頁第五十六頁，共73頁。由(6.3.16)得到)()()(kT

50、kkTkkAdddg(10.3.17) 計(jì)算 在 處的梯度.若 ,則停止計(jì)算;否則,用共軛.按此設(shè)想,令)(xf)1( kx01kgAddddgkkkkk關(guān)于和，并使構(gòu)造下一個(gè)搜索方向和)()1()1()(1)(1)1(kkkkdgd(10.3.18)上式兩端左乘 ,并令0)()(1)()1()(kTkkkTkkTkAddAgdAdd由此得到AdTk)()()(1)(kTkkTkkAddAgd(10.3.19)第56頁/共72頁第五十七頁，共73頁。 再從 出發(fā),沿方向 搜索.)1( kx)1( kd綜上分析，在第個(gè)搜索方向取負(fù)梯度的前提下, 重復(fù)使用公式(10.3.14),(10.3.17)

51、,(10.3.18)和(10.3.19),就能伴隨計(jì)算點(diǎn)的增加,構(gòu)造出一組搜索方向.下面將要證明,這組方向是關(guān)于 共軛的.因此,上述方法具有二次終止性.A 定理定理10.3.3 對(duì)于正定二次函數(shù)(10.3.12),具有精確一維搜索的Fletcher-Reeves法在 次一維搜索后即終止，并且對(duì)所有 ,下列關(guān)系成立:nm )1 (mii)0(. 31, 2 , 10. 21, 2 , 10. 1)()()(iiTiiTijTijTidggdgijggijAdd蘊(yùn)涵第57頁/共72頁第五十八頁，共73頁。 例例6.3.1 考慮下列問題：2322212121minxxx 取初始點(diǎn)和初始搜索方向分別為

52、021111)1()1(dx和 在FR法中，初始搜索方向必須取最速下降方向初始搜索方向必須取最速下降方向，這一點(diǎn)絕不可忽視。 對(duì)于二次凸函數(shù)，F(xiàn)R法的計(jì)算步驟計(jì)算步驟如下： 1.給定初始點(diǎn) ,置 .)1(x1k第58頁/共72頁第五十九頁，共73頁。 2.計(jì)算 ,若 ,則停止計(jì)算,得點(diǎn) ;否則,進(jìn)行下一步.)()(kkxfg0kg)(kxx 3.構(gòu)造搜索方向,令)1(1)(kkkkdgd其中,當(dāng) 時(shí), ,當(dāng) 時(shí),按公式 1k01k1k)0, 1(221iiiigigg計(jì)算因子 .1k 4.令)()()1(kkkkdxx其中按公式(6.3.17)計(jì)算步長k第59頁/共72頁第六十頁，共73頁。

53、5.若 ,則停止計(jì)算,得點(diǎn) ;否則,置 ,返回步2.nk )1( kxx1: kk 由第60頁/共72頁第六十一頁，共73頁。10.4 擬牛頓擬牛頓(ni dn)法法 6.4.1 擬牛頓(ni dn)條件前面(qin mian)介紹了牛頓法,它的突出優(yōu)點(diǎn)是收斂很快.但是,運(yùn)用牛頓法需要計(jì)算二階便導(dǎo)數(shù),而且目標(biāo)函數(shù)的Hessian矩陣可能非正定.為了克服牛頓法的缺點(diǎn),人們提出了擬牛頓法.它的基本思想是用不包含二階導(dǎo)數(shù)的矩陣近似牛頓法中的Hessian矩陣的逆矩陣.第61頁/共72頁第六十二頁，共73頁。 Newton法的優(yōu)缺點(diǎn)(qudin)都很突出。 優(yōu)點(diǎn)：高收斂速度（二階收斂）； 缺點(diǎn)(qud

54、in)：對(duì)初始點(diǎn)、目標(biāo)函數(shù)要求高，計(jì)算量、存儲(chǔ)量大（需要計(jì)算、存儲(chǔ)Hesse矩陣及其逆）。 擬Newton法是模擬(mn)Newton法給出的一個(gè)保優(yōu)去劣的算法 擬Newton法是效果很好的一大類方法。它當(dāng)中的DFP算法和BFGS算法是直到目前為止在不用Hesse矩陣(j zhn)的方法中的最好方法。第62頁/共72頁第六十三頁，共73頁。矩陣。點(diǎn)處的在點(diǎn)為此處HessexxfxfGkkk)()(2)()(第63頁/共72頁第六十四頁，共73頁。式：擬牛頓法的基本迭代公kkkkkkkgHddxx)()()()1(,)(-)(kkkxfgH為對(duì)稱矩陣，其中為下降方向：要求)() 1 (kd0-)(kkTkkTkgHgdg為正定矩陣故要求kHk