最優(yōu)化方法第一次基礎(chǔ)知識(shí)

1、最優(yōu)化方法最優(yōu)化方法 1.1.教教 材：最優(yōu)化理論與方法材：最優(yōu)化理論與方法 陳寶林，清華大學(xué)出版社陳寶林，清華大學(xué)出版社2.2.參考書：最優(yōu)化原理與方法參考書：最優(yōu)化原理與方法 薛嘉慶，冶金工業(yè)出版社薛嘉慶，冶金工業(yè)出版社 基本知識(shí)基本知識(shí)一一. .引言引言四四. .極值最優(yōu)化問題的經(jīng)典方法極值最優(yōu)化問題的經(jīng)典方法二二. .最優(yōu)化問題實(shí)例最優(yōu)化問題實(shí)例三三. .最優(yōu)化問題及基本概念最優(yōu)化問題及基本概念五五. .圖解法圖解法六六. .梯度與梯度與HesseHesse陣陣七七. .TaylorTaylor展開式展開式八八. .凸集與凸函數(shù)凸集與凸函數(shù)九九. .極小點(diǎn)的判定條件極小點(diǎn)的判定條件十十

2、. .算法及相關(guān)概念算法及相關(guān)概念十一十一. .中止條件中止條件十二十二. .收斂速度收斂速度一一. 引言引言1. 1. 最優(yōu)化定義最優(yōu)化定義最優(yōu)化是從所有可行方案中選擇最合理方案以達(dá)到最優(yōu)目標(biāo)最優(yōu)化是從所有可行方案中選擇最合理方案以達(dá)到最優(yōu)目標(biāo)的一門學(xué)科。的一門學(xué)科。（1 1） 達(dá)到最優(yōu)目標(biāo)的方案：最優(yōu)方案（最優(yōu)解）達(dá)到最優(yōu)目標(biāo)的方案：最優(yōu)方案（最優(yōu)解）（2 2） 搜尋最優(yōu)方案的方法：最優(yōu)化方法搜尋最優(yōu)方案的方法：最優(yōu)化方法最優(yōu)化問題：尋求某些變量的取值使其符合某些限制條件，最優(yōu)化問題：尋求某些變量的取值使其符合某些限制條件，并使某個(gè)目標(biāo)函數(shù)達(dá)到最大值或最小值的問題。并使某個(gè)目標(biāo)函數(shù)達(dá)到最大

