最優(yōu)化理論算法及工程應(yīng)用

1、Page 2第一章第一章 預(yù)備知識(shí)預(yù)備知識(shí)最優(yōu)化問(wèn)題最優(yōu)化問(wèn)題方向?qū)?shù)與極值問(wèn)題方向?qū)?shù)與極值問(wèn)題泰勒級(jí)數(shù)問(wèn)題泰勒級(jí)數(shù)問(wèn)題凸集、凸函數(shù)與凸優(yōu)化問(wèn)題凸集、凸函數(shù)與凸優(yōu)化問(wèn)題算法概述算法概述Page 31.最優(yōu)化問(wèn)題最優(yōu)化問(wèn)題最優(yōu)化定義最優(yōu)化定義: 最優(yōu)化是從所有可能方案中選擇最合理方案以達(dá)到最優(yōu)目最優(yōu)化是從所有可能方案中選擇最合理方案以達(dá)到最優(yōu)目標(biāo)的一門(mén)學(xué)科。標(biāo)的一門(mén)學(xué)科。最優(yōu)化問(wèn)題最優(yōu)化問(wèn)題： 尋求某些變量的取值使其符合某些限制條件，并使某個(gè)目尋求某些變量的取值使其符合某些限制條件，并使某個(gè)目標(biāo)函數(shù)達(dá)到最大值或最小值的問(wèn)題。標(biāo)函數(shù)達(dá)到最大值或最小值的問(wèn)題。最優(yōu)化方法包括: 線性規(guī)劃、非線性規(guī)劃

2、、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃、多目標(biāo)規(guī)劃、組合優(yōu)化等等。Page 41.最優(yōu)化問(wèn)題的發(fā)展最優(yōu)化問(wèn)題的發(fā)展n 最優(yōu)化問(wèn)題可以追溯至最優(yōu)化問(wèn)題可以追溯至17世紀(jì)法國(guó)數(shù)學(xué)家拉格朗日關(guān)世紀(jì)法國(guó)數(shù)學(xué)家拉格朗日關(guān)于一個(gè)函數(shù)在一組等式約束條件下的極值問(wèn)題于一個(gè)函數(shù)在一組等式約束條件下的極值問(wèn)題 (求解多元求解多元函數(shù)極值的函數(shù)極值的 Lagrange 乘數(shù)法乘數(shù)法 )。n 19 世紀(jì)柯西引入了最速下降法求解非線性規(guī)劃問(wèn)題。世紀(jì)柯西引入了最速下降法求解非線性規(guī)劃問(wèn)題。n 20 20世紀(jì)三、四十年代線性規(guī)劃世紀(jì)三、四十年代線性規(guī)劃(LP)理論的引入使得優(yōu)理論的引入使得優(yōu)化理論的研究出現(xiàn)了重大進(jìn)展?；碚摰难芯砍霈F(xiàn)了重大

3、進(jìn)展。 n 1951年庫(kù)恩和塔克給出了非線性規(guī)劃年庫(kù)恩和塔克給出了非線性規(guī)劃(NLP)的最優(yōu)性的最優(yōu)性條件。條件。n 隨著計(jì)算機(jī)技術(shù)的發(fā)展，各種最優(yōu)化算法應(yīng)運(yùn)而生。隨著計(jì)算機(jī)技術(shù)的發(fā)展，各種最優(yōu)化算法應(yīng)運(yùn)而生。 Page 5最優(yōu)化問(wèn)題的數(shù)學(xué)模型一般形式1 . 1 . 1 Ds.t.x f(x),min 2 . 1 . 1, 2 , 1, 0. .mixct si 3 . 1 . 1, 1, 0pmixci 其中其中nTnRxxxx,21（目標(biāo)函數(shù)）（目標(biāo)函數(shù)） （等式約束）（等式約束）（不等式約束）（不等式約束）Page 62.n元函數(shù)的Taylor公式n 一元函數(shù)的泰勒展開(kāi)式：一元函數(shù)的泰勒

