第2章經(jīng)典最優(yōu)化方法

1、第章第章 經(jīng)典最優(yōu)化方法經(jīng)典最優(yōu)化方法 內(nèi)容介紹內(nèi)容介紹 u微分學(xué)中求極值 u無(wú)約束最優(yōu)化問(wèn)題 u常用微分公式 u凸集與凸函數(shù) u等式約束最優(yōu)化問(wèn)題 u不等式約束最優(yōu)化問(wèn)題 u變分學(xué)中求極值 微分學(xué)中求極值微分學(xué)中求極值 一元函數(shù)的極值 1.一元函數(shù)極值的求法與判別 必要條件： 設(shè)函數(shù) 在點(diǎn) 處具有導(dǎo)數(shù)，且在 處 取得極值，則該函數(shù) 在 處的導(dǎo)數(shù) 這里有個(gè)前提，即函數(shù) 在設(shè)計(jì)區(qū)間要連續(xù)可導(dǎo)。凡是滿(mǎn)足 上述的點(diǎn)都叫函數(shù) 的駐點(diǎn)。我們可知駐點(diǎn)并不完全是極值 點(diǎn)，它還有拐點(diǎn)，當(dāng)然，極值點(diǎn)必定是駐點(diǎn)。因此，還必須有判 別函數(shù)極值的更充分條件。 ( )f x 0 x ( )f x 0 x ( )f x

2、0 x ()0fx ( )f x ( )f x 微分學(xué)中求極值微分學(xué)中求極值 ( )0,0, 10( ) 20( ) fxfx fxf x fxf x 充分條件： 當(dāng)函數(shù)的一階導(dǎo)數(shù)二階導(dǎo)數(shù)并且 ）時(shí)，函數(shù)取極大值，有極大值點(diǎn)； ）時(shí)，函數(shù)取極小值，有極小值點(diǎn)； 找出函數(shù)的極值點(diǎn)，函數(shù)的極值自然容易計(jì)算出來(lái)。 微分學(xué)中求極值微分學(xué)中求極值 * *2 . *2 . * * * 2. 1 2! 1 2! 00 000 x f xf xfxxfxx f xfxxfxx f xfxx fxf xfx f x fxfxxfxx 在 附近展成臺(tái)勞極 = = 由此可見(jiàn)： 當(dāng)時(shí)，函數(shù)是單調(diào)上升；當(dāng)時(shí)，函數(shù) 函數(shù)

3、是單調(diào)上升； 當(dāng) 時(shí)，若，則 為極小點(diǎn)，若，則 為極大點(diǎn) 微分學(xué)中求極值微分學(xué)中求極值 二元函數(shù)的極值 2 * *2 12 22 2 2 1122 2 22 2 122 (1) 1 ()() 2 (), , () , () T T T ff f Xf XXXX XX fff gf X Xxx ff xx x f Af X X ff x xx f X 二元函數(shù)的臺(tái)勞展開(kāi)式 其中 叫梯度，是一階偏導(dǎo)向量。 叫赫森矩陣，是二階偏導(dǎo)向量，對(duì)稱(chēng)方陣。 故臺(tái)勞展開(kāi)式也可寫(xiě)成 * 1 () 2 TT f XgXX A X 微分學(xué)中求極值微分學(xué)中求極值 111 1 (2) ( )( ) ( ) f f Xf

4、X X gxgxf Xx x 梯度與方向?qū)?shù) 梯度的定義：梯度是函數(shù)的一階偏導(dǎo)數(shù)組成的向量。記為：g 梯度 在 方向上的投影，即 在 方向上的分量，就是函數(shù)在 方向的偏導(dǎo)數(shù)， 即函數(shù)在 方向的變化率。 112212 0 ( ) (,)( , ) ( ) f XX f xx xxf x x f X 方向?qū)?shù)的定義：二元函數(shù)沿任意 方向取長(zhǎng)度為的點(diǎn)，該點(diǎn)的函數(shù)的極限 lim 存在，就稱(chēng)極限值為函數(shù)在該點(diǎn)沿 方向的方向?qū)?shù) 微分學(xué)中求極值微分學(xué)中求極值 1.() . ( ) 3.0, 0 4. f X f x g 由梯度與方向?qū)?shù)的概念，我們可以得到： 函數(shù)在該點(diǎn)沿 方向的方向?qū)?shù)等于梯度g沿 方向

5、的 投影。 2.梯度g在自身方向上的投影最大，最大值為 g 因而，函數(shù) 沿梯度方向上升最快。 梯度 在與自身垂直的方向上投影為 所以函數(shù)沿與梯度 垂直方向變化最慢，變化率為 ； 與梯度成銳角方向，函數(shù)是上升的；與梯度成鈍角方向， 函數(shù)是下降的。 微分學(xué)中求極值微分學(xué)中求極值 (3)赫森矩陣（Hesse） 2 2 2 () 3. 00 TT f Af X X A X A XX A X 定義：赫森矩陣，是二階偏導(dǎo)數(shù)矩陣，且是2 2對(duì)稱(chēng)方陣 ，用記號(hào)A代表 性質(zhì)：1.A是目標(biāo)函數(shù)的二階偏導(dǎo)數(shù)，是梯度的一階偏導(dǎo)數(shù)。 2.A是對(duì)稱(chēng)方陣。 為正定的條件是：各階主子式大于零。 4.若矩陣A正定，則二次型，若

