




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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),擬牛
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 綿陽(yáng)綠卡服務(wù)管理辦法
- 宜昌物業(yè)收費(fèi)管理辦法
- 托管機(jī)構(gòu)配送管理辦法
- 育兒健康教育課件
- 肥鄉(xiāng)實(shí)驗(yàn)中學(xué)消防課件
- 套管培訓(xùn)大綱課件
- 腸癌化療護(hù)理
- 網(wǎng)球培訓(xùn)教程課件圖片
- 對(duì)口高考最難數(shù)學(xué)試卷
- 高中1到9章的數(shù)學(xué)試卷
- 大廈工程施工設(shè)計(jì)方案
- 2025-2030中國(guó)電力設(shè)備檢測(cè)行業(yè)市場(chǎng)深度調(diào)研及發(fā)展前景與投融資戰(zhàn)略規(guī)劃研究報(bào)告
- 2025至2030年中國(guó)不銹鋼蝕刻板數(shù)據(jù)監(jiān)測(cè)研究報(bào)告
- DB42T743-2016 高性能蒸壓砂加氣混凝土砌塊墻體自保溫系統(tǒng)應(yīng)用技術(shù)規(guī)程
- 軟件研發(fā)行業(yè)安全生產(chǎn)培訓(xùn)
- 《供應(yīng)鏈管理法律風(fēng)險(xiǎn)》課件
- 兒童專注力訓(xùn)練300題可打印
- 2025年度工業(yè)園區(qū)物業(yè)管理及服務(wù)收費(fèi)標(biāo)準(zhǔn)及細(xì)則
- 三升四數(shù)學(xué)暑假思維訓(xùn)練題答案
- 2024-2030年中國(guó)橋梁管理與養(yǎng)護(hù)市場(chǎng)調(diào)查研究及發(fā)展趨勢(shì)分析報(bào)告
- 山東省菏澤市2023-2024學(xué)年高一下學(xué)期7月期末考試 政治 含解析
評(píng)論
0/150
提交評(píng)論