優(yōu)化方法數(shù)學基礎(chǔ)

1、關(guān)于優(yōu)化方法的數(shù)學基礎(chǔ)第1頁，共51頁，2022年，5月20日，19點3分，星期四2-1 方向?qū)?shù)與梯度一、函數(shù)的方向?qū)?shù)一個二元函數(shù)F(x1,x2)在X0點處的偏導數(shù)定義為: 分別是函數(shù)在點X0處沿坐標軸方向的變化率. 第2頁，共51頁，2022年，5月20日，19點3分，星期四函數(shù) 在點 處沿某一方向的變化率如圖2-1 稱它為函數(shù)沿此方向的方向?qū)?shù) （2-1） 第3頁，共51頁，2022年，5月20日，19點3分，星期四 和 也可看成是函數(shù)分別沿坐標軸方向的方向?qū)?shù)推導方向?qū)?shù)與偏導數(shù)之間的數(shù)量關(guān)系：偏導數(shù)是方向?qū)?shù)的特例（2-2）第4頁，共51頁，2022年，5月20日，19點3分，星期

2、四n元函數(shù)在點x0處沿s方向的方向?qū)?shù) Ox2x1x10 x20 x0 x1x2sxS12圖2-3第5頁，共51頁，2022年，5月20日，19點3分，星期四二、 梯度二元函數(shù)的梯度: 為函數(shù)F(x1，x2)在x0點處的梯度。第6頁，共51頁，2022年，5月20日，19點3分，星期四梯度的模：設(shè)梯度方向和s方向重合時，方向?qū)?shù)值最大。第7頁，共51頁，2022年，5月20日，19點3分，星期四 梯度方向是函數(shù)值變化最快的方向，而梯度的模就是函數(shù)變化率的最大值 。圖2-4 梯度方向與等值線的關(guān)系設(shè)：則有 為單位向量。第8頁，共51頁，2022年，5月20日，19點3分，星期四多元函數(shù)的梯度第9

3、頁，共51頁，2022年，5月20日，19點3分，星期四函數(shù)的梯度方向與函數(shù)等值面相垂直，也就是和等值面上過x0的一切曲線相垂直。 由于梯度的模因點而異，即函數(shù)在不同點處的最大變化率是不同的。因此，梯度是函數(shù)的一種局部性質(zhì)。梯度 模：第10頁，共51頁，2022年，5月20日，19點3分，星期四梯度兩個重要性質(zhì)： 性質(zhì)一 函數(shù)在某點的梯度不為零，則必與過該點的等值面垂直； 性質(zhì)二 梯度方向是函數(shù)具有最大變化率的方向。圖2-5 梯度方向與等值面的關(guān)系第11頁，共51頁，2022年，5月20日，19點3分，星期四例2-1 求二元函數(shù) 在點 沿 和 的方向?qū)?shù)。解： 因此， 同理：第12頁，共51頁

4、，2022年，5月20日，19點3分，星期四例 2-2求函數(shù) 在點x(1)=3,2T 的 梯度。在點x(1)=3,2T處的梯度為：解： 第13頁，共51頁，2022年，5月20日，19點3分，星期四例2-3：試求目標函數(shù) 在點 處的最速下降方向。則函數(shù)在 處的最速下降方向是解： 由于第14頁，共51頁，2022年，5月20日，19點3分，星期四 當極值點X*能使f（X*）在整個可行域中為最小值時，即在整個可行域中對任一X都有f（X）f（X*）時，則X*就是最優(yōu)點，且稱為全域最優(yōu)點或整體最優(yōu)點。若f（X*）為局部可行域中的極小值而不是整個可行域中的最小值時，則稱X*為局部最優(yōu)點或相對最優(yōu)點。最優(yōu)

5、化設(shè)計的目標是全域最優(yōu)點。為了判斷某一極值點是否為全域最優(yōu)點，研究一下函數(shù)的凸性很有必要。 函數(shù)的凸性表現(xiàn)為單峰性。對于具有凸性特點的函數(shù)來說，其極值點只有一個，因而該點既是局部最優(yōu)點亦為全域最優(yōu)點。 為了研究函數(shù)的凸性，現(xiàn)引入凸集的概念：2-2 凸集、凸函數(shù)與凸規(guī)劃第15頁，共51頁，2022年，5月20日，19點3分，星期四一、凸集 設(shè)D為n維歐氏空間中的一個集合，若其中任意兩點X(1)、X(2)之間的聯(lián)接直線都屬于D，則稱這種集合D為n維歐氏空間的一個凸集。圖2-6（a）是二維空間的一個凸集，而圖2-6（b）不是凸集。圖2-6二維空間的凸集與非凸集第16頁，共51頁，2022年，5月20