6、矩陣A負(fù)定，則二次型 2 ( )( ) 0( )f Xgf XAf X (4)二元函數(shù)極值的充分條件 定理：二元函數(shù)存在極值點(diǎn)的充分條件是：梯度。且 正定，則有極小點(diǎn)。反之，則有極大點(diǎn)。 無(wú)約束最優(yōu)化問(wèn)題無(wú)約束最優(yōu)化問(wèn)題 由上一節(jié)可知，對(duì)于無(wú)約束最優(yōu)化問(wèn)題，其數(shù)學(xué)模型中只有目標(biāo)函 數(shù) 采用解析法求解，其求解過(guò)程可以歸結(jié)為一下三個(gè)步驟： 1.令梯度g=0，解出各個(gè)駐點(diǎn)。 2.計(jì)算各駐點(diǎn)的矩陣 A,判斷矩陣A正定或負(fù)定，得到相對(duì)應(yīng)的極小點(diǎn) 或極大點(diǎn)； 3.計(jì)算極值。 ()f Xmin X n E 常用微分公式常用微分公式 C C (X X) (X QX) T T T T B B B 對(duì)于多元函數(shù)，

7、在求解運(yùn)算過(guò)程中，常用到以下微分公式： 1.0 式中 為常數(shù)； 0為n維0向量； 2.0 式中B為n維常向量； 0為n*n階矩陣； 3.XB 式中B為n維常向量； X為n維變向量； X為標(biāo)量 4.2X； 5.2QX； 6. X=I； 凸集與凸函數(shù)凸集與凸函數(shù) 凸集與凸函數(shù)凸集與凸函數(shù) 凸集與凸函數(shù)凸集與凸函數(shù) 凸集與凸函數(shù)凸集與凸函數(shù) 凸集與凸函數(shù)凸集與凸函數(shù) 凸集與凸函數(shù)凸集與凸函數(shù) 凸集與凸函數(shù)凸集與凸函數(shù) 凸集與凸函數(shù)凸集與凸函數(shù) 凸集與凸函數(shù)凸集與凸函數(shù) 凸集與凸函數(shù)凸集與凸函數(shù) 凸集與凸函數(shù)凸集與凸函數(shù) 凸集與凸函數(shù)凸集與凸函數(shù) 等式約束最優(yōu)化問(wèn)題等式約束最優(yōu)化問(wèn)題 等式約束最優(yōu)化問(wèn)

8、題的數(shù)學(xué)模型式 這里介紹兩種比較常用的方法：消元法和拉格朗日乘子法。 () . .( )0 i f X S t g x min n XE 1,2,.,im 等式約束最優(yōu)化問(wèn)題等式約束最優(yōu)化問(wèn)題 12 12 12212 11 1. ( )( , ) . ( , ) 0 ( , ) 0( ), ( ) min ( , ( ) f Xf x x Stg x x g x xxh xx f Xf x h x 消元法 消元法就是將等式約束最優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束最優(yōu)化問(wèn)題的一種最為簡(jiǎn)單的方法， 這里以二維為例，對(duì)其方法加以說(shuō)明： 已知問(wèn)題的數(shù)學(xué)模型為 min 先由約束方程，解出即消去 ； 然后把所得的表達(dá)式

9、代入目標(biāo)函數(shù)中，便可得到無(wú)約束的極值問(wèn)題 min 等式約束最優(yōu)化問(wèn)題等式約束最優(yōu)化問(wèn)題 2.拉格朗日乘子法 消元法的特點(diǎn)在于改寫(xiě)約束條件，消除約束方程。但是，當(dāng)?shù)仁郊s束是多維，高次或 非線性時(shí)，這種方法就顯得十分煩瑣。拉格朗日乘子法是引進(jìn)一個(gè)代定系數(shù)，構(gòu)造一個(gè) 新的無(wú)約束條件的目標(biāo)函數(shù)，而使數(shù)學(xué)變換過(guò)程簡(jiǎn)化。這里也以二維為例 。 12 121212 12 111 222 12 , ,(,)(,) 0 0 0 0 (,)0 xx Lxxfxxg xx LLL xx Lfg xxx Lfg xxx L g xx 我 們 可 以 得 到 三 元 函 數(shù) ，的 三 個(gè) 偏 導(dǎo) 數(shù) 都 等 于 零 的

