最優(yōu)化理論與方法概述演示文稿

最優(yōu)化理論與方法概述演示文稿當(dāng)前第1頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)（優(yōu)選）最優(yōu)化理論與方法概述.當(dāng)前第2頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)1.最優(yōu)化問題最優(yōu)化問題：求一個(gè)一元函數(shù)或多元函數(shù)的極值。在微積分中，我們?cè)?jīng)接觸過一些比較簡(jiǎn)單的極值問題。下面通過具體例子來看看什么是最優(yōu)化問題。當(dāng)前第3頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)1.1最優(yōu)化問題的例子例1對(duì)邊長(zhǎng)為a的正方形鐵板，在四個(gè)角處剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？解：設(shè)剪去的正方形邊長(zhǎng)為x，由題意易知，此問題的數(shù)學(xué)模型為， 當(dāng)前第4頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)配料每磅配料中的營(yíng)養(yǎng)含量鈣蛋白質(zhì)纖維每磅成本（元）石灰石谷物大豆粉0.3800.000.000.0010.090.020.0020.500.08

0.01640.04630.1250例2.（混合飼料配合）設(shè)每天需要混合飼料的批量為100磅，這份飼料必須含：至少0.8%而不超過1.2%的鈣;至少22%的蛋白質(zhì);至多5%的粗纖維。假定主要配料包括石灰石、谷物、大豆粉。這些配料的主要營(yíng)養(yǎng)成分如下表所示。試以最低成本確定滿足動(dòng)物所需營(yíng)養(yǎng)的最優(yōu)混合飼料。當(dāng)前第5頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)解:根據(jù)前面介紹的建模要素得出此問題的數(shù)學(xué)模型如下:設(shè)是生產(chǎn)100磅混合飼料所須的石灰石、谷物、大豆粉的量（磅）。當(dāng)前第6頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)1.2最優(yōu)化問題的數(shù)學(xué)模型一般形式向量形式其中當(dāng)前第7頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)

目標(biāo)函數(shù)不等式約束等式約束

稱滿足所有約束條件的向量為可行解，或可行點(diǎn)，全體可行點(diǎn)的集合稱為可行集，記為。

若是連續(xù)函數(shù)，則是閉集。當(dāng)前第8頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)

在可行集中找一點(diǎn)，使目標(biāo)函數(shù)在該點(diǎn)取最小值，即滿足：的過程即為最優(yōu)化的求解過程。稱為問題的最優(yōu)點(diǎn)或最優(yōu)解，稱為最優(yōu)值。

定義1：整體（全局）最優(yōu)解：若，對(duì)于一切，恒有則稱是最優(yōu)化問題的整體最優(yōu)解。定義2：局部最優(yōu)解：若，存在某鄰域，使得對(duì)于一切，恒有則稱是最優(yōu)化問題的局部最優(yōu)解。其中嚴(yán)格最優(yōu)解：當(dāng)，有則稱為問題的嚴(yán)格最優(yōu)解。當(dāng)前第9頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)f(X)局部最優(yōu)解整體最優(yōu)解當(dāng)前第10頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)1.3最優(yōu)化問題的分類與時(shí)間的關(guān)系：靜態(tài)問題，動(dòng)態(tài)問題是否有約束條件：有約束問題，無約束問題函數(shù)類型：線性規(guī)劃，非線性規(guī)劃當(dāng)前第11頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)2、梯度與Hesse矩陣2.1等值線二維問題的目標(biāo)函數(shù)表示三維空間中的曲面。在空間直角坐標(biāo)系中，平面與曲面的交線在平面上的投影曲線為取不同的值得到不同的投影曲線。每一條投影曲線對(duì)應(yīng)一個(gè)值，所以我們稱此投影曲線為目標(biāo)函數(shù)的等值線或等高線。當(dāng)前第12頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)當(dāng)常數(shù)取不同的值時(shí)，重復(fù)上面的討論，在平面上得到一族曲線——等值線.等值線的形狀完全由曲面的形狀所決定；反之，由等高線的形狀也可以推測(cè)出曲面的形狀．當(dāng)前第13頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)例

在坐標(biāo)平面上畫出目標(biāo)函數(shù)的等值線．

解:因?yàn)楫?dāng)目標(biāo)函數(shù)取常數(shù)時(shí)，曲線表示是以原點(diǎn)為圓心，半徑為的圓．因此等值線是一族以原點(diǎn)為圓心的同心圓（如圖所示）

當(dāng)前第14頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)2.2n元函數(shù)的可微性與梯度梯度：多元函數(shù)關(guān)于的一階導(dǎo)數(shù)當(dāng)前第15頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)Hesse矩陣：多元函數(shù)關(guān)于的二階偏導(dǎo)數(shù)矩陣當(dāng)前第16頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)例：求目標(biāo)函數(shù)的梯度和Hesse矩陣。解：因?yàn)?/p>

則又因?yàn)椋?/p>

故Hesse陣為：

當(dāng)前第17頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)下面幾個(gè)公式是今后常用到的：（1），則（2），則(單位陣）（3），Q對(duì)稱，則（4）若，其中f：則：

當(dāng)前第18頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)3、多元函數(shù)的Taylor展開

多元函數(shù)Taylor展開式在最優(yōu)化理論中十分重要。許多方法及其收斂性的證明都是從它出發(fā)的。

定理：設(shè)具有二階連續(xù)偏導(dǎo)數(shù)。則：

其中而0＜θ＜1當(dāng)前第19頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)多元函數(shù)Taylor展開其他形式：