4、展開(kāi)式： 設(shè)函數(shù)在定義域內(nèi)連續(xù)可微，則有設(shè)函數(shù)在定義域內(nèi)連續(xù)可微，則有凸集、凸函數(shù)與凸優(yōu)化問(wèn)凸集、凸函數(shù)與凸優(yōu)化問(wèn)題題20000( )0()()()()2!()!nnnfxf xxf xfxxxfxxRn 10,)!1()(10)1(nnnxnxxfR 其中其中Page 7n 二元函數(shù)的二元函數(shù)的Taylor展式：展式：),(),(),(000000yxfyyxxyxfyyxxf2000011(,)(,)2!nnxyf xyxyf xyRxynxy10),()!1(1001yyxxfyyxxnRnn其中其中Page 83.函數(shù)的方向?qū)?shù)與極值問(wèn)題函數(shù)的方向?qū)?shù)與極值問(wèn)題n 目標(biāo)函數(shù)的等值面（線

5、）目標(biāo)函數(shù)的等值面（線）對(duì)于簡(jiǎn)單的問(wèn)題，可用等值線或等值面來(lái)描述函數(shù)的對(duì)于簡(jiǎn)單的問(wèn)題，可用等值線或等值面來(lái)描述函數(shù)的變化趨勢(shì)，還可以直觀地給出極值點(diǎn)的位置。變化趨勢(shì)，還可以直觀地給出極值點(diǎn)的位置。 1）目標(biāo)函數(shù)的等值面，其數(shù)學(xué)表達(dá)式為）目標(biāo)函數(shù)的等值面，其數(shù)學(xué)表達(dá)式為f(x)=c。 在這種線或面上所有點(diǎn)的函數(shù)值均相等，因此，這種線或在這種線或面上所有點(diǎn)的函數(shù)值均相等，因此，這種線或面就稱為函數(shù)的等值線或等值面。面就稱為函數(shù)的等值線或等值面。當(dāng)當(dāng)c取一系列不同的常數(shù)值時(shí)，可以得到一組形態(tài)相取一系列不同的常數(shù)值時(shí)，可以得到一組形態(tài)相似的等值線或等值面，稱為函數(shù)的等值線簇或等值面簇。似的等值線或等值

6、面，稱為函數(shù)的等值線簇或等值面簇。Page 9函數(shù)的方向?qū)?shù)與極值問(wèn)題函數(shù)的方向?qū)?shù)與極值問(wèn)題2）當(dāng)）當(dāng)n=2時(shí)，該點(diǎn)集是設(shè)計(jì)平面中的一條直線或曲線。時(shí)，該點(diǎn)集是設(shè)計(jì)平面中的一條直線或曲線。 例例1： 目標(biāo)函數(shù)目標(biāo)函數(shù)f(x)一一60 x1一一120 x2的等值線族。的等值線族。 這是一組相互平行的直線，函數(shù)值沿箭頭所指方間逐漸下這是一組相互平行的直線，函數(shù)值沿箭頭所指方間逐漸下降。如圖所示。降。如圖所示。凸集、凸函數(shù)與凸優(yōu)化問(wèn)凸集、凸函數(shù)與凸優(yōu)化問(wèn)題題Page 10函數(shù)的方向?qū)?shù)與極值問(wèn)題函數(shù)的方向?qū)?shù)與極值問(wèn)題3）當(dāng)）當(dāng)n=3時(shí)，該點(diǎn)集是設(shè)計(jì)空間中的一個(gè)平面或曲面。時(shí)，該點(diǎn)集是設(shè)計(jì)空間中的