10、聯(lián) 立 方 程 ， 若 引 入 函 數(shù) ， 令 其 偏 微 分 均 等 于 ， 有 于 是 可 以 得 到 等式約束最優(yōu)化問(wèn)題等式約束最優(yōu)化問(wèn)題 X () X()() () () L f X Lf Xg X f X g X 由此說(shuō)明，可通過(guò)求引入的函數(shù)稱(chēng)之為拉格朗日函數(shù)，的無(wú)約束極值， 求解等式約束條件下目標(biāo)函數(shù) 的極值。即稱(chēng)之為拉格朗日乘子法。 可用如下式子表示 ： ， 其中 的幾何意義表示為 物理意義為：表示隨著約束條件的微小變化，會(huì)使目標(biāo)函數(shù)引起變化的一種比率， 又稱(chēng)靈敏度。 等式約束最優(yōu)化問(wèn)題等式約束最優(yōu)化問(wèn)題 22 12121212 1212 22 12121212 12 111 2

11、22 1 ()(,)1 046 0 . .(,)80 X()()1 046 08 21 00 fXfxxxxx xxx S t gxxxx LfXgXxxx xxxxx Lfg xx xxx Lfg xxx 例： 用 拉 格 朗 日 法 求 解 m i n 解 ： 1 . 列 出 拉 格 朗 日 函 數(shù) ， （） 2 . 求 解 偏 導(dǎo) 數(shù) 方 程 式 21 1212 * 1 * 2 * 12 * 240 (,)80 3 . 5 3 4 . ,5 , 3 ()1 7 T T xx L gxxxx x x Xxx fX 解 以 上 聯(lián) 立 方 程 式 ， 得 到 3 由 于 無(wú) 約 束 的 拉

12、格 朗 日 函 數(shù) 的 極 值 點(diǎn) 就 是 原 目 標(biāo) 函 數(shù) 的 極 值 點(diǎn) ， 即 則 原 目 標(biāo) 函 數(shù) 的 極 小 值 可 以 算 出 為。 不等式約束最優(yōu)化問(wèn)題不等式約束最優(yōu)化問(wèn)題 不等式約束的最優(yōu)化問(wèn)題的解析法與前面處理的基本思路相類(lèi)似，也是 構(gòu)造一個(gè)包含原目標(biāo)函數(shù)與約束函數(shù)的新目標(biāo)函數(shù)。只是具體的構(gòu) 造方法不同，這里處理的也是二維問(wèn)題 原問(wèn)題的數(shù)學(xué)模型為 引入一個(gè)松弛變量r,把約束條件改為等式約束，即 12 12 ()( ,) . . ( ,)0 f Xf x x S t g x x min 2 12 ( ,)0g x xr 2 X()()Lvf Xg Xv 構(gòu)造一個(gè)拉格朗日函數(shù)

13、 ， ， 不等式約束最優(yōu)化問(wèn)題不等式約束最優(yōu)化問(wèn)題 2 111 222 2 12 * 0 0 ( ,)0 20 ,(), v Lfg xxx Lfg xxx L g x xv L v v Xf X 由于引入的松弛變量是以 的形式出現(xiàn)，這就保證了引入項(xiàng)為非負(fù)值， 能使不等式轉(zhuǎn)化為等式，于是，對(duì)新構(gòu)成的拉格朗日函數(shù)可列出其極值條件 四個(gè)未知數(shù)四個(gè)方程，可以求解得到成為原問(wèn)題的最優(yōu)解，最優(yōu)值。 等式約束最優(yōu)化問(wèn)題等式約束最優(yōu)化問(wèn)題 說(shuō)明： 從這個(gè)手算的約束最優(yōu)化問(wèn)題來(lái)看，拉格朗日乘子法使簡(jiǎn)單而易算的，但終歸 只是一種經(jīng)典算法。當(dāng)最優(yōu)化問(wèn)題為大型非線性問(wèn)題時(shí)，要解高次聯(lián)立方程組； 另外，當(dāng)拉格朗日函數(shù)

14、為非凸函數(shù)時(shí)，求得得最優(yōu)點(diǎn)可能出現(xiàn)鞍點(diǎn)，導(dǎo)致尋優(yōu)過(guò)程 失敗。不過(guò)這種方法在約束非線性最優(yōu)化問(wèn)題的求解中仍有意義和應(yīng)用。 變分學(xué)中求極值變分學(xué)中求極值 變分學(xué)是研究確定泛函的極值或者說(shuō)駐值的學(xué)科。而泛函定義為一個(gè)函數(shù)或數(shù)個(gè)函數(shù)的 函數(shù)。因此，變分學(xué)可用于求解隱函數(shù)及其動(dòng)態(tài)優(yōu)化問(wèn)題，此外，變分學(xué)在求解某些力學(xué)， 光學(xué)及最優(yōu)控制中也很有用。 2 1122 A , , (), (), dx du AFxu dx xxu u xuu xu 2 1 x x 1 無(wú)約束的變分理論中的一個(gè)簡(jiǎn)單問(wèn)題可敘述如下： 求函數(shù)u(x)以使極小化泛函 =F(x,u,u ,u ) 式中， 和可稱(chēng)為泛函， 是獨(dú)立的變量， 上式中的積分定義域區(qū)間或者說(shuō)范圍在內(nèi)。設(shè) 在邊界上的值已經(jīng)給定為 則稱(chēng)它們式此問(wèn)題的邊界條件。 可用于求解此式問(wèn)題的方法之一及步驟是： 1.選擇一