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

關(guān)于優(yōu)化方法的數(shù)學(xué)基礎(chǔ)§2-1方向?qū)?shù)與梯度

一、函數(shù)的方向?qū)?shù)一個二元函數(shù)F(x1,x2)在X0點(diǎn)處的偏導(dǎo)數(shù)定義為:

分別是函數(shù)在點(diǎn)X0處沿坐標(biāo)軸方向的變化率.

第2頁,共51頁，2024年2月25日，星期天函數(shù)在點(diǎn)處沿某一方向的變化率如圖2-1稱它為函數(shù)沿此方向的方向?qū)?shù)

（2-1）第3頁,共51頁，2024年2月25日，星期天

和也可看成是函數(shù)分別沿坐標(biāo)軸方向的方向?qū)?shù)推導(dǎo)方向?qū)?shù)與偏導(dǎo)數(shù)之間的數(shù)量關(guān)系：偏導(dǎo)數(shù)是方向?qū)?shù)的特例（2-2）第4頁,共51頁，2024年2月25日，星期天n元函數(shù)在點(diǎn)x0處沿s方向的方向?qū)?shù)

Ox2x1x10x20x0

x1

x2

sxS

1

2圖2-3第5頁,共51頁，2024年2月25日，星期天二、梯度二元函數(shù)的梯度:

為函數(shù)F(x1，x2)在x0點(diǎn)處的梯度。第6頁,共51頁，2024年2月25日，星期天梯度的模：設(shè)梯度方向和s方向重合時，方向?qū)?shù)值最大。第7頁,共51頁，2024年2月25日，星期天

梯度方向是函數(shù)值變化最快的方向，而梯度的模就是函數(shù)變化率的最大值

。圖2-4梯度方向與等值線的關(guān)系設(shè)：則有

為單位向量。第8頁,共51頁，2024年2月25日，星期天多元函數(shù)的梯度第9頁,共51頁，2024年2月25日，星期天函數(shù)的梯度方向與函數(shù)等值面相垂直，也就是和等值面上過x0的一切曲線相垂直。

由于梯度的模因點(diǎn)而異，即函數(shù)在不同點(diǎn)處的最大變化率是不同的。因此，梯度是函數(shù)的一種局部性質(zhì)。梯度模：第10頁,共51頁，2024年2月25日，星期天梯度兩個重要性質(zhì)：性質(zhì)一函數(shù)在某點(diǎn)的梯度不為零，則必與過該點(diǎn)的等值面垂直；性質(zhì)二梯度方向是函數(shù)具有最大變化率的方向。圖2-5梯度方向與等值面的關(guān)系第11頁,共51頁，2024年2月25日，星期天例2-1

求二元函數(shù)在點(diǎn)沿和的方向?qū)?shù)。解：

因此，

同理：第12頁,共51頁，2024年2月25日，星期天例2-2求函數(shù)在點(diǎn)x(1)=[3,2]T的梯度。在點(diǎn)x(1)=[3,2]T處的梯度為：解：第13頁,共51頁，2024年2月25日，星期天例2-3：試求目標(biāo)函數(shù)在點(diǎn)處的最速下降方向。則函數(shù)在處的最速下降方向是解：由于第14頁,共51頁，2024年2月25日，星期天

當(dāng)極值點(diǎn)X*能使f（X*）在整個可行域中為最小值時，即在整個可行域中對任一X都有f（X）≥f（X*）時，則X*就是最優(yōu)點(diǎn)，且稱為全域最優(yōu)點(diǎn)或整體最優(yōu)點(diǎn)。若f（X*）為局部可行域中的極小值而不是整個可行域中的最小值時，則稱X*為局部最優(yōu)點(diǎn)或相對最優(yōu)點(diǎn)。最優(yōu)化設(shè)計的目標(biāo)是全域最優(yōu)點(diǎn)。為了判斷某一極值點(diǎn)是否為全域最優(yōu)點(diǎn)，研究一下函數(shù)的凸性很有必要。函數(shù)的凸性表現(xiàn)為單峰性。對于具有凸性特點(diǎn)的函數(shù)來說，其極值點(diǎn)只有一個，因而該點(diǎn)既是局部最優(yōu)點(diǎn)亦為全域最優(yōu)點(diǎn)。為了研究函數(shù)的凸性，現(xiàn)引入凸集的概念：§2-2凸集、凸函數(shù)與凸規(guī)劃第15頁,共51頁，2024年2月25日，星期天一、凸集