7、一個(gè)平面或曲面。例例2 函數(shù)函數(shù) 的圖形的圖形(旋轉(zhuǎn)拋物面旋轉(zhuǎn)拋物面)，以及用平，以及用平面面f(X)c切割該拋物面所得交線在設(shè)計(jì)空間中的投影。切割該拋物面所得交線在設(shè)計(jì)空間中的投影。如圖所示。如圖所示。4）當(dāng)）當(dāng)n大于大于3時(shí)，該點(diǎn)集是設(shè)計(jì)空間時(shí)，該點(diǎn)集是設(shè)計(jì)空間 中的一個(gè)超曲面。中的一個(gè)超曲面。4十4x一x十xf(x)12221Page 11函數(shù)的方向?qū)?shù)與極值問(wèn)題函數(shù)的方向?qū)?shù)與極值問(wèn)題n 方向?qū)?shù)方向?qū)?shù) 討論函數(shù)討論函數(shù) 在一點(diǎn)在一點(diǎn)P沿某一方向的變化率問(wèn)題。沿某一方向的變化率問(wèn)題。 如果函數(shù)在點(diǎn)如果函數(shù)在點(diǎn) 是可微分的，那末函數(shù)在該點(diǎn)沿任意是可微分的，那末函數(shù)在該點(diǎn)沿任意方向方向L

8、的方向?qū)?shù)都存在，且有的方向?qū)?shù)都存在，且有 其中其中 為為x軸到方向軸到方向L的轉(zhuǎn)角的轉(zhuǎn)角), ( yxfz),(yxPsincosyfxflfPage 12函數(shù)的方向?qū)?shù)與極值問(wèn)題函數(shù)的方向?qū)?shù)與極值問(wèn)題n 梯度梯度 函數(shù)在一點(diǎn)的梯度是這樣一個(gè)向量函數(shù)在一點(diǎn)的梯度是這樣一個(gè)向量, 它的方向與取得最它的方向與取得最大方向?qū)?shù)的方向一致大方向?qū)?shù)的方向一致, 而它的模為方向?qū)?shù)的最大值。而它的模為方向?qū)?shù)的最大值。 以以 的的n個(gè)偏導(dǎo)數(shù)為分量的向量稱為在處的梯度，個(gè)偏導(dǎo)數(shù)為分量的向量稱為在處的梯度， 記為記為 梯度也可以稱為函數(shù)關(guān)于向量的一階導(dǎo)數(shù)。梯度也可以稱為函數(shù)關(guān)于向量的一階導(dǎo)數(shù)。)(xf

9、Tnxxfxxfxxfxf)(,)(,)()(21Page 13n Hesse矩陣22221211222222122222212()()()()()()()()()()()nnnnnfxfxfxxxxxxfxfxfxxxxxfHxfxfxfxxxxxxxx20c2()0Tb x2()2Tx AxA（其中TAA）Page 14函數(shù)的方向?qū)?shù)與極值問(wèn)題函數(shù)的方向?qū)?shù)與極值問(wèn)題n 梯度與方向?qū)?shù)之間的關(guān)系梯度與方向?qū)?shù)之間的關(guān)系(1) 若若 ，則，則P的方向是函數(shù)在點(diǎn)的方向是函數(shù)在點(diǎn) 處的下降方向；處的下降方向；(2) 若若 ，則，則P的方向是函數(shù)在點(diǎn)的方向是函數(shù)在點(diǎn) 處的上升方向。處的上升方向。

10、方向?qū)?shù)的正負(fù)決定了函數(shù)值方向?qū)?shù)的正負(fù)決定了函數(shù)值的升降，而升降的快慢就由它的的升降，而升降的快慢就由它的絕對(duì)值大小決定絕對(duì)值越大，絕對(duì)值大小決定絕對(duì)值越大，升降的速度就越快升降的速度就越快0)(0PxfT0)(0PxfT0 x0 xPage 15結(jié)論：結(jié)論：(1)梯度方向是函數(shù)值的最速上升方向；梯度方向是函數(shù)值的最速上升方向；(2)函數(shù)在與其梯度正交的方向上變化率為零；函數(shù)在與其梯度正交的方向上變化率為零；(3)函數(shù)在與其梯度成銳角的方向上是上升的，而在與其梯度函數(shù)在與其梯度成銳角的方向上是上升的，而在與其梯度成鈍角的方向上是下降的；成鈍角的方向上是下降的；(4)梯度反方向是函數(shù)值的最速下

11、降方向梯度反方向是函數(shù)值的最速下降方向Page 16函數(shù)的方向?qū)?shù)與極值問(wèn)題函數(shù)的方向?qū)?shù)與極值問(wèn)題n 可行方向可行方向定義定義 設(shè)設(shè) x是規(guī)劃（是規(guī)劃（NPNP）一個(gè)可行點(diǎn)）一個(gè)可行點(diǎn), ,若非零向量若非零向量 d滿足滿足： 當(dāng)當(dāng) 時(shí)時(shí)， , 0(0, )Rxd則稱則稱 為集為集dRx處的一個(gè)可行方向（處的一個(gè)可行方向（feasible directionfeasible direction）。）。合合 在點(diǎn)在點(diǎn) 若下降方向關(guān)于區(qū)域若下降方向關(guān)于區(qū)域 D D 可行，可行，則稱為則稱為可行下降方向可行下降方向。Page 17函數(shù)的方向?qū)?shù)與極值問(wèn)題函數(shù)的方向?qū)?shù)與極值問(wèn)題n 無(wú)約束優(yōu)化極值問(wèn)題

