




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、第10章 使用導數的最優(yōu)化方法,無約束最優(yōu)化問題,2. 最速下降法,4.共軛梯度法 5.擬牛頓法,3. 牛頓法,一. 無約束最優(yōu)化問題,無約束非線性規(guī)劃問題的求解方法分為解析法和直接法兩類。,解析法 需要計算函數的梯度,利用函數的解析性質構造迭代公式使之收斂到最優(yōu)解。本節(jié)介紹最速下降法、共軛梯度法、牛頓法、變尺度法等解析方法,直接法 僅通過比較目標函數值的大小來移動迭代點。下一章主要介紹模式搜索法等直接方法。,無約束非線性規(guī)劃問題的求解方法分為解析法和直接法兩類。,一般來說,無約束非線性規(guī)劃問題的求解是通過一系列一維搜索來實現。因此,如何選擇搜索方向是解無約束非線性規(guī)劃問題的核心問題,搜索方向
2、的不同選擇,形成不同的求解方法。,本章主要介紹解析法;另一類只用到目標函數值,不必計算導數,通常稱為直接方法,放在第11章討論.,本章考慮如下的下降算法:,主要介紹最速下降法、牛頓法,共軛梯度法,擬牛頓法等,其中函數 具有一階連續(xù)偏導數. 人們在處理這類問題時,總希望從某一點出發(fā),選擇一個目標函數值下降最快的方向,以利于盡快達到極小點.正是基于這樣一種愿望,早在1847年法國著名數學家Cauchy提出了最速下降法.后來,Curry等人作了進一步的研究.現在最速下降法已經成為眾所周知的一種最基本的算法,它對其他算法的研究也很有啟發(fā)作用,因此在最優(yōu)化方法中占有重要地位.下面我們先來討論怎樣選擇最速
3、下降方向.,解:,第二次迭代:,第三次迭代:,在最速下降法的一位搜素中,即在最速下降法中相鄰兩次搜索方向是正交的。,對于二次嚴格凸函數,其中A為n維對稱正定矩陣,可以求出步長因子k,(本章習題7),鋸齒現象,最速下降法的迭代點在向極小點靠近的過程中,走的是曲折的路線:后一次搜索方向d(k+1)與前一次搜索方向 d(k),總是相互垂直的,稱它為鋸齒現象。這一點在前面的例題中已得到驗證。除極特殊的目標函數(如等值面為球面的函數)和極特殊的初始點外,這種現象一般都要發(fā)生。,最速下降法的收斂性,從直觀上可以看到,在遠離極小點的地方,每次迭代都有可能使目標函數值有較多的下降,但在接近極小點的地方,由于鋸
4、齒現象,每次迭代行進的距離開始逐漸變小。因而收斂速度不快。,已有結論表明,最速下降法對于正定二次函數關于任意初始點都是收斂的(定理10.1.2),而且恰好是線性收斂的。,則牛頓法產生的序列收斂于 .,實際上,當牛頓法收斂時,有下列關系:,其中 C 是某個常數.因此,牛頓法至少2級收斂,參看文獻19.可見牛頓法的收斂速率是很快的.,例10.2.1 用牛頓法解下列問題:,我們取初點,解:,第2次迭代:,第2次迭代:,繼續(xù)迭代,得到,最終收斂到最優(yōu)解x*=(1,0)T,我們先用極值條件求解.令,下面用牛頓法求解. 任取初始點x(1) , 根據牛頓法的迭代公式:,特別地,對于二次凸函數,用牛頓法求解,
5、經1次迭代即達極小點.,設有二次凸函數,其中A是對稱正定矩陣。,求迭代點x(2),即1次迭代達到極小點.,對于二次凸函數,用牛頓法求解,經1次迭代即達極小點,10.3、共軛梯度法,10.3.1 共軛方向法,1. 共軛方向和共軛方向法,共軛是正交的推廣。,幾何意義,幾何意義,推論:,共軛方向法,對于上述正交方向法,它是下降算法嗎?,不難得到:,故正交方向法,它是下降算法。,可由一組線性無關向量組,類似于schmidt正交化過程,,10.3.2. 共軛梯度法,如何選取一組共軛方向?,以下分析算法的具體步驟。,我們先討論對于二次凸函數的共軛梯度法,然后再把這種方法推廣到極小化一般函數的情形,初始搜索
6、方向為最速下降方向,常用兩個公式: 著名的FR和PPR公式,求解二次凸規(guī)劃的FR 共軛梯度法,求解二次凸規(guī)劃的FR 共軛梯度法迭代多少次才可以達到最優(yōu)解?,10.3.3. 用于一般函數的共軛梯度法,10.3.3. 用于一般函數的共軛梯度法,10.4 擬牛頓法,6.4.1 擬牛頓條件,前面介紹了牛頓法,它的突出優(yōu)點是收斂很快.但是,運用牛頓法需要計算二階便導數,而且目標函數的Hessian矩陣可能非正定.為了克服牛頓法的缺點,人們提出了擬牛頓法.它的基本思想是用不包含二階導數的矩陣近似牛頓法中的Hessian矩陣的逆矩陣.,Newton法的優(yōu)缺點都很突出。 優(yōu)點:高收斂速度(二階收斂); 缺點:對初始點、目標函數要求高,計算量、存儲量大(需要計算、存儲Hesse矩陣及其逆)。,擬Newton法是模擬Newton法給出的一個保優(yōu)去劣的算法,擬Newton法是效果很好的一大類方法。它當中的DFP算法和BFGS算法是直到目前為止在不用Hesse矩陣的方法中的最好方法。,由于構造近似矩陣的方法不同,因而出現不同的擬牛頓法.經理論證明和實踐檢驗,擬牛
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 服裝展會推廣活動方案
- 普法活動招募活動方案
- 最籃球活動方案
- 朱砂首飾活動方案
- 晉安軍訓活動方案
- 智力徽章活動策劃方案
- 棗陽學校家訪活動方案
- 春蕾計劃活動方案
- 普惠營銷活動方案
- 村鎮(zhèn)環(huán)保實踐活動方案
- 商洛學院《大學學術綜合英語》2023-2024學年第二學期期末試卷
- 遼寧省沈陽市2023?2024學年高二下冊期末考試數學試卷2附解析
- 2025年高考英語全國二卷聽力試題答案詳解講解(課件)
- 廚師三級考試試題及答案
- 高級采氣工理論練習卷附答案
- 一例膿毒性休克個案護理
- 國開電大【管理英語3單元自測1-8答案】+【管理英語4形考任務單元自測1-8答案】
- 智能藥盒創(chuàng)新創(chuàng)業(yè)計劃書
- 生化檢驗員職業(yè)技能競賽理論考試題庫500題(含答案)
- 護理小組文化建設與管理
- 2025年4月自考00226知識產權法試題及答案含評分標準
評論
0/150
提交評論