第2章優(yōu)化方法的數(shù)學(xué)基礎(chǔ)

1、2-1 2-1 方向?qū)?shù)與梯度方向?qū)?shù)與梯度2-2 2-2 凸集、凸函數(shù)與凸規(guī)劃凸集、凸函數(shù)與凸規(guī)劃2-3 2-3 無約束優(yōu)化問題的極值條件無約束優(yōu)化問題的極值條件 2-4 2-4 有約束優(yōu)化問題的極值條件有約束優(yōu)化問題的極值條件 一、函數(shù)的方向?qū)?shù)一、函數(shù)的方向?qū)?shù)一個二元函數(shù)一個二元函數(shù)F(x1,x2)在在X0點處的偏導(dǎo)數(shù)定義為點處的偏導(dǎo)數(shù)定義為: 分別是函數(shù)在點分別是函數(shù)在點X0處沿坐標(biāo)軸方向的變化率處沿坐標(biāo)軸方向的變化率. 1020102101010),(),(lim)(1xxxFxxxFxFxX2020120201020),(),(lim)(2xxxFxxxFxFxX),(),(li

2、m)(020120210100 xxfxxxxFFSX2221)()(xx函數(shù) 在點 處沿某一方向的變化率如圖2-1 ),(21xxF0X稱它為函數(shù)沿此方向的方向?qū)?shù) （2-1） 和 也可看成是函數(shù)分別沿坐標(biāo)軸方向的方向?qū)?shù)推導(dǎo)方向?qū)?shù)與偏導(dǎo)數(shù)之間的數(shù)量關(guān)系：10)(xFX20)(xFX偏導(dǎo)數(shù)是方向?qū)?shù)的特例),(),(lim)(020120210100 xxFxxxxFFSX22021012021010110201021010),(),(lim),(),(limxxxxxFxxxxFxxxxFxxxF220110cos)(cos)(xFxFXX（2-2）n元函數(shù)在點元函數(shù)在點x0處沿處沿s

3、s方向的方向?qū)?shù)方向的方向?qū)?shù) 0000012121coscoscoscosnnniiiFFFFsxxxFxxxxxxOx2x1x10 x20 x0 x1 x2 sxS 1 2圖圖2-3二元函數(shù)的梯度: 0001212coscosFFFsxxxxx01212coscosFFxxx0010122()TFxFFFFxxxxxx為函數(shù)F(x1，x2)在x0點處的梯度。梯度的模：1212coscoscos,TFFFsxxFsFsF s 2212FFFxx設(shè)12coscoss梯度方向和s方向重合時，方向?qū)?shù)值最大。12coscoss 而梯度而梯度的模就是函數(shù)變化率的最大值的模就是函數(shù)變化率的最大值 。圖

4、圖2-4 梯度方向與等值線的關(guān)系梯度方向與等值線的關(guān)系000()() cos(, )TFFsFF ss xxx設(shè)：設(shè)：則有則有 為單位向量。為單位向量。0012012()TnnFxFFFFxFxxxFxxxx00001cos()() cos(, )nTiiiFFFFF ssx xxxdx012201()()niiFFxxx函數(shù)的梯度方向與函數(shù)等值面相垂直，也就是和等函數(shù)的梯度方向與函數(shù)等值面相垂直，也就是和等值面上過值面上過x0的一切曲線相垂直。的一切曲線相垂直。 由于梯度的模因點而異，即函數(shù)在不同點處的最大由于梯度的模因點而異，即函數(shù)在不同點處的最大變化率是不同的。因此，梯度是函數(shù)的一種變化

