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

1、第章第章 經(jīng)典最優(yōu)化方法經(jīng)典最優(yōu)化方法 內(nèi)容介紹內(nèi)容介紹 u微分學(xué)中求極值 u無約束最優(yōu)化問題 u常用微分公式 u凸集與凸函數(shù) u等式約束最優(yōu)化問題 u不等式約束最優(yōu)化問題 u變分學(xué)中求極值 微分學(xué)中求極值微分學(xué)中求極值 一元函數(shù)的極值 1.一元函數(shù)極值的求法與判別 必要條件： 設(shè)函數(shù) 在點 處具有導(dǎo)數(shù)，且在 處 取得極值，則該函數(shù) 在 處的導(dǎo)數(shù) 這里有個前提，即函數(shù) 在設(shè)計區(qū)間要連續(xù)可導(dǎo)。凡是滿足 上述的點都叫函數(shù) 的駐點。我們可知駐點并不完全是極值 點，它還有拐點，當(dāng)然，極值點必定是駐點。因此，還必須有判 別函數(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ù)取極小值，有極小值點； 找出函數(shù)的極值點，函數(shù)的極值自然容易計算出來。 微分學(xué)中求極值微分學(xué)中求極值 * *2 . *2 . * * * 2. 1 2! 1 2! 00 000 x f xf xfxxfxx f xfxxfxx f xfxx fxf xfx f x fxfxxfxx 在 附近展成臺勞極 = = 由此可見： 當(dāng)時，函數(shù)是單調(diào)上升；當(dāng)時，函數(shù) 函數(shù)

3、是單調(diào)上升； 當(dāng) 時，若，則 為極小點，若，則 為極大點 微分學(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ù)的臺勞展開式 其中 叫梯度，是一階偏導(dǎo)向量。 叫赫森矩陣，是二階偏導(dǎo)向量，對稱方陣。 故臺勞展開式也可寫成 * 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ù)沿任意 方向取長度為的點，該點的函數(shù)的極限 lim 存在，就稱極限值為函數(shù)在該點沿 方向的方向?qū)?shù) 微分學(xué)中求極值微分學(xué)中求極值 1.() . ( ) 3.0, 0 4. f X f x g 由梯度與方向?qū)?shù)的概念，我們可以得到： 函數(shù)在該點沿 方向的方向?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對稱方陣 ，用記號A代表 性質(zhì)：1.A是目標(biāo)函數(shù)的二階偏導(dǎo)數(shù)，是梯度的一階偏導(dǎo)數(shù)。 2.A是對稱方陣。 為正定的條件是：各階主子式大于零。 4.若矩陣A正定，則二次型，若

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

7、在求解運算過程中，常用到以下微分公式： 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)化問題等式約束最優(yōu)化問題 等式約束最優(yōu)化問

8、題的數(shù)學(xué)模型式 這里介紹兩種比較常用的方法：消元法和拉格朗日乘子法。 () . .( )0 i f X S t g x min n XE 1,2,.,im 等式約束最優(yōu)化問題等式約束最優(yōu)化問題 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)化問題轉(zhuǎn)化為無約束最優(yōu)化問題的一種最為簡單的方法， 這里以二維為例，對其方法加以說明： 已知問題的數(shù)學(xué)模型為 min 先由約束方程，解出即消去 ； 然后把所得的表達式

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

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

12、格 朗 日 函 數(shù) 的 極 值 點 就 是 原 目 標(biāo) 函 數(shù) 的 極 值 點 ， 即 則 原 目 標(biāo) 函 數(shù) 的 極 小 值 可 以 算 出 為。 不等式約束最優(yōu)化問題不等式約束最優(yōu)化問題 不等式約束的最優(yōu)化問題的解析法與前面處理的基本思路相類似，也是 構(gòu)造一個包含原目標(biāo)函數(shù)與約束函數(shù)的新目標(biāo)函數(shù)。只是具體的構(gòu) 造方法不同，這里處理的也是二維問題 原問題的數(shù)學(xué)模型為 引入一個松弛變量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)造一個拉格朗日函數(shù)

13、 ， ， 不等式約束最優(yōu)化問題不等式約束最優(yōu)化問題 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)，這就保證了引入項為非負值， 能使不等式轉(zhuǎn)化為等式，于是，對新構(gòu)成的拉格朗日函數(shù)可列出其極值條件 四個未知數(shù)四個方程，可以求解得到成為原問題的最優(yōu)解，最優(yōu)值。 等式約束最優(yōu)化問題等式約束最優(yōu)化問題 說明： 從這個手算的約束最優(yōu)化問題來看，拉格朗日乘子法使簡單而易算的，但終歸 只是一種經(jīng)典算法。當(dāng)最優(yōu)化問題為大型非線性問題時，要解高次聯(lián)立方程組； 另外，當(dāng)拉格朗日函數(shù)

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