使用導(dǎo)數(shù)的最優(yōu)化方法.ppt

1、第10章 使用導(dǎo)數(shù)的最優(yōu)化方法,無(wú)約束最優(yōu)化問(wèn)題,2. 最速下降法,4.共軛梯度法 5.擬牛頓法,3. 牛頓法,一. 無(wú)約束最優(yōu)化問(wèn)題,無(wú)約束非線性規(guī)劃問(wèn)題的求解方法分為解析法和直接法兩類。,解析法 需要計(jì)算函數(shù)的梯度，利用函數(shù)的解析性質(zhì)構(gòu)造迭代公式使之收斂到最優(yōu)解。本節(jié)介紹最速下降法、共軛梯度法、牛頓法、變尺度法等解析方法,直接法 僅通過(guò)比較目標(biāo)函數(shù)值的大小來(lái)移動(dòng)迭代點(diǎn)。下一章主要介紹模式搜索法等直接方法。,無(wú)約束非線性規(guī)劃問(wèn)題的求解方法分為解析法和直接法兩類。,一般來(lái)說(shuō)，無(wú)約束非線性規(guī)劃問(wèn)題的求解是通過(guò)一系列一維搜索來(lái)實(shí)現(xiàn)。因此，如何選擇搜索方向是解無(wú)約束非線性規(guī)劃問(wèn)題的核心問(wèn)題，搜索方向

2、的不同選擇，形成不同的求解方法。,本章主要介紹解析法;另一類只用到目標(biāo)函數(shù)值,不必計(jì)算導(dǎo)數(shù),通常稱為直接方法,放在第11章討論.,本章考慮如下的下降算法：,主要介紹最速下降法、牛頓法，共軛梯度法，擬牛頓法等,其中函數(shù) 具有一階連續(xù)偏導(dǎo)數(shù). 人們?cè)谔幚磉@類問(wèn)題時(shí),總希望從某一點(diǎn)出發(fā),選擇一個(gè)目標(biāo)函數(shù)值下降最快的方向,以利于盡快達(dá)到極小點(diǎn).正是基于這樣一種愿望,早在1847年法國(guó)著名數(shù)學(xué)家Cauchy提出了最速下降法.后來(lái),Curry等人作了進(jìn)一步的研究.現(xiàn)在最速下降法已經(jīng)成為眾所周知的一種最基本的算法,它對(duì)其他算法的研究也很有啟發(fā)作用,因此在最優(yōu)化方法中占有重要地位.下面我們先來(lái)討論怎樣選擇最速

3、下降方向.,解：,第二次迭代：,第三次迭代：,在最速下降法的一位搜素中,即在最速下降法中相鄰兩次搜索方向是正交的。,對(duì)于二次嚴(yán)格凸函數(shù),其中A為n維對(duì)稱正定矩陣,可以求出步長(zhǎng)因子k,（本章習(xí)題7）,鋸齒現(xiàn)象,最速下降法的迭代點(diǎn)在向極小點(diǎn)靠近的過(guò)程中，走的是曲折的路線：后一次搜索方向d(k+1)與前一次搜索方向 d(k),總是相互垂直的，稱它為鋸齒現(xiàn)象。這一點(diǎn)在前面的例題中已得到驗(yàn)證。除極特殊的目標(biāo)函數(shù)（如等值面為球面的函數(shù)）和極特殊的初始點(diǎn)外，這種現(xiàn)象一般都要發(fā)生。,最速下降法的收斂性,從直觀上可以看到，在遠(yuǎn)離極小點(diǎn)的地方，每次迭代都有可能使目標(biāo)函數(shù)值有較多的下降，但在接近極小點(diǎn)的地方，由于鋸

4、齒現(xiàn)象，每次迭代行進(jìn)的距離開(kāi)始逐漸變小。因而收斂速度不快。,已有結(jié)論表明，最速下降法對(duì)于正定二次函數(shù)關(guān)于任意初始點(diǎn)都是收斂的(定理10.1.2)，而且恰好是線性收斂的。,則牛頓法產(chǎn)生的序列收斂于 .,實(shí)際上,當(dāng)牛頓法收斂時(shí),有下列關(guān)系:,其中 C 是某個(gè)常數(shù).因此,牛頓法至少2級(jí)收斂,參看文獻(xiàn)19.可見(jiàn)牛頓法的收斂速率是很快的.,例10.2.1 用牛頓法解下列問(wèn)題:,我們?nèi)〕觞c(diǎn),解：,第2次迭代：,第2次迭代：,繼續(xù)迭代，得到,最終收斂到最優(yōu)解x*=(1,0)T,我們先用極值條件求解.令,下面用牛頓法求解. 任取初始點(diǎn)x(1) , 根據(jù)牛頓法的迭代公式：,特別地,對(duì)于二次凸函數(shù),用牛頓法求解,

5、經(jīng)1次迭代即達(dá)極小點(diǎn).,設(shè)有二次凸函數(shù),其中A是對(duì)稱正定矩陣。,求迭代點(diǎn)x(2),即1次迭代達(dá)到極小點(diǎn).,對(duì)于二次凸函數(shù),用牛頓法求解,經(jīng)1次迭代即達(dá)極小點(diǎn),10.3、共軛梯度法,10.3.1 共軛方向法,1. 共軛方向和共軛方向法,共軛是正交的推廣。,幾何意義,幾何意義,推論：,共軛方向法,對(duì)于上述正交方向法，它是下降算法嗎？,不難得到：,故正交方向法，它是下降算法。,可由一組線性無(wú)關(guān)向量組，類似于schmidt正交化過(guò)程，,10.3.2. 共軛梯度法,如何選取一組共軛方向？,以下分析算法的具體步驟。,我們先討論對(duì)于二次凸函數(shù)的共軛梯度法,然后再把這種方法推廣到極小化一般函數(shù)的情形,初始搜索

6、方向?yàn)樽钏傧陆捣较?常用兩個(gè)公式: 著名的FR和PPR公式,求解二次凸規(guī)劃的FR 共軛梯度法,求解二次凸規(guī)劃的FR 共軛梯度法迭代多少次才可以達(dá)到最優(yōu)解？,10.3.3. 用于一般函數(shù)的共軛梯度法,10.3.3. 用于一般函數(shù)的共軛梯度法,10.4 擬牛頓法,6.4.1 擬牛頓條件,前面介紹了牛頓法,它的突出優(yōu)點(diǎn)是收斂很快.但是,運(yùn)用牛頓法需要計(jì)算二階便導(dǎo)數(shù),而且目標(biāo)函數(shù)的Hessian矩陣可能非正定.為了克服牛頓法的缺點(diǎn),人們提出了擬牛頓法.它的基本思想是用不包含二階導(dǎo)數(shù)的矩陣近似牛頓法中的Hessian矩陣的逆矩陣.,Newton法的優(yōu)缺點(diǎn)都很突出。 優(yōu)點(diǎn)：高收斂速度（二階收斂）； 缺點(diǎn)：對(duì)初始點(diǎn)、目標(biāo)函數(shù)要求高，計(jì)算量、存儲(chǔ)量大（需要計(jì)算、存儲(chǔ)Hesse矩陣及其逆）。,擬Newton法是模擬Newton法給出的一個(gè)保優(yōu)去劣的算法,擬Newton法是效果很好的一大類方法。它當(dāng)中的DFP算法和BFGS算法是直到目前為止在不用Hesse矩陣的方法中的最好方法。,由于構(gòu)造近似矩陣的方法不同,因而出現(xiàn)不同的擬牛頓法.經(jīng)理論證明和實(shí)踐檢驗(yàn),擬牛