5、率是不同的。因此，梯度是函數(shù)的一種局部性局部性質(zhì)質(zhì)。0()Fxl梯度梯度 模：模：圖圖2-5 梯度方向與等值面的關(guān)系梯度方向與等值面的關(guān)系例例2-1 求二元函數(shù) 在點 沿 和 的方向?qū)?shù)。4)(221xxFX T1 , 10X44211S63212S解解：21212142)()()(xxxxFxFFXXX T1 , 10X42)(0XF 因此，666. 14cos44cos2cos)(cos)()(22011010 xFxFFXXSX 同理：465. 16cos43cos2)(20SXF求函數(shù)求函數(shù) 在點在點x(1)=3,2T 的的 梯度。梯度。22121( )44fxxxx112224( )

6、2fxxfxfxx(1)1(1)2242()24xxfx x在點在點x(1)=3,2T處的梯度為：處的梯度為：l解：解： 12121264,42fXfXxxxxxx 121211200121021644422xxxxfXxxxPfXxxfXx ：試求目標(biāo)函數(shù)：試求目標(biāo)函數(shù) 在點在點 處的處的最速下降方向。最速下降方向。2221212143,xxxxxxf00,1TX00,1TX則函數(shù)在則函數(shù)在 處的最速下降方向是處的最速下降方向是解：解： 由于由于 當(dāng)極值點當(dāng)極值點X X* *能使能使f f（X X* *）在整個可行域中為最小值時，即在整）在整個可行域中為最小值時，即在整個可行域中對任一個可行

7、域中對任一X X都有都有f f（X X）f f（X X* *）時，則）時，則X X* *就是最優(yōu)點，就是最優(yōu)點，且稱為且稱為。若。若f f（X X* *）為局部可行域中的）為局部可行域中的極小值而不是整個可行域中的最小值時，則稱極小值而不是整個可行域中的最小值時，則稱X X* *為為。最優(yōu)化設(shè)計的目標(biāo)是全域最優(yōu)點。為了判斷某一極。最優(yōu)化設(shè)計的目標(biāo)是全域最優(yōu)點。為了判斷某一極值點是否為全域最優(yōu)點，研究一下函數(shù)的凸性很有必要。值點是否為全域最優(yōu)點，研究一下函數(shù)的凸性很有必要。 函數(shù)的凸性表現(xiàn)為單峰性。對于具有凸性特點的函數(shù)來說，函數(shù)的凸性表現(xiàn)為單峰性。對于具有凸性特點的函數(shù)來說，其極值點只有一個，

8、因而該點既是局部最優(yōu)點亦為全域最優(yōu)點。其極值點只有一個，因而該點既是局部最優(yōu)點亦為全域最優(yōu)點。 為了研究函數(shù)的凸性，現(xiàn)引入凸集的概念：為了研究函數(shù)的凸性，現(xiàn)引入凸集的概念： 設(shè)設(shè)D D為為n n維歐氏空間中的一個集合，若其中任意兩點維歐氏空間中的一個集合，若其中任意兩點X X(1)(1)、X X(2)(2)之間的聯(lián)接直線都屬于之間的聯(lián)接直線都屬于D D，則稱這種集合，則稱這種集合D D為為n n維維歐氏空間的一個凸集。圖歐氏空間的一個凸集。圖2-62-6（a a）是二維空間的一個凸集，）是二維空間的一個凸集，而圖而圖2-62-6（b b）不是凸集。）不是凸集。圖圖2-6二維空間的凸集與非凸集二

9、維空間的凸集與非凸集X X（1 1）、X X（2 2）兩點之間的聯(lián)接直線，可用數(shù)學(xué)式表達(dá)為兩點之間的聯(lián)接直線，可用數(shù)學(xué)式表達(dá)為: :(1)(2)(1)XXX式中式中 為由為由0 0到到1 1（0 10 1）間的任意實數(shù)。）間的任意實數(shù)。凸集的性質(zhì)：凸集的性質(zhì)： 1 1）若）若D D為凸集，為凸集， 是一個實數(shù)，則集合是一個實數(shù)，則集合 D D仍是凸集；仍是凸集； 2 2）若）若D D和和F F均為凸集，則其和（或并）仍是凸集；均為凸集，則其和（或并）仍是凸集； 3 3）任何一組凸集的積（或交）仍是凸集。）任何一組凸集的積（或交）仍是凸集。 具有凸性（表現(xiàn)為單峰性）或只有唯一的局部最優(yōu)值具有凸性

10、（表現(xiàn)為單峰性）或只有唯一的局部最優(yōu)值亦即全域最優(yōu)值的函數(shù)，稱為亦即全域最優(yōu)值的函數(shù)，稱為。其數(shù)學(xué)。其數(shù)學(xué)定義是定義是： 設(shè)設(shè) f f（X X）為定義在）為定義在 n n維歐氏空間中的一個凸集維歐氏空間中的一個凸集D D上的函數(shù)，上的函數(shù)，如果對任何實數(shù)如果對任何實數(shù)（ 0 1 ）以及對）以及對D D中任意兩點中任意兩點X X(1)(1)、X X( (2)2)恒有恒有: :(1)(2)(1)(2)(1)() (1) ()fXXf Xf X 則則f f（X X）為）為D D上的上的凸函數(shù)凸函數(shù)，若不滿足上式，則為若不滿足上式，則為凹函數(shù)凹函數(shù)。凸函數(shù)凸函數(shù)的幾何意義如圖的幾何意義如圖2-72-7

11、所示：所示：圖圖2-7 一元凸函數(shù)的幾何意義一元凸函數(shù)的幾何意義 在凸函數(shù)曲線上取任意兩點（對應(yīng)于在凸函數(shù)曲線上取任意兩點（對應(yīng)于X軸上的坐標(biāo)軸上的坐標(biāo)X(1)、X（2）聯(lián)成一直線線段，則該線段上任一點（對應(yīng)于）聯(lián)成一直線線段，則該線段上任一點（對應(yīng)于X軸上軸上的的X(k)點）的縱坐標(biāo)點）的縱坐標(biāo)Y值必大于或等于該點（值必大于或等于該點（X(k)）處的原函）處的原函數(shù)值數(shù)值f(X(k)。 凸函數(shù)的一些性質(zhì)：凸函數(shù)的一些性質(zhì)： 1 1）若）若 f（X）為定義在凸集）為定義在凸集D D上的一個凸函數(shù)，且上的一個凸函數(shù)，且 a是一個是一個正數(shù)（正數(shù)（a 0），則），則 af（X）也必是定義在凸集）也

12、必是定義在凸集D D上的凸函數(shù)；上的凸函數(shù)； 3 3）若若f f1 1( (X X），），f f2 2( (X X) )為定義在凸集為定義在凸集D D上的兩個凸函數(shù)，上的兩個凸函數(shù)，和和為兩個任意正數(shù)，則函數(shù)為兩個任意正數(shù)，則函數(shù) afafl l（X X）ff2 2( (X X) )仍為仍為D D上的凸函數(shù)上的凸函數(shù)。 2 2）定義在凸集定義在凸集D D上的兩個凸函數(shù)上的兩個凸函數(shù)f f1 1( (X X），），f f2 2( (X X) )，其和，其和 f f（X X）=f=f1 1（X X）十）十f f2 2（X X）亦必為該凸集上的一個凸函數(shù)。）亦必為該凸集上的一個凸函數(shù)。 4 4）若若

13、f f（X X）為定義在凸集）為定義在凸集D D上且具有連續(xù)一階導(dǎo)數(shù)的函上且具有連續(xù)一階導(dǎo)數(shù)的函數(shù)，則數(shù)，則f f（X X）為凸函數(shù)的充分必要條件為：）為凸函數(shù)的充分必要條件為： 對任意兩點對任意兩點X X（1 1），X X（2 2），不等式，不等式(2)(1)(2)(1)(1)()() ()()Tf Xf XXXf X恒成立恒成立 對于約束優(yōu)化問題對于約束優(yōu)化問題12min()(),. .()01,2,nnjF XF xxxXRstgXjm ， ， ， 式中若式中若F F（X X）、 均均為凸函數(shù)，為凸函數(shù)，則稱此問題為則稱此問題為。()jgX凸規(guī)劃的一些性質(zhì)：凸規(guī)劃的一些性質(zhì)： 2 2）凸

14、規(guī)劃問題中的任何局部最優(yōu)解都是全局最優(yōu)解凸規(guī)劃問題中的任何局部最優(yōu)解都是全局最優(yōu)解；*()() 0TF XXX 1 1）可行域）可行域 為凸集；為凸集；()01,2,jDX gXjm 3 3）若若F F（X X）可微可微，則，則X X* *為凸為凸規(guī)劃問題規(guī)劃問題的的最優(yōu)解的最優(yōu)解的充分必充分必要條件為：要條件為： 對任意對任意 ，對滿足對滿足XD 不論是無約束或有約束的優(yōu)化問題，在實際應(yīng)用中，要證不論是無約束或有約束的優(yōu)化問題，在實際應(yīng)用中，要證明一個優(yōu)化問題是否為凸規(guī)劃，一般比較困難，有時甚至比求明一個優(yōu)化問題是否為凸規(guī)劃，一般比較困難，有時甚至比求解優(yōu)化問題本身還要麻煩。尤其對一些工程問

15、題，由于其數(shù)學(xué)解優(yōu)化問題本身還要麻煩。尤其對一些工程問題，由于其數(shù)學(xué)模型的性態(tài)都比較復(fù)雜，更難實現(xiàn)。因此，在優(yōu)化設(shè)計的求解模型的性態(tài)都比較復(fù)雜，更難實現(xiàn)。因此，在優(yōu)化設(shè)計的求解中，就不必花精力進(jìn)行求證，而通常是從幾個初始點出發(fā)，找中，就不必花精力進(jìn)行求證，而通常是從幾個初始點出發(fā)，找出幾個局部最優(yōu)解，從中選擇目標(biāo)函數(shù)值最好的解。出幾個局部最優(yōu)解，從中選擇目標(biāo)函數(shù)值最好的解。21( )()()()2kkTTkFFFF xxxxxxx22211220222212()FFxx xFFFx xx x111222kkxxxxxx x二元函數(shù)：二元函數(shù)：12()kkTnFFFFxxxxx222211212

16、22222122222212()()nkknnnnFFFxx xx xFFFxxxxxFH xFFFxxxxx x海色矩陣海色矩陣（Hessian）21( )()()()2kkTTkFFFF xxxxxxx12() 0TnFFFFxxxxx1.F(x)在在 處取得極值，其必要條件是處取得極值，其必要條件是: *x即在極值點處函數(shù)的梯度為即在極值點處函數(shù)的梯度為n維零向量。維零向量。l例：例： 在在 處梯度為處梯度為l但但 只是雙曲拋物面的鞍點，而不是極小點。只是雙曲拋物面的鞍點，而不是極小點。1212,.f x xx x*0,0TX 00,00f *Xx 則稱則稱 為為f的的。*X*0fX定義

17、：設(shè)定義：設(shè) 是是D的內(nèi)點，若的內(nèi)點，若:,nfDR*Xl根據(jù)函數(shù)在根據(jù)函數(shù)在 點處的泰勒展開式，考慮上述極點處的泰勒展開式，考慮上述極值必要條件，可得相應(yīng)的充分條件。值必要條件，可得相應(yīng)的充分條件。*x 為了判斷從上述必要條件求得的為了判斷從上述必要條件求得的 是否是極值是否是極值點，需建立極值的充分條件。點，需建立極值的充分條件。*x2222112122222*2122222212*()nnnnnFFFxx xx xFFFx xxx xFFFFx xx xx 正定或負(fù)定xx*x022211211aaaa011a0333231232221131211aaaaaaaaa021222211121

18、1nnnnnnaaaaaaaaa，.，各階主子式均大于零各階主子式均大于零: 則海色（則海色（Hessian）矩陣）矩陣 是是正定正定的的,即海色（即海色（Hessian）矩陣）矩陣 ，則，則X*為為。()Hx()Hx 各階主子式負(fù)、正相間各階主子式負(fù)、正相間: 則則X*為為。 2202220222Xf2, 2, 02, 2, 20, 2, 2322232132322222122312212212xfxxfxxfxxfxfxxfxxfxxfxf TxxxxxxxXf233122122, 3222,22 23322xxxXf 21122xxxXf 32223122xxxxXf2221231 22

19、 33223xxxxxx xx例例2-4：求目標(biāo)函數(shù)：求目標(biāo)函數(shù)f（X）=的梯度和的梯度和矩陣。矩陣。解：因為解：因為 則則故故陣為：陣為：例例2-5 求函數(shù) 的極值。解解：根據(jù)極值的必要條件求駐點得駐點 再根據(jù)極值的充分條件，判斷此點是否為極值點。由于其各階主子式均大于零，H(x*)為正定矩陣，故X*=2,4T為極小點，極小值為F(X*)= -13。784),(21222121xxxxxxF082)(042)(2211xxFxxFXXTX4 , 2*2002)()()()()(22*212*221*221*2*xFxxFxxFxFHXXXXX02 042002l 不等式約束的多元函數(shù)極值的必

20、要條件是著名的不等式約束的多元函數(shù)極值的必要條件是著名的庫恩庫恩-塔克（塔克（Kuhn-Tucker）條件，它是非線性優(yōu)化）條件，它是非線性優(yōu)化問題的重要理論問題的重要理論1 庫恩庫恩塔克條件塔克條件 (K-T條件）條件）l對于多元函數(shù)不等式的約束優(yōu)化問題：對于多元函數(shù)不等式的約束優(yōu)化問題：l min( )F x.( )0 (1,2, )jst gjmxlK-T條件可闡述為：l若 是一個局部極小點，則該點的目標(biāo)函數(shù)梯度 可表示成諸起作用約束面梯度 的線性組合.l即*X)(*XF)(*Xug (2-17)m在設(shè)計點處的起作用約束不等式約束面數(shù)；), 2 , 1(mjj非負(fù)值的乘子，也稱為拉格朗日

21、乘子。式中()()0mjjj JFgxxOx1x2極值點處于等值線的中心極值點處于兩個約束曲線的交點上xg1 (x)0g2 (x)0g3 (x)0Ox1x2xg1(x)0g2(x)00)()(kxf2 2 有約束問題最優(yōu)點的幾種情況有約束問題最優(yōu)點的幾種情況: :2.2. 有有作用約束作用約束 目標(biāo)函數(shù)是凸函數(shù)目標(biāo)函數(shù)是凸函數(shù), ,可行域是凸可行域是凸集，則目標(biāo)函數(shù)等值線與集，則目標(biāo)函數(shù)等值線與作用約作用約束束曲面的切點為最優(yōu)點，而且是曲面的切點為最優(yōu)點，而且是全局最優(yōu)點。全局最優(yōu)點。1. 1. 無作用約束無作用約束 目標(biāo)函數(shù)是凸函數(shù)，可行域是凸目標(biāo)函數(shù)是凸函數(shù)，可行域是凸集，則最優(yōu)點是內(nèi)點。

22、相當(dāng)于無約集，則最優(yōu)點是內(nèi)點。相當(dāng)于無約束問題的最優(yōu)點。束問題的最優(yōu)點。x x (k)(k) 為最優(yōu)點為最優(yōu)點x x* *的條件：的條件：必要條件：必要條件：充分條件：充分條件： Hessian矩陣矩陣 H(xH(x(k)(k) ) 是正定矩陣是正定矩陣X*0X1X2g3 (x) = 0g2 (x) = 0g1 (x) = 0f (x) x*)()(2kxg)()(kxF)()(1kxg)()(2kxg)()(kxF)()(1kxg()()0mjjj JFgxx 庫恩庫恩塔克條件的幾何意義是塔克條件的幾何意義是: 在約束極小值點在約束極小值點 x*處，處，函數(shù)函數(shù)F (x) 的負(fù)梯度一定能表示

23、成所有起作用約束在該的負(fù)梯度一定能表示成所有起作用約束在該點梯度（法向量）的非負(fù)線性組合。點梯度（法向量）的非負(fù)線性組合。 是多元函數(shù)取得約束極值的是多元函數(shù)取得約束極值的, ,以用來作為約束極值的判斷條件，以用來作為約束極值的判斷條件，又可以來直接求解較簡單的約束優(yōu)化問題。又可以來直接求解較簡單的約束優(yōu)化問題。 這種情況這種情況K-TK-T條件即為多元函數(shù)取條件即為多元函數(shù)取得約束極值的充分必要條件。得約束極值的充分必要條件。 K-T K-T條件是多元函數(shù)取得約束極值的必要條件條件是多元函數(shù)取得約束極值的必要條件, ,以用來作為約束極值的判斷條件，又可以來直接以用來作為約束極值的判斷條件，又

24、可以來直接求解較簡單的約束優(yōu)化問題。求解較簡單的約束優(yōu)化問題。例例2-6 2-6 庫恩庫恩塔克（塔克（K-TK-T）條件應(yīng)用舉例）條件應(yīng)用舉例 2212( )(2)minfxxx21122231( )1 0( )0( )0gxxgxgx xxxls.tl判斷判斷1 0T是否為約束最優(yōu)點。是否為約束最優(yōu)點。1211202(2)2()02xxxfxx1211022()11ixxxg x20()1gx(1)當(dāng)前點當(dāng)前點 為可行點，因滿足約束條件為可行點，因滿足約束條件(1)10Tx(1)1(1)2(1)3()0()0()10ggg xxx(3) 各函數(shù)的梯度：各函數(shù)的梯度：（2）在）在 起作用約束為

25、起作用約束為g1和和g2 , 因因 (1)10Tx(1)3()0gx1122()()()fggxxx121010（4）求拉格朗日乘子）求拉格朗日乘子l由于拉格朗日乘子均為非負(fù)，說明由于拉格朗日乘子均為非負(fù)，說明是一個局部最優(yōu)點，因為它滿足是一個局部最優(yōu)點，因為它滿足K-T條件。條件。(1)1 0Tx10 120 2212212min( )(2)fxxx21122231( )1 0( )0( )0gxxgxgx xxxls.t例例2-7 對于約束極值問題2221)3()(minxxFXs.t. 04)(2211xxgX0)(22xgX0)(13xg X試運用K-T條件驗證點T0 , 2*X為約束極值點。解解：圖例例2-7給出了由g1(x)=0、 g2(x)=0、 g3(x)=0、及所確定的可行域，同時給出了的幾條等值線。 0404)(1Xg0)(2Xg02)(3Xg可見起作