設(shè)D為n維歐氏空間中的一個集合，若其中任意兩點(diǎn)X(1)、X(2)之間的聯(lián)接直線都屬于D，則稱這種集合D為n維歐氏空間的一個凸集。圖2-6（a）是二維空間的一個凸集，而圖2-6（b）不是凸集。圖2-6二維空間的凸集與非凸集第16頁,共51頁，2024年2月25日，星期天X（1）、X（2）兩點(diǎn)之間的聯(lián)接直線，可用數(shù)學(xué)式表達(dá)為:式中為由0到1（0≤≤1）間的任意實(shí)數(shù)。凸集的性質(zhì)：1）若D為凸集，是一個實(shí)數(shù)，則集合D仍是凸集；2）若D和F均為凸集，則其和（或并）仍是凸集；3）任何一組凸集的積（或交）仍是凸集。第17頁,共51頁，2024年2月25日，星期天二、凸函數(shù)

具有凸性（表現(xiàn)為單峰性）或只有唯一的局部最優(yōu)值亦即全域最優(yōu)值的函數(shù)，稱為凸函數(shù)或單峰函數(shù)。其數(shù)學(xué)定義是：

設(shè)f（X）為定義在n維歐氏空間中的一個凸集D上的函數(shù)，如果對任何實(shí)數(shù)α（0≤α≤1）以及對D中任意兩點(diǎn)X(1)、X(2)恒有:

則f（X）為D上的凸函數(shù)，若不滿足上式，則為凹函數(shù)。第18頁,共51頁，2024年2月25日，星期天凸函數(shù)的幾何意義如圖2-7所示：圖2-7一元凸函數(shù)的幾何意義

在凸函數(shù)曲線上取任意兩點(diǎn)（對應(yīng)于X軸上的坐標(biāo)X(1)、X（2））聯(lián)成一直線線段，則該線段上任一點(diǎn)（對應(yīng)于X軸上的X(k)點(diǎn)）的縱坐標(biāo)Y值必大于或等于該點(diǎn)（X(k)）處的原函數(shù)值f(X(k))。第19頁,共51頁，2024年2月25日，星期天凸函數(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ù)的充分必要條件為：對任意兩點(diǎn)X（1），X（2），不等式恒成立第20頁,共51頁，2024年2月25日，星期天三、凸規(guī)劃

對于約束優(yōu)化問題

式中若F（X）、均為凸函數(shù)，則稱此問題為凸規(guī)劃。第21頁,共51頁，2024年2月25日，星期天凸規(guī)劃的一些性質(zhì)：2）凸規(guī)劃問題中的任何局部最優(yōu)解都是全局最優(yōu)解；1）可行域為凸集；3）若F（X）可微，則X*為凸規(guī)劃問題的最優(yōu)解的充分必要條件為：對任意，對滿足第22頁,共51頁，2024年2月25日，星期天

不論是無約束或有約束的優(yōu)化問題，在實(shí)際應(yīng)用中，要證明一個優(yōu)化問題是否為凸規(guī)劃，一般比較困難，有時甚至比求解優(yōu)化問題本身還要麻煩。尤其對一些工程問題，由于其數(shù)學(xué)模型的性態(tài)都比較復(fù)雜，更難實(shí)現(xiàn)。因此，在優(yōu)化設(shè)計的求解中，就不必花精力進(jìn)行求證，而通常是從幾個初始點(diǎn)出發(fā)，找出幾個局部最優(yōu)解，從中選擇目標(biāo)函數(shù)值最好的解。注意：第23頁,共51頁，2024年2月25日，星期天一、多元函數(shù)的泰勒展開§2-3無約束優(yōu)化問題的極值條件二元函數(shù)：第24頁,共51頁，2024年2月25日，星期天多元函數(shù)泰勒展開海色矩陣（Hessian）第25頁,共51頁，2024年2月25日，星期天二、無約束優(yōu)化問題的極值條件

1.F(x)在處取得極值，其必要條件是:即在極值點(diǎn)處函數(shù)的梯度為n維零向量。第26頁,共51頁，2024年2月25日，星期天例：在處梯度為但只是雙曲拋物面的鞍點(diǎn)，而不是極小點(diǎn)。函數(shù)的梯度為零的條件僅為必要的，而不是充分的。

則稱為f的駐點(diǎn)。定義：設(shè)是D的內(nèi)點(diǎn)，若第27頁,共51頁，2024年2月25日，星期天根據(jù)函數(shù)在點(diǎn)處的泰勒展開式，考慮上述極值必要條件，可得相應(yīng)的充分條件。

為了判斷從上述必要條件求得的是否是極值點(diǎn)，需建立極值的充分條件。第28頁,共51頁，2024年2月25日，星期天2.處取得極值充分條件第29頁,共51頁，2024年2月25日，星期天，..，，各階主子式均大于零:

則海色（Hessian）矩陣是正定的,即海色（Hessian）矩陣負(fù)定的，則X*為極大點(diǎn)。

