優(yōu)化方法的數(shù)學(xué)基礎(chǔ)完整版

優(yōu)化方法的數(shù)學(xué)基礎(chǔ)§1方向?qū)?shù)與梯度§2凸集、凸函數(shù)與凸規(guī)劃§3二次函數(shù)及正定矩陣§4無約束優(yōu)化問題的極值條件§5有約束優(yōu)化問題的極值條件2023/11/7引例：一塊長方形的金屬板，中心在坐標原點處。在原點處有一個火焰，它使金屬板受熱．在(3,2)處有一個螞蟻，問這只螞蟻應(yīng)沿什么方向爬行才能最快到達較涼快的地點？問題的實質(zhì)：應(yīng)沿由熱變冷變化最驟烈的方向爬行．§1方向?qū)?shù)與梯度2023/11/7

討論函數(shù)在一點P沿某一方向的變化率問題．．引射線內(nèi)有定義，自點的某一鄰域在點設(shè)函數(shù)lPPUyxP)(),(),(,).(pUP'lyyxxPlxD+D+

上的另一點且為并設(shè)為的轉(zhuǎn)角軸正向到射線設(shè)j一、方向?qū)?shù)的定義2023/11/7當(dāng)沿著趨于時，且考慮板書三維圖2023/11/7}0,1{1=er依定義，函數(shù)),(yxf在點P沿著x軸正向、y軸正向}1,0{2=er的方向?qū)?shù)分別為yxff,沿著x軸負向、y軸負向的方向?qū)?shù)是

yxff--,.的方向?qū)?shù)．沿方向則稱這極限為函數(shù)在點在，時，如果此比的極限存趨于沿著當(dāng)之比值，兩點間的距離與函數(shù)的增量定義lPPlP'yxP'P

D+D=

22)()(r記為2023/11/7故有方向?qū)?shù)二、方向?qū)?shù)的計算2023/11/7例1

求函數(shù)yxez2=在點)0,1(P處沿從點

)0,1(P到點)1,2(-Q的方向的方向?qū)?shù).解故x軸到方向lr的轉(zhuǎn)角4p-=j.所求方向?qū)?shù)這里方向lr即為}1,1{-=PQ2023/11/7解由方向?qū)?shù)的計算公式知例2

求函數(shù)在點沿與x軸方向夾角為a的方向射線lr的方向?qū)?shù).問在怎樣的方向上此方向?qū)?shù)有

（1）最大值；

（2）最小值；

（3）等于零？2023/11/7故（1）當(dāng)4p=a時，方向?qū)?shù)達到最大值2;（3）當(dāng)43p=a和47p=a時，方向?qū)?shù)等于0.（2）當(dāng)45p=a時，方向?qū)?shù)達到最小值-22023/11/72023/11/7對于三元函數(shù)),,(zyxfu=，它在空間一點),,(zyxP沿著方向L的方向?qū)?shù)

，可定義為推廣可得三元函數(shù)方向?qū)?shù)的定義其中2023/11/7n元函數(shù)在點x0處沿s方向的方向?qū)?shù)：

2023/11/7三、

函數(shù)的梯度為函數(shù)F(x1，x2)在X0點處的梯度。梯度-向量?:最快沿哪一方向增加的速度函數(shù)在點問題X02023/11/7梯度的模：設(shè)s=2023/11/7

梯度方向是函數(shù)值變化最快的方向，而梯度的模就是函數(shù)變化率的最大值。設(shè)：則有為單位向量。梯度方向和s方向重合時，方向?qū)?shù)值最大。變化率為零?變化率最大?2023/11/7在幾何上表示一個曲面曲面被平面所截得所得曲線在xoy面上投影如圖等高線梯度為等高線上的法向量2023/11/7梯度兩個重要性質(zhì)：

性質(zhì)一函數(shù)在某點的梯度不為零，則必與過該點的等值面垂直；性質(zhì)二梯度方向是函數(shù)具有最大變化率的方向。圖

梯度方向與等值面的關(guān)系2023/11/7多元函數(shù)的梯度：2023/11/7函數(shù)的梯度方向與函數(shù)等值面相垂直，也就是和等值面上過x0的切線相垂直。

由于梯度的模因點而異，即函數(shù)在不同點處的最大變化率是不同的。因此，梯度是函數(shù)的一種局部性質(zhì)。梯度模：2023/11/7例3:求函數(shù)在點[3,2]T的梯度。在點x(1)=[3,2]T處的梯度為：解：2023/11/7例4求函數(shù)在點x1=