3、值或最小值的問題。 一般的數(shù)學(xué)形式為：一般的數(shù)學(xué)形式為：上上的的函函數(shù)數(shù)為為定定義義在在集集合合其其中中DxfDxtsxf)(.,)(min 2. 2. 發(fā)展簡(jiǎn)況發(fā)展簡(jiǎn)況q經(jīng)典最優(yōu)化理論的研究已有很久，最早可追溯到經(jīng)典最優(yōu)化理論的研究已有很久，最早可追溯到FermatFermat時(shí)代。時(shí)代。q19401940年前，對(duì)多變量函數(shù)的數(shù)值最優(yōu)化方法知之年前，對(duì)多變量函數(shù)的數(shù)值最優(yōu)化方法知之甚少，但當(dāng)時(shí)已發(fā)現(xiàn)了若干最小二乘法和在物理上甚少，但當(dāng)時(shí)已發(fā)現(xiàn)了若干最小二乘法和在物理上應(yīng)用的最速下降法，多變量的牛頓法也很著名。應(yīng)用的最速下降法，多變量的牛頓法也很著名。q 40 40年代與年代與5050年代：線

4、性規(guī)劃（年代：線性規(guī)劃（LPLP）的發(fā)展。的發(fā)展。q 二戰(zhàn)以后，爬山法得到發(fā)展與應(yīng)用（實(shí)用，粗糙）。二戰(zhàn)以后，爬山法得到發(fā)展與應(yīng)用（實(shí)用，粗糙）。q 1959 1959年，年，W-W-C.DavidonC.Davidon的一個(gè)報(bào)告引入了變尺度方的一個(gè)報(bào)告引入了變尺度方 法。法。3.3.應(yīng)用領(lǐng)域應(yīng)用領(lǐng)域工程設(shè)計(jì)、軍事科學(xué)、自動(dòng)控制、空間技術(shù)、資源工程設(shè)計(jì)、軍事科學(xué)、自動(dòng)控制、空間技術(shù)、資源分配、計(jì)算機(jī)科學(xué)等等。例如：分配、計(jì)算機(jī)科學(xué)等等。例如：橋梁結(jié)構(gòu)設(shè)計(jì)；橋梁結(jié)構(gòu)設(shè)計(jì)；運(yùn)輸問題；運(yùn)輸問題；參數(shù)擬合；參數(shù)擬合；多波形信號(hào)發(fā)生儀中正弦波形逼近的優(yōu)化設(shè)計(jì)，多波形信號(hào)發(fā)生儀中正弦波形逼近的優(yōu)化設(shè)計(jì)，在

5、在 中找中找 n n 個(gè)分點(diǎn)，使過這些分點(diǎn)的折線和個(gè)分點(diǎn)，使過這些分點(diǎn)的折線和正弦函數(shù)曲線的誤差最小。正弦函數(shù)曲線的誤差最小。 2,04.4.包含內(nèi)容：包含內(nèi)容：最優(yōu)化又稱數(shù)學(xué)規(guī)劃：最優(yōu)化又稱數(shù)學(xué)規(guī)劃： LPLP、NLPNLP、DPDP、IPIP5.5.分類：分類： 多多目目標(biāo)標(biāo)動(dòng)動(dòng)態(tài)態(tài)問問題題非非線線性性規(guī)規(guī)劃劃線線性性規(guī)規(guī)劃劃有有約約束束問問題題無無約約束束問問題題靜靜態(tài)態(tài)問問題題單單目目標(biāo)標(biāo)最最優(yōu)優(yōu)化化問問題題二二. . 最優(yōu)化問題實(shí)例最優(yōu)化問題實(shí)例例例1 1：多參數(shù)曲線擬合問題：多參數(shù)曲線擬合問題已知熱電阻已知熱電阻 R 依賴于溫度依賴于溫度 t 的函數(shù)關(guān)系為：的函數(shù)關(guān)系為：其中其中

6、是待定參數(shù)。通過試驗(yàn)，得到是待定參數(shù)。通過試驗(yàn)，得到it ti iR Ri i1 1505034780347802 2555528610286103 360602365023650。151512012033073307利用最小二乘思想，可將其化為三維空間的無約束最優(yōu)化利用最小二乘思想，可將其化為三維空間的無約束最優(yōu)化問題，即：?jiǎn)栴}，即： 321expxtxxR321xx,x和和組組數(shù)數(shù)的的和和15Rt 1512321321exp),(miniiixtxxRxxxf現(xiàn)有現(xiàn)有 m 種資源的數(shù)量為種資源的數(shù)量為 。計(jì)劃生產(chǎn)。計(jì)劃生產(chǎn) n 種產(chǎn)種產(chǎn)品品1 1,2,2, ,n n。有關(guān)數(shù)據(jù)如下，試問：怎

7、樣安排生產(chǎn)可以使利有關(guān)數(shù)據(jù)如下，試問：怎樣安排生產(chǎn)可以使利潤(rùn)達(dá)大？潤(rùn)達(dá)大？mbbb,21產(chǎn)品擁有量 1 2 n 資源 1 2 m單位利潤(rùn)11a12ana121a22ana21ma2mamna1b2bmb1c2cnc令令 表示第表示第 j 種產(chǎn)品的產(chǎn)量。種產(chǎn)品的產(chǎn)量。jx njxmibxatsxcxfjinjjijnjjj,.,2 , 10,.,2 , 1.)(max11模模型型：例例2. 2. 生產(chǎn)安排問題生產(chǎn)安排問題已知有已知有m m個(gè)生產(chǎn)點(diǎn)個(gè)生產(chǎn)點(diǎn)B Bi i，可供應(yīng)某種物質(zhì)量分別為可供應(yīng)某種物質(zhì)量分別為 n n個(gè)銷地個(gè)銷地 ，需求量為需求量為 . . 從從 到到 的單的單位運(yùn)價(jià)為位運(yùn)價(jià)為

8、 。問：應(yīng)如何安排運(yùn)輸方案才能使總運(yùn)費(fèi)最?。?。問：應(yīng)如何安排運(yùn)輸方案才能使總運(yùn)費(fèi)最小？),2, 1(mibi ),2,1(njcj iBjCijajC例例3. 3. 運(yùn)輸問題（運(yùn)輸問題（TPTP）運(yùn)費(fèi) 銷 地產(chǎn)量 1 2 n 產(chǎn)地 1 2 m 銷量 11a12ana121a22ana21ma2mamna1b2bmb1c2cnc在產(chǎn)銷平衡條件下，要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，可得如下在產(chǎn)銷平衡條件下，要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，可得如下模型：模型：設(shè)設(shè) 表示從第表示從第i個(gè)產(chǎn)地向第個(gè)產(chǎn)地向第j個(gè)銷地的運(yùn)量，則有個(gè)銷地的運(yùn)量，則有ijx njmixnjcxmibxtsxazijjmiijinjijm

9、injijij,.,1,.,10,.,2,1,.,2,1.min1111三三. . 最優(yōu)化問題及基本概念最優(yōu)化問題及基本概念 0)(0)(.)(minxhxgtsxf pjxhmixgtsxfji，, 10)(, 10)(.)(minDxtsxf .)(min2.2.解法分類解法分類 解析方法：利用函數(shù)的解析性質(zhì)去構(gòu)造迭代公式使之收斂到最優(yōu)解（如牛頓法）。 直接方法：它對(duì)函數(shù)的解析性質(zhì)如可微性沒有要求，而是根據(jù)一定的數(shù)學(xué)原理來確定（如0.618法）。1.1.模型模型DxxfxfxDxNxxfxfxxxxxNxfxxfxT ),()(:),(),()(:|),()(,()(*0*00*全全局局最

10、最優(yōu)優(yōu)解解局局部部最最優(yōu)優(yōu)解解鄰鄰域域最最優(yōu)優(yōu)解解：最最優(yōu)優(yōu)值值：最最優(yōu)優(yōu)點(diǎn)點(diǎn)：3.3.全局最優(yōu)解與局部最優(yōu)解全局最優(yōu)解與局部最優(yōu)解四四. . 極值問題的經(jīng)典方法極值問題的經(jīng)典方法1.1.求駐點(diǎn)的方法求駐點(diǎn)的方法 000)()(1minnnRxxfxfxfxf 0)(0)()()(),(min0),(0),(.),(min12121121xhLxhxfxLxhxfxLxxxhxxxhtsxxxfliiilRnRxnlnn（2.Lagrange 2.Lagrange 乘子法乘子法五. 圖解法等值線（面）的特點(diǎn)：1.不同值的等值線不相交 ;2.除極值點(diǎn)外，等值線是連續(xù)曲線 ;3.等值線稠密處導(dǎo)數(shù)變

11、化快，稀疏處變化慢 ;六六. 梯度與梯度與Hesse陣陣1. 梯度梯度TnxfxfxfXf),.,()(21 性質(zhì)性質(zhì)1：函數(shù)在某點(diǎn)的梯度若不為：函數(shù)在某點(diǎn)的梯度若不為0， 則必與過該點(diǎn)的等值線則必與過該點(diǎn)的等值線（面）垂直。（面）垂直。x0Lf(X)=f(X0)f(X0)X0L性質(zhì)性質(zhì)2：梯度方向是函數(shù)值具有最大變化率的方向，即函數(shù)值：梯度方向是函數(shù)值具有最大變化率的方向，即函數(shù)值上升最快的方向。上升最快的方向。2. 方向?qū)?shù)和下降（上升）方向方向?qū)?shù)和下降（上升）方向（1）方向?qū)?shù)方向?qū)?shù)：|)()(lim)(0000ptxfptxfpxft 函數(shù)函數(shù) 在點(diǎn)在點(diǎn) 處沿著方向處沿著方向p 的

12、方向?qū)?shù)。的方向?qū)?shù)。)(xf0 x（2）給定函數(shù)）給定函數(shù) 和方向和方向p，如果存在實(shí)數(shù)如果存在實(shí)數(shù) ，使得對(duì)，使得對(duì)于任意的于任意的 ，都有，都有 ，則稱，則稱p為為 在在點(diǎn)點(diǎn) 處的下降方向。處的下降方向。)(xf0 t),0(t )()(0 xfpxfo )(xf0 x（3） 性質(zhì)性質(zhì) (a) . |)()(00ppxfpxfT (b) p是下降方向是下降方向; 0)(0pxf 0)(0pxf(c) p是下降方向。是下降方向。 0)(0pxfTp是上升方向。（4）常用梯度公式）常用梯度公式,0 c,)(bxbT ,2)(xxxT .2)(AxAxxT 3. Hesse矩陣矩陣（1）雅可比

13、矩陣：設(shè)雅可比矩陣：設(shè) )()()(1xgxgxgm，nmjinmmnxgxxgxxgxxgxxgxg )()()()()(1111（2）海賽（海賽（Hesse） 矩陣矩陣：nnjinnnnxxfxfxxfxxfxxfxxfxfxfxf 2221222122122122)()(（3）其它Ix 11AAx )()()(0tpxft ptpxftT)()(0 ptpxfptTT)()(02 01 ncc七七. Taylor展開式展開式)10(,)(21)()()()(21)()()(1222 pxxpxfppxfxfpopxfppxfxfpxfTTTT： )()(21)()()()(2002000

14、0 xxxfxxxxxfxfxfTT：八八. 凸集與凸函數(shù)凸集與凸函數(shù)1.凸集凸集（1）凸組合：已知凸組合：已知,nRX 任取k個(gè)點(diǎn) ， Xxi 如果存在常數(shù)0 ia，),2,1(ki 11 kiia，使得 xxakiii1，則稱 x為ix),2,1(ki 的凸組合。的凸組合。（2）凸集：設(shè)集合）凸集：設(shè)集合nRX ，如果X中任意兩點(diǎn)的凸組合仍然屬于X，則稱X為凸集。2.凸函數(shù)凸函數(shù)設(shè)設(shè)RRXfn :，任取任取Xxx 21,，如果如果1,0,2121 iiaaa，有有)()()(22112211xfaxfaxaxaf ，則稱則稱f為為X上的（嚴(yán)格）上的（嚴(yán)格）凸函數(shù)。凸函數(shù)。例子：例子： 2)