12、無(wú)約束優(yōu)化極值問(wèn)題 定理定理3.1 (3.1 (一階必要條件一階必要條件) )( )f x在在一一次可微次可微；x(2)(2) 為為 的局部極值點(diǎn)，則的局部極值點(diǎn)，則( )0fx（1 1）函數(shù)函數(shù)x( )f x定理定理3.2. (3.2. (充分條件充分條件) )( )0fx（3 3）HesseHesse矩陣矩陣2( )0fx（）。）。則則為的嚴(yán)格局部極小值點(diǎn)（極大值）為的嚴(yán)格局部極小值點(diǎn)（極大值） ( )f x在在二次可微二次可微；x（1 1）函數(shù)函數(shù)2( )0fx（2 2）xPage 18凸集、凸函數(shù)與凸優(yōu)化問(wèn)題凸組合：已知 ，任取k個(gè)點(diǎn)，如果存在常 數(shù) ， 使得 則稱 為 的凸組合。 凸

13、集凸集：設(shè)集合：設(shè)集合 ，如果，如果 中任意兩點(diǎn)中任意兩點(diǎn)的凸組合仍然屬于的凸組合仍然屬于 , ,則稱則稱 為凸集。為凸集。nRDnRD0ia),2, 1(ki11kiiaxxakiii1xix),2, 1(kiDDDPage 19凸集、凸函數(shù)與凸優(yōu)化問(wèn)題設(shè)設(shè) ，任取，任取 如果有如果有 ，有，有則稱則稱 為為 上的（嚴(yán)格）凸函數(shù)。上的（嚴(yán)格）凸函數(shù)。ab凸函數(shù)凸函數(shù)1x2x1P2Ppab凹函數(shù)凹函數(shù)1x2xnRDf:Dxx21,1, 0,2121iiaaafD)()()(22112211xfaxfaxaxafPage 20n 凸函數(shù)的判斷條件凸函數(shù)的判斷條件（1） 一階導(dǎo)數(shù)向量法一階導(dǎo)數(shù)向量法 是凸集是凸集 上的凸函數(shù)的充要條件是，上的凸函數(shù)的充要條件是， 有有 (2) 二階導(dǎo)數(shù)矩陣法二階導(dǎo)數(shù)矩陣法 設(shè)設(shè) 在凸集在凸集X上有二階連續(xù)偏導(dǎo)數(shù)，則上有二階連續(xù)偏導(dǎo)數(shù)，則 是凸函數(shù)的是凸函數(shù)的充要條件是，充要條件是， 有有 半正定。半正定。)(xfDDxx21,)()()()() 1 ()2() 1 () 1 ()2(xxxfxfxfT)(xf)(xfDx)(2xfPage 21n 凸規(guī)劃凸規(guī)劃 設(shè)有規(guī)劃 設(shè)P為凸規(guī)劃，則：min ( ). .( )0,1,2,ifst gimxx當(dāng)當(dāng) ( )f x( )(1,2,)igimx為凸函