[3,2]T和

x2=[1,2]T的梯度,并作圖表示。解：2023/11/7則函數(shù)在X0處的最速下降方向是例5：試求目標函數(shù)在點處的最速下降方向，并求沿這個方向移動一個單位長度后新點的目標函數(shù)值。解：由于這個方向上的單位向量是：2023/11/7例5：試求目標函數(shù)在點處的最速下降方向，并求沿這個方向移動一個單位長度后新點的目標函數(shù)值。新點是這個方向上的單位向量是：0.722023/11/7練習(xí)：

求函數(shù)

yxzyxu2332222-+++=在點

)2,1,1(處的梯度，并問在

哪些點處梯度為零？解由梯度計算公式得在)0,21,23(0-P處梯度為0.2023/11/7幾個常用的梯度公式：2023/11/7在整個可行域中對任一X都有f（X）≥f（X*）時，則X*就是最優(yōu)點，且稱為全域最優(yōu)點或整體最優(yōu)點。若f（X*）為局部可行域中的極小值而不是整個可行域中的最小值時，則稱X*為局部最優(yōu)點或相對最優(yōu)點。最優(yōu)化設(shè)計的目標是全域最優(yōu)點。函數(shù)的凸性表現(xiàn)為單峰性。對于具有凸性特點的函數(shù)來說，其極值點只有一個，因而該點既是局部最優(yōu)點亦為全域最優(yōu)點。為了研究函數(shù)的凸性，現(xiàn)引入凸集的概念：§2凸集、凸函數(shù)與凸規(guī)劃2023/11/7一、凸集集合D為n維歐氏空間的一個凸集。圖

二維空間的凸集與非凸集X（1）、X（2）兩點之間的聯(lián)接直線，可用數(shù)學(xué)式表達為:式中為由0到1（0≤≤1）間的任意實數(shù)。2023/11/7二、凸函數(shù)

具有凸性（表現(xiàn)為單峰性）或只有唯一的局部最小值亦即全域最優(yōu)值的函數(shù)，稱為凸函數(shù)或單峰函數(shù)。其數(shù)學(xué)定義是：設(shè)f（X）為定義在凸集D上的函數(shù)，如果對任何實數(shù)α（0≤α≤1）以及對D中任意兩點X(1)、X(2)恒有:則f（X）為D上的凸函數(shù)，若不等式反向，則為凹函數(shù)。2023/11/7凸函數(shù)的幾何意義如圖所示：在凸函數(shù)函數(shù)值曲線上取任意兩點聯(lián)成一直線線段，則該線段上任一點的值必大于或等于兩點間的函數(shù)值。

圖4一元凸函數(shù)的幾何意義2023/11/7凸函數(shù)的一些性質(zhì)：

1）若

f（X）為定義在凸集D上的一個凸函數(shù)，且

a是一個正數(shù)（a>0），則

af（X）也必是定義在凸集D上的凸函數(shù)；

3）若f1(X），f2(X)為定義在凸集D上的兩個凸函數(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ù)一階導(dǎo)數(shù)的函數(shù)，則f（X）為凸函數(shù)的充分必要條件為：對任意兩點X（1），X（2），不等式恒成立：2023/11/72023/11/7三、凸規(guī)劃對于約束優(yōu)化問題式中若F（X）、均為凸函數(shù)，則稱此問題為凸規(guī)劃。2023/11/7凸規(guī)劃的一些性質(zhì)：

2）凸規(guī)劃問題中的任何局部最優(yōu)解都是全局最優(yōu)解；

3）若F（X）可微，則X*為凸規(guī)劃問題的最優(yōu)解的充分必要條件為：對任意，對滿足

1）可行域為凸集；2023/11/7不論是無約束或有約束的優(yōu)化問題，在實際應(yīng)用中，要證明一個優(yōu)化問題是否為凸規(guī)劃，一般比較困難，有時甚至比求解優(yōu)化問題本身還要麻煩。尤其對一些工程問題，由于其數(shù)學(xué)模型的性態(tài)都比較復(fù)雜，更難實現(xiàn)。因此，在優(yōu)化設(shè)計的求解中，就不必花精力進行求證，而通常是從幾個初始點出發(fā)，找出幾個局部最優(yōu)解，從中選擇目標函數(shù)值最好的解。注意：2023/11/7外，最簡單最重要的一類就是二次函數(shù)。在n元函數(shù)中，除了線性函數(shù)：或f(X)=aX+c§3二次函數(shù)及正定矩陣2023/11/7其中均為常數(shù)：其向量矩陣表示形式是：二次函數(shù)的一般形式為：其中Q=b=Q為對稱矩陣2023/11/7若，X≠0，均有＞0，則稱矩陣Q是正定的。

若，且X≠0，均有＜0，則稱Q是負定的。定義：設(shè)Q為n×n對稱矩陣在代數(shù)學(xué)中將特殊的二次函數(shù)稱為二次型。對于二次函數(shù)，我們更關(guān)心的是Q為正定矩陣的情形。2023/11/7解：對稱矩陣Q的三個主子式依次為：例：判定矩陣Q=是否正定一個n×n對稱矩陣Q是正定矩陣的充要條件是矩陣Q的各階主子式都是正的。一個n×n對稱矩陣Q是負定矩陣的充要條件是矩陣Q的各階主子式的值負、正相間。因此知矩陣Q是正定的。2023/11/7定理：若二次函數(shù)中Q正定，則它的等值面是同心橢球面族，且中心為前面已說過，一般目標函數(shù)的等值面在極小點附近近似地呈現(xiàn)為橢球面族。由此可見對于二次目標函數(shù)有效的求極小點的算法，當(dāng)用于一般目標函數(shù)時，至少在極小點附近同樣有效。特別地若算法對于Q為正定的二次目標函數(shù)能在有限步內(nèi)找出極小點來，就稱此算法為二次收斂算法，或具有二次收斂性。這族橢球面的中心是二次目標函數(shù)的唯一極小點。2023/11/72023/11/7求函數(shù)極值問題中，對復(fù)雜的問題，常用簡單函數(shù)來逼近，最簡單最重要的一類就是二次函數(shù)?！?無約束優(yōu)化問題的極值條件一元函數(shù)的泰勒展開2023/11/7一、多元函數(shù)的泰勒展開二元函數(shù)：二元函數(shù)：在點Xk處2023/11/7多元函數(shù)泰勒展開:海色矩陣（Hessian）2023/11/7對二次函數(shù)：為二次函數(shù)的海色（Hessian）矩陣，常量矩陣。2023/11/7例：求目標函數(shù)的梯度和Hesse矩陣。解：因為

則又因為：故Hesse陣為：2023/11/7例題:

用泰勒展開將函數(shù)在點簡化成線性函數(shù)與二次函數(shù)。解：函數(shù)在點的函數(shù)值、梯度和二階導(dǎo)數(shù)矩陣：2023/11/7簡化的線性函數(shù):簡化的二次函數(shù):2023/11/7二、無約束優(yōu)化問題的極值條件

1.F(x)在處取得極值，其必要條件是:即在極值點處函數(shù)的梯度為n維零向量。2023/11/7函數(shù)的梯度為零的條件僅為必要的，而不是充分的。則稱為f的駐點。定義：設(shè)是D的內(nèi)點，若:例：在處梯度為但只是雙曲拋物面的鞍點，而不是極小點。2023/11/7根據(jù)函數(shù)在點處的泰勒展開式，考慮上述極值必要條件，可得相應(yīng)的充分條件。為了判斷從上述必要條件求得的是否是極值點，需建立極值的充分條件。2023/11/72.處取得極值充分條件海色（Hessian）矩陣正定，即各階主子式均大于零，則X*為極小點。海色（Hessian）矩陣負定，即各階主子式負、正相間，則X*為極大點。正定或負定2023/11/7§5約束優(yōu)化問題的極值條件

不等式約束的多元函數(shù)極值的必要條件是著名的庫恩--塔克（Kuhn-Tucker）條件具有等式和不等式約束的優(yōu)化問題:2023/11/7圖約束問題的極值2023/11/7圖約束問題的極值2023/11/7圖約束問題的極值2023/11/7對于等式約束優(yōu)化問題：可以建立如下拉格朗日函數(shù)：令▽L(X,λ)=0：2023/11/7對于一般約束優(yōu)化問題：引入松弛變量2023/11/7庫恩—塔克條件表明：如點是函數(shù)的極值點，要么要么目標函數(shù)的負梯度等于起作用約束梯度的非負線性組合。對于一般約束優(yōu)化問題，K-T條件：2023/11/7x1x2Og2(x)=0g1(x)=0F(x)=C

g2(xk)

g1(xk)－

F(xk)xk可行域點xk處的切平面x1x2Og2(x)=0g1(x)=0F(x)=C

g2(xk)

g1(xk)－

F(xk)xk