6、日，19點3分，星期四X（1）、X（2）兩點之間的聯(lián)接直線，可用數(shù)學式表達為:式中 為由0到1（0 1）間的任意實數(shù)。凸集的性質(zhì)： 1）若D為凸集， 是一個實數(shù)，則集合 D仍是凸集； 2）若D和F均為凸集，則其和（或并）仍是凸集； 3）任何一組凸集的積（或交）仍是凸集。第17頁，共51頁，2022年，5月20日，19點3分，星期四二、凸函數(shù) 具有凸性（表現(xiàn)為單峰性）或只有唯一的局部最優(yōu)值亦即全域最優(yōu)值的函數(shù)，稱為凸函數(shù)或單峰函數(shù)。其數(shù)學定義是： 設(shè) f（X）為定義在 n維歐氏空間中的一個凸集D上的函數(shù)，如果對任何實數(shù)（ 0 1 ）以及對D中任意兩點X(1)、X(2)恒有: 則f（X）為D上的凸

7、函數(shù)，若不滿足上式，則為凹函數(shù)。第18頁，共51頁，2022年，5月20日，19點3分，星期四凸函數(shù)的幾何意義如圖2-7所示：圖2-7 一元凸函數(shù)的幾何意義 在凸函數(shù)曲線上取任意兩點（對應于X軸上的坐標X(1)、X（2）聯(lián)成一直線線段，則該線段上任一點（對應于X軸上的X(k)點）的縱坐標Y值必大于或等于該點（X(k)）處的原函數(shù)值f(X(k)。 第19頁，共51頁，2022年，5月20日，19點3分，星期四凸函數(shù)的一些性質(zhì)： 1）若 f（X）為定義在凸集D上的一個凸函數(shù)，且 a是一個正數(shù)（a 0），則 af（X）也必是定義在凸集D上的凸函數(shù)； 3）若f1(X），f2(X)為定義在凸集D上的兩個

8、凸函數(shù)，和為兩個任意正數(shù)，則函數(shù) afl（X）f2(X)仍為D上的凸函數(shù)。 2）定義在凸集D上的兩個凸函數(shù)f1(X），f2(X)，其和 f（X）=f1（X）十f2（X）亦必為該凸集上的一個凸函數(shù)。 4）若f（X）為定義在凸集D上且具有連續(xù)一階導數(shù)的函數(shù)，則f（X）為凸函數(shù)的充分必要條件為： 對任意兩點X（1），X（2），不等式恒成立第20頁，共51頁，2022年，5月20日，19點3分，星期四三、凸規(guī)劃 對于約束優(yōu)化問題 式中若F（X）、 均為凸函數(shù)，則稱此問題為凸規(guī)劃。第21頁，共51頁，2022年，5月20日，19點3分，星期四凸規(guī)劃的一些性質(zhì)： 2）凸規(guī)劃問題中的任何局部最優(yōu)解都是全局最

9、優(yōu)解； 1）可行域 為凸集； 3）若F（X）可微，則X*為凸規(guī)劃問題的最優(yōu)解的充分必要條件為： 對任意 ，對滿足第22頁，共51頁，2022年，5月20日，19點3分，星期四 不論是無約束或有約束的優(yōu)化問題，在實際應用中，要證明一個優(yōu)化問題是否為凸規(guī)劃，一般比較困難，有時甚至比求解優(yōu)化問題本身還要麻煩。尤其對一些工程問題，由于其數(shù)學模型的性態(tài)都比較復雜，更難實現(xiàn)。因此，在優(yōu)化設(shè)計的求解中，就不必花精力進行求證，而通常是從幾個初始點出發(fā)，找出幾個局部最優(yōu)解，從中選擇目標函數(shù)值最好的解。注意：第23頁，共51頁，2022年，5月20日，19點3分，星期四一、 多元函數(shù)的泰勒展開2-3 無約束優(yōu)化問

10、題的極值條件 二元函數(shù)：第24頁，共51頁，2022年，5月20日，19點3分，星期四多元函數(shù)泰勒展開海色矩陣（Hessian）第25頁，共51頁，2022年，5月20日，19點3分，星期四二、無約束優(yōu)化問題的極值條件 1.F(x)在 處取得極值，其必要條件是: 即在極值點處函數(shù)的梯度為n維零向量。第26頁，共51頁，2022年，5月20日，19點3分，星期四例： 在 處梯度為但 只是雙曲拋物面的鞍點，而不是極小點。函數(shù)的梯度為零的條件僅為必要的，而不是充分的。 則稱 為f的駐點。定義：設(shè) 是D的內(nèi)點，若第27頁，共51頁，2022年，5月20日，19點3分，星期四根據(jù)函數(shù)在 點處的泰勒展開式

11、，考慮上述極值必要條件，可得相應的充分條件。 為了判斷從上述必要條件求得的 是否是極值點，需建立極值的充分條件。第28頁，共51頁，2022年，5月20日，19點3分，星期四2. 處取得極值充分條件第29頁，共51頁，2022年，5月20日，19點3分，星期四，.，各階主子式均大于零: 則海色（Hessian）矩陣 是正定的,即海色（Hessian）矩陣 負定的，則X*為極大點。 各階主子式負、正相間: 則X*為極小點。第30頁，共51頁，2022年，5月20日，19點3分，星期四例2-4：求目標函數(shù)f（X）=的梯度和Hessian矩陣。解：因為 則故Hessian陣為：第31頁，共51頁，2

12、022年，5月20日，19點3分，星期四例2-5 求函數(shù) 的極值。解：根據(jù)極值的必要條件求駐點得駐點 再根據(jù)極值的充分條件，判斷此點是否為極值點。由于其各階主子式均大于零，H(x*)為正定矩陣，故X*=2,4T為極小點，極小值為F(X*)= -13。第32頁，共51頁，2022年，5月20日，19點3分，星期四2-4 有約束優(yōu)化問題的極值條件 不等式約束的多元函數(shù)極值的必要條件是著名的庫恩-塔克（Kuhn-Tucker）條件，它是非線性優(yōu)化問題的重要理論1 庫恩塔克條件 (K-T條件）對于多元函數(shù)不等式的約束優(yōu)化問題： 第33頁，共51頁，2022年，5月20日，19點3分，星期四K-T條件可

13、闡述為：若 是一個局部極小點，則該點的目標函數(shù)梯度 可表示成諸起作用約束面梯度 的線性組合.即 (2-17)在設(shè)計點處的起作用約束不等式約束面數(shù)；非負值的乘子，也稱為拉格朗日乘子。式中第34頁，共51頁，2022年，5月20日，19點3分，星期四Ox1x2極值點處于等值線的中心極值點處于兩個約束曲線的交點上xg1 (x)0g2 (x)0g3 (x)0Ox1x2xg1(x)0g2(x)0第35頁，共51頁，2022年，5月20日，19點3分，星期四2 有約束問題最優(yōu)點的幾種情況:有作用約束 目標函數(shù)是凸函數(shù),可行域是凸集，則目標函數(shù)等值線與作用約束曲面的切點為最優(yōu)點，而且是全局最優(yōu)點。1. 無作

14、用約束 目標函數(shù)是凸函數(shù)，可行域是凸集，則最優(yōu)點是內(nèi)點。相當于無約束問題的最優(yōu)點。x (k) 為最優(yōu)點x*的條件：必要條件：充分條件： Hessian矩陣 H(x(k) 是正定矩陣X*f (x) x*第36頁，共51頁，2022年，5月20日，19點3分，星期四 庫恩塔克條件的幾何意義是: 在約束極小值點 x*處，函數(shù)F (x) 的負梯度一定能表示成所有起作用約束在該點梯度（法向量）的非負線性組合。第37頁，共51頁，2022年，5月20日，19點3分，星期四 K-T條件是多元函數(shù)取得約束極值的必要條件,以用來作為約束極值的判斷條件，又可以來直接求解較簡單的約束優(yōu)化問題。 對于目標函數(shù)和約束函

15、數(shù)都是凸函數(shù)的情況， 符合K-T條件的點一定是全局最優(yōu)點。這種情況K-T條件即為多元函數(shù)取得約束極值的充分必要條件。第38頁，共51頁，2022年，5月20日，19點3分，星期四 K-T條件是多元函數(shù)取得約束極值的必要條件,以用來作為約束極值的判斷條件，又可以來直接求解較簡單的約束優(yōu)化問題。例2-6 庫恩塔克（K-T）條件應用舉例 s.t判斷1 0T是否為約束最優(yōu)點。第39頁，共51頁，2022年，5月20日，19點3分，星期四(1)當前點 為可行點，因滿足約束條件(3) 各函數(shù)的梯度：（2）在 起作用約束為g1和g2 , 因 第40頁，共51頁，2022年，5月20日，19點3分，星期四（4

16、）求拉格朗日乘子由于拉格朗日乘子均為非負，說明是一個局部最優(yōu)點，因為它滿足K-T條件。第41頁，共51頁，2022年，5月20日，19點3分，星期四s.t第42頁，共51頁，2022年，5月20日，19點3分，星期四例2-7 對于約束極值問題s.t. 試運用K-T條件驗證點為約束極值點。解：圖例2-7給出了由g1(x)=0、 g2(x)=0、 g3(x)=0、及所確定的可行域，同時給出了的幾條等值線。 第43頁，共51頁，2022年，5月20日，19點3分，星期四 可見起作用的約束函數(shù)是和1. 計算點 的各個約束函數(shù)值例-7約束極值問題第44頁，共51頁，2022年，5月20日，19點3分，星期四2、求相關(guān)函數(shù)在 點的梯度3、將梯度代入判別公式，求拉格朗日乘子 即 第45頁，共51頁，2022年，5月20日，19點3分，星期四 均為非負，滿足K-T條件，因此同時，由于是凸函數(shù)，可行域是凸集，因此點也是全域最優(yōu)點。為約束極值點。和第46頁，共51頁，2022年，5月20日，19點3分，星期四設(shè)約束優(yōu)化問題 (課堂練習)它的當前迭代點為=1,0T，試用KT條件。判斷它是否為約束最優(yōu)點第47頁，共51頁，2022