當(dāng)前第20頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)當(dāng)前第21頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)當(dāng)前第22頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)當(dāng)前第23頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)當(dāng)前第24頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)當(dāng)前第25頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)

凸集和凸函數(shù)在非線性規(guī)劃的理論中具有重要作用，下面給出凸集和凸函數(shù)的一些基本知識(shí)。定義1

設(shè)，若對(duì)D中任意兩點(diǎn)與，連接與的線段仍屬于D；換言之，對(duì)，∈D，∈[0,1]恒有

+(1-)∈D則稱D為凸集。+(1-)稱為和的凸組合。nRDí)1(x)2(x)1(x)2(x")1(x)2(xa")1(xa)2(xa)1(xaa)2(x)1(x)2(x5、凸集、凸函數(shù)和凸規(guī)劃當(dāng)前第26頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)例規(guī)定：歐式空間是凸集，空集是凸集，單點(diǎn)集{x}為凸集當(dāng)前第27頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)例:證明集合是凸集。其中，A為mn矩陣，b為m維向量。證明：任取，則所以，當(dāng)前第28頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)例：給定線性規(guī)劃，其中，若令，則是凸集。當(dāng)前第29頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)凸集的性質(zhì)有限個(gè)凸集的交集仍然是凸集。設(shè)是凸集，則是凸集。設(shè)是凸集，則是凸集。凸集的和集仍然是凸集。設(shè)是凸集，則是凸集。推論：設(shè)是凸集，，則也是凸集，其中。當(dāng)前第30頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)定義3極點(diǎn)（頂點(diǎn)）：設(shè)D是凸集,若D中的點(diǎn)x不能成為D中任何線段上的內(nèi)點(diǎn)，則稱x為凸集D的極點(diǎn)。設(shè)D為凸集，X∈D,若X不能用X(1)∈D,X(2)∈D兩點(diǎn)的一個(gè)凸組合表示為X=αX(1)+(1-α)X(2),其中0<α<1，則稱X為D的一個(gè)極點(diǎn)。定義2.凸組合：設(shè)X(1)，X(2)，…，X(k)是n維歐式空間中的k個(gè)點(diǎn)，若存在μ1,μ2,…,μk滿足0≤μi≤1,(i=1,2,…,k),

使X=μ1X(1)+μ2X(2)+…μkX(k)，則稱X為X(1)，X(2)，…，X(k)的凸組合。當(dāng)前第31頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)

多邊形的頂點(diǎn)是凸集的極點(diǎn)（頂點(diǎn)）。圓周上的點(diǎn)都是凸集的極點(diǎn)（頂點(diǎn)）。當(dāng)前第32頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)定義4

設(shè)D為R中非空凸集，若對(duì)，∈D，∈(0,1)恒有n")1(x)2(xa"f[+(1-)]≤+(1-)f(*))1(xa)2(xa)()1(xfaa)()2(x則稱為D上的凸函數(shù)；進(jìn)一步，若≠時(shí)，(*)式僅〝<〞成立,則稱為D上嚴(yán)格凸函數(shù)。)(xf)1(x)2(x)(xf對(duì)凸的一元函數(shù)的幾何意義為：在曲線上任取兩點(diǎn)P1(x1,),P2(x2,)弦位于弧之上（見圖）。)(xf)(1xf(x2)f21PP21PPx1x2x(x,y)p1p2)(xf當(dāng)前第33頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)性質(zhì)1：

f(x)是凸集D上的凹函數(shù)的充要條件是-f(x)是D上的凸函數(shù)。當(dāng)前第34頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)+(1-)-a)(1xfa)(2xf])1([21xxfaa-+=2221)1(xxaa-+221])1([xxaa-+-=2221)1(xxaa-+-])1(2)1([21222212xxxxaaaa-+-+=212221)1(2)1()1(xxxxaaaaaa---+-=(1-)aa)2(212221xxxx-+=(1-)aa(x1-x2)≥02∴+(1-)≥a)(1xfa)(2xf])1([21xxfaa-+所以，=

x是R上凸函數(shù)。)(xf2例如，對(duì)=x，因x1,x2∈R，∈(0,1))(xf"a"2當(dāng)前第35頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)例：證明線性函數(shù)是上的凸函數(shù)。

同理可證線性函數(shù)

也是上的凹函數(shù)。

當(dāng)前第36頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)定理2(一階條件）：

設(shè)D是R中非空開凸集,是定義在D上的可微函數(shù),則是凸函數(shù)的充要條件為x,y∈D,有n)(xf)(xf")(yf≥+(

y-x) )(xfT)(xf?而是D上嚴(yán)格凸函數(shù)為x,y∈D,x≠y,上式僅〝>〞成立。)(xf"xf(x)當(dāng)前第37頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)證明：必要性即由Taylor公式令得當(dāng)前第38頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)設(shè)則充分性令即所以同理當(dāng)前第39頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)定理3（二階條件）：

設(shè)D是R中非空開凸集,是定義在D上的二次可微函數(shù),則是凸函數(shù)的充要條件為對(duì)x∈D,≥0,即Hesse矩陣半正定。n)(xf)(xf")(2xf?)(2xf?若x∈D,>0，即Hesse矩陣正定，則為嚴(yán)格凸函數(shù)。")(2xf?)(xf當(dāng)前第40頁(yè)\共有47頁(yè)\編于星期五\1點(diǎn)證明：必要性所以由Taylor公式令得因?yàn)闉殚_集。由一階條件所以由p的任意性，半正定。當(dāng)前第41頁(yè)\共有47頁(yè)\編于星