各階主子式負(fù)、正相間:

則X*為極小點(diǎn)。第30頁,共51頁，2024年2月25日，星期天例2-4：求目標(biāo)函數(shù)f（X）=的梯度和Hessian矩陣。解：因為

則故Hessian陣為：第31頁,共51頁，2024年2月25日，星期天例2-5

求函數(shù)的極值。解：根據(jù)極值的必要條件求駐點(diǎn)得駐點(diǎn)再根據(jù)極值的充分條件，判斷此點(diǎn)是否為極值點(diǎn)。由于其各階主子式均大于零，H(x*)為正定矩陣，故X*=[2,4]T為極小點(diǎn)，極小值為F(X*)=-13。第32頁,共51頁，2024年2月25日，星期天§2-4有約束優(yōu)化問題的極值條件

不等式約束的多元函數(shù)極值的必要條件是著名的庫恩--塔克（Kuhn-Tucker）條件，它是非線性優(yōu)化問題的重要理論1庫恩—塔克條件(K-T條件）對于多元函數(shù)不等式的約束優(yōu)化問題：

第33頁,共51頁，2024年2月25日，星期天K-T條件可闡述為：若是一個局部極小點(diǎn)，則該點(diǎn)的目標(biāo)函數(shù)梯度可表示成諸起作用約束面梯度的線性組合.即(2-17)——在設(shè)計點(diǎn)處的起作用約束不等式約束面數(shù)；——非負(fù)值的乘子，也稱為拉格朗日乘子。式中第34頁,共51頁，2024年2月25日，星期天Ox1x2極值點(diǎn)處于等值線的中心極值點(diǎn)處于兩個約束曲線的交點(diǎn)上x﹡g1

(x)＝0g2

(x)＝0g3

(x)＝0Ox1x2x﹡g1(x)＝0g2(x)＝0第35頁,共51頁，2024年2月25日，星期天2有約束問題最優(yōu)點(diǎn)的幾種情況:有作用約束目標(biāo)函數(shù)是凸函數(shù),可行域是凸集，則目標(biāo)函數(shù)等值線與作用約束曲面的切點(diǎn)為最優(yōu)點(diǎn)，而且是全局最優(yōu)點(diǎn)。1.無作用約束目標(biāo)函數(shù)是凸函數(shù)，可行域是凸集，則最優(yōu)點(diǎn)是內(nèi)點(diǎn)。相當(dāng)于無約束問題的最優(yōu)點(diǎn)。x(k)

為最優(yōu)點(diǎn)x*的條件：必要條件：充分條件：Hessian矩陣H(x(k))

是正定矩陣··X*f(x)·x*第36頁,共51頁，2024年2月25日，星期天

庫恩—塔克條件的幾何意義是:在約束極小值點(diǎn)x*處，函數(shù)F(x)的負(fù)梯度一定能表示成所有起作用約束在該點(diǎn)梯度（法向量）的非負(fù)線性組合。第37頁,共51頁，2024年2月25日，星期天

K-T條件是多元函數(shù)取得約束極值的必要條件,以用來作為約束極值的判斷條件，又可以來直接求解較簡單的約束優(yōu)化問題。

對于目標(biāo)函數(shù)和約束函數(shù)都是凸函數(shù)的情況，符合K-T條件的點(diǎn)一定是全局最優(yōu)點(diǎn)。這種情況K-T條件即為多元函數(shù)取得約束極值的充分必要條件。第38頁,共51頁，2024年2月25日，星期天K-T條件是多元函數(shù)取得約束極值的必要條件,以用來作為約束極值的判斷條件，又可以來直接求解較簡單的約束優(yōu)化問題。例2-6庫恩—塔克（K-T）條件應(yīng)用舉例

s.t判斷[10]T是否為約束最優(yōu)點(diǎn)。第39頁,共51頁，2024年2月25日，星期天(1)當(dāng)前點(diǎn)為可行點(diǎn)，因滿足約束條件(3)各函數(shù)的梯度：（2）在起作用約束為g1和g2,因第40頁,共51頁，2024年2月25日，星期天（4）求拉格朗日乘子由于拉格朗日乘子均為非負(fù)，說明是一個局部最優(yōu)點(diǎn)，因為它滿足K-T條件。第41頁,共51頁，2024年2月25日，星期天s.t第42頁,共51頁，2024年2月25日，星期天例2-7

對于約束極值問題s.t.

試運(yùn)用K-T條件驗證點(diǎn)為約束極值點(diǎn)。解：圖例2-7給出了由g1(x)=0、g2(x)=0、g3(x)=0、及所確定的可行域，同時給出了的幾條等值線。

第43頁,共51頁，2024年2月25日，星期天

可見起作用的約束函數(shù)是和