15、(xxf 水平集水平集： fXxxfxD,)(| 是凸函數(shù)是凸函數(shù)。性質(zhì)：水平集一定是凸集。性質(zhì)：水平集一定是凸集。3. 凸函數(shù)的性質(zhì)凸函數(shù)的性質(zhì)定理定理. 凸函數(shù)的局部極小點(diǎn)就是全局極小點(diǎn)。凸函數(shù)的局部極小點(diǎn)就是全局極小點(diǎn)。4. 凸函數(shù)的判斷條件凸函數(shù)的判斷條件定理定理1. )(xf是凸集是凸集X上的凸函數(shù)的充要條件是上的凸函數(shù)的充要條件是Xxx 21,，有，有)()()()(12112xxxfxfxfT .定理定理2.設(shè)設(shè))(xf在凸集在凸集X上有二階連續(xù)偏導(dǎo)數(shù)，則上有二階連續(xù)偏導(dǎo)數(shù)，則)(xf是凸是凸函數(shù)的充要條件是函數(shù)的充要條件是Xx ，有，有)(2xf 半正定。半正定。例：正定二次函

16、數(shù)例：正定二次函數(shù)cxbAxxxfTT 21)(，其中，其中A是正定矩陣。是正定矩陣。)(xf是凸函數(shù)。是凸函數(shù)。5. 凸規(guī)劃凸規(guī)劃（1）Dxtsxf .)(min其中其中)(xf是凸函數(shù)，是凸函數(shù)，D是凸集。是凸集。（2）)(minxf 0)(0)(0)(0)(.11xhxhxgxgtskl其中其中),2,1()(, )(lixgxfi 是線性函數(shù)是線性函數(shù).),2,1( )(kjxhj 是凸函數(shù)是凸函數(shù),6. 二次規(guī)劃二次規(guī)劃mnmnnnnTTRp,RA,Rc,Rb,RQ,RxxpAx. t . scxbQxx)x(fmin 1021這里這里九九. 極小點(diǎn)的判定條件極小點(diǎn)的判定條件（1）必

17、要條件：）必要條件：0)()(min)(xfxfxf（2）充分條件：）充分條件：0)(0)(2 xfxf)(min)(xfxf 2221xxo)xx)(x( f)xx()xx()x( f)x( f)x( fTT 02)x(f（3） 兩個(gè)結(jié)論兩個(gè)結(jié)論 函數(shù)在極小點(diǎn)附近的等值線為近似的同心橢圓。函數(shù)在極小點(diǎn)附近的等值線為近似的同心橢圓。有有唯唯一一的的極極值值點(diǎn)點(diǎn)：正正定定二二次次函函數(shù)數(shù)bQxcxbQxxxfTT1*21)( 十十. 算法及相關(guān)概念算法及相關(guān)概念1、迭代算法、迭代算法集合集合 D上的迭代算法上的迭代算法A： （1）初始點(diǎn)）初始點(diǎn)0 x；（2）按照某種規(guī)則）按照某種規(guī)則A產(chǎn)生下一個(gè)

18、迭代點(diǎn)產(chǎn)生下一個(gè)迭代點(diǎn))(1kkxAx 。（i）如果點(diǎn)列如果點(diǎn)列kx收斂于最優(yōu)解收斂于最優(yōu)解*x，則稱算法，則稱算法A收斂。收斂。（ii）如果如果 )()()(10kxfxfxf，則稱算法，則稱算法A為為下降迭代算法。下降迭代算法。.0 x.1x.2xD.3x2.下降迭代算法步驟下降迭代算法步驟（1）給出初始點(diǎn)）給出初始點(diǎn)0 x，令，令0 k；（2）按照某種規(guī)則確定下降搜索方向）按照某種規(guī)則確定下降搜索方向kd；（3）按照某種規(guī)則確定搜索步長(zhǎng)）按照某種規(guī)則確定搜索步長(zhǎng)k ，使得，使得)()(kkkkxfdxf ；（4）令）令kkkkdxx 1，1: kk；（5）判斷）判斷kx是否滿足停止條件。是則停止，否則轉(zhuǎn)第是否滿足停止條件。是則停止，否則轉(zhuǎn)第2步。步。搜索步長(zhǎng)確定方法：搜索步長(zhǎng)確定方法：)(min)(kkkkkdxfdxf 稱稱0)( kTkkkddxf 。k 為最優(yōu)步長(zhǎng)，且