02九月202313-1優(yōu)化設(shè)計問題的幾何意義一、目標(biāo)函數(shù)的等值面(線)n維變量的目標(biāo)函數(shù)，其函數(shù)圖象只能在n+1維空間中描述出來第3章優(yōu)化設(shè)計理論基礎(chǔ)02九月20232二維無約束最優(yōu)化設(shè)計02九月20233給定一個設(shè)計方案，即給定一組

x1,x2,…,xn的值時目標(biāo)函數(shù)f(X)=f(x1,x2,…,xn)必相應(yīng)有一確定的函數(shù)值02九月20234給定一個f(X)有無限多組值x1,x2,…,xn與之對應(yīng)當(dāng)f(X)=a時X=[x1,x2,…,xn]T在設(shè)計空間中對應(yīng)有一個點(diǎn)集目標(biāo)函數(shù)的等值面（線）該點(diǎn)集是一個曲面(二維是曲線，大于三維稱超曲面)02九月20235f(X(1))=a2f(X)=a1f(X)=a2f(X)=a3f(X)=a4f(X(2))=a2X(2)=[x1(2),x2(2)]X(1)=[x1(1),x2(1)]Of(X)x2x1X*02九月20236給定一系列的a值即a=a1,a2,…,an時一組超曲面族f(X)=a1,a2,…,an

等值面族該組超曲面族02九月20237等值面特性即在一個特定的等值面上，盡管設(shè)計方案很多，但每一個設(shè)計方案的目標(biāo)函數(shù)值都是相等的。二維無約束最優(yōu)化設(shè)計問題幾何意義以x1,x2和f(X)為坐標(biāo)f(X)=f(x1,x2)為沿軸方向的高度等值線是等值面在二維設(shè)計空間中的特定形態(tài)f(X(1))=a2f(X)=a1f(X)=a2f(X)=a3f(X)=a4f(X(2))=a2X(2)=[x1(2),x2(2)]X(1)=[x1(1),x2(1)]Of(X)x2x1X*02九月2023802九月20239等值線族當(dāng)給定一系列不同的a值時，可以得到一組平面曲線：f(X)=f(x1,x2)=a1f(X)=f(x1,x2)=a2…這組曲線構(gòu)成目標(biāo)函數(shù)的等值線族02九月202310等值線的分布反映目標(biāo)函數(shù)值的變化等值線越向里，目標(biāo)函數(shù)值越小有中心的曲線族目標(biāo)函數(shù)的無約束極小點(diǎn)就是等值線族的一個共同中心X*02九月202311幾何意義---求目標(biāo)函數(shù)無約束極小點(diǎn)也就是求其等值線族的共同中心。由二維設(shè)計空間等值線的討論，可推廣到分析多維問題。02九月202312注意，對于三維問題在設(shè)計空間中是等值面高于三維的問題在設(shè)計空間中則是等值超曲面02九月202313例二維約束優(yōu)化問題x1x2f(x)f(x)g(x)g1(x)g2(x)O02九月202314二維目標(biāo)函數(shù)等值線族

以點(diǎn)(2，0)為圓心，以為半徑的一族同心圓02九月202315x2x1X*1g4(X)g3(X)g1(X)g1(X)X*20.25f(X)=12.253.846.25f(X)=912123O02九月202316等值面（線）的形狀及其分布規(guī)律對于目標(biāo)函數(shù)極小化問題，愈靠近極值點(diǎn)的等值面（線）所代表的目標(biāo)函數(shù)值愈?。辉跇O值點(diǎn)附近的等值線呈現(xiàn)橢圓形狀，其中心就是極值點(diǎn)；在等值線較稠密的部位，目標(biāo)函數(shù)值變化愈迅速；目標(biāo)函數(shù)的非線性程度愈嚴(yán)重，其等值線的形狀愈復(fù)雜，且可能存在多個極值點(diǎn)。二維目標(biāo)函數(shù)等值線形態(tài)分析02九月202317X1*x1x201123X2*X3*x1x2012323456X1*02九月202318無約束最優(yōu)化最優(yōu)點(diǎn)就是目標(biāo)函數(shù)的極值點(diǎn)實(shí)際上就是目標(biāo)函數(shù)等值線的中心約束最優(yōu)化最優(yōu)點(diǎn)往往是目標(biāo)函數(shù)等值超曲面與約束超曲面的一個切點(diǎn)而且可能在兩個以上約束超曲面的交集上區(qū)別無論在數(shù)學(xué)模型還是幾何意義上，兩者均是不同的概念。3-2約束最優(yōu)解和無約束最優(yōu)解

二維優(yōu)化問題進(jìn)行幾何描述例

對二維優(yōu)化問題進(jìn)行幾何描述。02九月202319約束線、可行域、目標(biāo)函數(shù)等值線、約束極值點(diǎn)213x221-1-2-3-1-2-4-5x1f(X)X*g1(X)g2(X)0幾何意義上來說明約束最優(yōu)解和無約束最優(yōu)解設(shè)已知目標(biāo)函數(shù)f(X)=x12+x22-4x1+4，受約束于g1(X)=x1-x2+2

0g2(X)=x1

0g3(X)=x2

0

g4(X)=-x12+x2-1

0

求其最優(yōu)解X*和f(X*)。02九月20232002九月202321x1x2x2x1f(X)f(X)g1(X)g4(X)Og2(X)g4(X)g1(X)g3(X)f(X)等值線6.2543.810.251234O-212X*(1)X*(2)(b)(a)D02九月202322二維問題關(guān)于約束最優(yōu)解和無約束最優(yōu)解幾何意義的討論．同樣可推廣到高維問題n個設(shè)計變量x1,x2,…,xn，組成設(shè)計空間。在這個空間中的每一個點(diǎn)代表一個設(shè)計方案，此時n個變量具有確定的值。3-3局部最優(yōu)解和全域最優(yōu)解

02九月202323目標(biāo)函數(shù)不是單峰函數(shù)有多個極值點(diǎn)X1*,X2*,…,02九月202324X2*X1*f(X)x2x102九月202325局部最優(yōu)解X1*和f(X1*)、X2*和f(X2*)全域最優(yōu)解目標(biāo)函數(shù)值是全區(qū)域中所有局部最優(yōu)解中的最小者對應(yīng)的解02九月202326如圖，目標(biāo)函數(shù)f(X)的等值線繪于圖上，有兩個不等式約束g1(X)0,g2(X)0構(gòu)成兩個可行域D1和D2。02九月202327局部最優(yōu)解X1*、f(X1*)X2*、f(X2*)X3*、f(X3*)均稱局部最優(yōu)解。全域最優(yōu)解由于f(X1*(1))

f(X2*(2))

f(X3*(3))可知X3*(3)為全域極小點(diǎn)，亦即X3*(3)和f(X3*(3))為全域最優(yōu)解。02九月202328期望求出全域最優(yōu)解實(shí)際只能求出局部最優(yōu)解措施局部最優(yōu)解之間比較，取最小的一個3-4無約束目標(biāo)函數(shù)的極值點(diǎn)存在條件

一、函數(shù)的極值與極值點(diǎn)以一元函數(shù)為例說明函數(shù)的極值與極值點(diǎn)。如圖所示為定義在區(qū)間[a，b]上的一元函數(shù)f(X)02九月20232902九月202330f(x)xf(a)f(x(1))f(x(2))x(1)f(x(3))f(b)x(3)x(2)ab

圖上有兩個特殊點(diǎn)x(1)與x(2)

在x(1)附近，函數(shù)f(x)的值以f(x(1))為最大；在x(2)附近，函數(shù)值以f(x(2))為最小。02九月202331因此x(1)與x(2)即為函數(shù)的極大點(diǎn)與極小點(diǎn)，統(tǒng)稱為函數(shù)f(x)的極值點(diǎn)。f(x(1))與f(x(2))相應(yīng)地為函數(shù)的極大值與極小值，統(tǒng)稱為函數(shù)f(x)的極值。02九月202332需要注意，這里所謂極值是相對于—點(diǎn)的附近鄰域各點(diǎn)而言的，僅具有局部的性質(zhì)，所以這種極值又稱為局部極值。02九月202333函數(shù)的最大值與最小值是指整個區(qū)間而言的。如圖中函數(shù)的最大值為f(b)，函數(shù)的最小值為f(a)。函數(shù)的極值并不一定是最大值或最小值。02九月202334二、極值點(diǎn)存在的條件

(一)一元函數(shù)(即單變量函數(shù))的情況

(1)極值點(diǎn)存在的必要條件02九月202335在高等數(shù)學(xué)中已經(jīng)學(xué)過：如果函數(shù)f(x)的一階導(dǎo)數(shù)f’(x)存在，則欲使x*為極值點(diǎn)的必要條件為：f’(x*)＝002九月202336仍以圖中所示一元函數(shù)為例，由圖可見，在x(1)與x(2)處的f’(x(1))與f’(x(2))均等于零，即函數(shù)在該兩點(diǎn)處的切線與x軸平行。但使f’(x)＝0的點(diǎn)并不一定都是極值點(diǎn)。02九月20233702九月202338f(x)xf(a)f(x(1))f(x(2))x(1)f(x(3))f(b)x(3)x(2)ab使函數(shù)f(x)的一階導(dǎo)數(shù)f’(x)＝0的點(diǎn)稱為函數(shù)的駐點(diǎn)。極值點(diǎn)(對存在導(dǎo)數(shù)的函數(shù))必為駐點(diǎn)駐點(diǎn)不一定是極值點(diǎn)駐點(diǎn)是否為極值點(diǎn)可以通過二階導(dǎo)數(shù)f’’(x)來判斷。02九月202339(2)極值點(diǎn)存在的充分條件若在駐點(diǎn)附近f’’(x)0則該點(diǎn)為極大點(diǎn)；若在駐點(diǎn)附近f’’(x)0則該點(diǎn)為極小點(diǎn)。02九月202340在圖中的x(3)附近，其右側(cè)f’’(x)0，但其左側(cè)f’’(x)0，因此它不是極值點(diǎn)?？梢?，函數(shù)二階導(dǎo)數(shù)的符號成為判斷極值點(diǎn)的充分條件。02九月202341函數(shù)的偏導(dǎo)數(shù)偏導(dǎo)數(shù)是指在某坐標(biāo)軸方向函數(shù)值的變化率連續(xù)可微的n

維函數(shù)f(X)=f(x1,x2,…,xn)，在點(diǎn)X(K)=[x1(K),

x2(K),…,xn(K)]T的一階偏導(dǎo)數(shù)表示為，…，三、多元函數(shù)的方向?qū)?shù)、梯度和赫賽矩陣函數(shù)的梯度

n維函數(shù)的梯度是函數(shù)各維一階偏導(dǎo)數(shù)組成的向量02九月202343梯度的模是函數(shù)各維一階偏導(dǎo)數(shù)平方和的開方梯度與它的模的比值稱為梯度的單位向量02九月202344函數(shù)梯度的性質(zhì)1、函數(shù)的梯度

f(X(K))是函數(shù)在點(diǎn)X(K)的最速上升方向，而負(fù)梯度-

f(X(K))是函數(shù)在點(diǎn)X(K)的最快下降方向。

函數(shù)的梯度隨著點(diǎn)X(K)在設(shè)計空間的位置不同而異，這只是反映了函數(shù)在點(diǎn)X(K)

鄰域內(nèi)函數(shù)的局部性質(zhì)。02九月2023452、函數(shù)梯度的模是在點(diǎn)X(K)函數(shù)變化率的最大值。

3、函數(shù)的梯度

f(X(K))與在點(diǎn)X(K)的函數(shù)等值面正交。與點(diǎn)X(K)的函數(shù)等值面相切方向的函數(shù)變化率為零。02九月20234602九月202347X(K)x1x2O上升方向變化率為零的方向（切線方向）下降方向最速下降方向最速上升方向（法線方向）▽f(X(K))－▽f(X(K))02九月202348注意，函數(shù)f(X)在某點(diǎn)X(K)的梯度向量

f(X(K))僅反映f(X)在點(diǎn)X(K)附近極小鄰域的性質(zhì)．因而是一種局部性質(zhì)。函數(shù)在定義域內(nèi)的各點(diǎn)都各自對應(yīng)著一個確定的梯度。函數(shù)的赫森矩陣

函數(shù)的二階偏導(dǎo)數(shù)矩陣它是一個n×n階的對稱矩陣02九月202349赫森矩陣正定和負(fù)定的判定如果赫森矩陣行列式各階主子式全部大于零，即02九月202350則它是正定的。如果各階主子式是相間的一負(fù)一正，則它是負(fù)定的。02九月202351…設(shè)f(x)為定義在XDRn中的n元函數(shù)。向量X的分量x1,x2,…,xn，就是函數(shù)的自變量。設(shè)x(k)為定義域內(nèi)的—個點(diǎn)，且在該點(diǎn)有連續(xù)的n＋1階偏導(dǎo)數(shù)，則在該點(diǎn)附近可用泰勒級數(shù)展開，如取到二次項02九月202352多元函數(shù)的極值條件02九月202353如用向量矩陣形式表示，則上式可寫為

02九月202354可簡寫為02九月202355式中

02九月202356

f(X(k))是函數(shù)f(X)在點(diǎn)X(k)的一階偏導(dǎo)數(shù)矩陣，稱為函數(shù)在該點(diǎn)的梯度。

2f(X(k))是函數(shù)f(X)在點(diǎn)X(k)的二階偏導(dǎo)數(shù)組成的，n

n階對稱矩陣，或稱為f(X(k))的赫森(Hessian)矩陣，記作H(X(k))。02九月202357公式中只取到泰勒級數(shù)二次項，稱為函數(shù)的二次近似表達(dá)式。極值點(diǎn)存在的必要條件。n元函數(shù)在定義域內(nèi)極值點(diǎn)X*存在的必要條件

02九月202358即對每一個變量的一階偏導(dǎo)數(shù)值必須為零，或者說梯度為零(n維零向量)。與一元函數(shù)對應(yīng)，滿足梯度為零只是多元函數(shù)極值點(diǎn)存在的必要條件，而并非充分條件；02九月202359滿足

f(X*)的點(diǎn)X*稱為駐點(diǎn)駐點(diǎn)是否為極值點(diǎn)，尚須通過二階偏導(dǎo)數(shù)矩陣來判斷。02九月202360極值點(diǎn)存在充分條件

如何判斷多元函數(shù)的一個駐點(diǎn)是否為極值點(diǎn)呢?

將多元函數(shù)f(X)在駐點(diǎn)X*附近用泰勒公式的二次式近似地表示，則由式得02九月202361由X*為駐點(diǎn)，

f(X*)=0，于是有02九月202362在X*點(diǎn)附近的鄰域內(nèi)，若對一切的X恒有亦即02九月202363

則X*為極小點(diǎn)

否則，當(dāng)恒有則X*為極大點(diǎn)

根據(jù)矩陣?yán)碚撝?，由式得極小點(diǎn)的充分條件為：02九月202364亦即駐點(diǎn)赫森矩陣H(X*)必須為正定

同理知極大點(diǎn)的充分條件為：02九月202365亦即駐點(diǎn)赫森矩陣H(X*)必須為負(fù)定。而當(dāng)02九月202366亦即駐點(diǎn)赫森矩陣H(X*)既非正定，又非負(fù)定，而是不定，f(X)在X*處無極值。

至于對稱矩陣正定、負(fù)定的檢驗(yàn)，由線性代數(shù)可知：對稱矩陣02九月202367正定的條件是它的行列式|A|的順序主子式全部大于零，即02九月202368……

…負(fù)定的條件是它的行列式|A|中一串主子式為相間的一負(fù)一正的，即02九月202369

至此，完全不難自行歸納得出無約束目標(biāo)函數(shù)極值點(diǎn)存在的充分必要條件和用數(shù)學(xué)分析作為工具對n維無約束優(yōu)化問題尋求最優(yōu)解。02九月202370無約束目標(biāo)函數(shù)的極值條件

必要條件：在點(diǎn)X*=[x1*,x2*,…,xn*]T的一階偏導(dǎo)數(shù)為零（即梯度向量為零向量）

02九月202371充分條件：如果它的二階偏導(dǎo)數(shù)矩陣（即赫森矩陣）是負(fù)定的，則為極大點(diǎn)；如果它的二階偏導(dǎo)數(shù)矩陣是正定的，則為極小點(diǎn)。02九月202372求三維函數(shù)的極值點(diǎn)。

解：根據(jù)三維函數(shù)存在極值的必要條件，令梯度為零

02九月202373聯(lián)解得到02九月202374計算點(diǎn)的赫森矩陣

赫森矩陣行列式各階主子式

02九月20237502九月202376赫森矩陣是正定的，是極小點(diǎn)。對應(yīng)的目標(biāo)函數(shù)值02九月20237702九月202378最優(yōu)值指全域而言極值局部的性質(zhì)一般來說，在函數(shù)定義的區(qū)域內(nèi)部，最優(yōu)點(diǎn)必是極值點(diǎn)，反之卻不一定。3-5函數(shù)的凸性

02九月202379x1x2x1x2OODX(2)X(1)X(2)X(1)D(a)(b)一、凸集與非凸集

設(shè)D為n維歐氏空間中設(shè)計點(diǎn)X的一個集合，若其中任意兩點(diǎn)x(1)和x(2)的連線都在集合中，則稱這種集合是n維歐氏空間的一個凸集。二維函數(shù)的情況如圖所示，其中圖(a)為凸集，圖(b)為非凸集02九月202380凸集的概念02九月202381凸集的定義定義：設(shè)集合S

Rn，若x(1),x(2)

S,

[0,1]，必有

x(1)＋(1-

)x(2)

S，則稱S為凸集。規(guī)定：單點(diǎn)集{x}為凸集，空集

為凸集。注:

x(1)＋(1-

)x(2)=x(2)＋

(x(1)-x(2))

是連接x(1)與x(2)的線段。02九月202382凸集非凸集凸集02九月202383二、凸函數(shù)最優(yōu)值最優(yōu)值與極值之間的關(guān)系目標(biāo)函數(shù)的凸性性質(zhì)02九月202384凸函數(shù)的概念xx(2)x*x(1)Of(x)f(x(1))f(x*)f(x(2))xf(x)x(2)x*x(1)Of(x(1))f(x(2))f(x*)(a)(b)用一元函數(shù)來說明函數(shù)的凸性。如圖所示，圖(a)在x(1)、x(2)區(qū)間曲線為下凸的，圖(b)的曲線是上凸的，它們的極值點(diǎn)(極小點(diǎn)或極大點(diǎn))在區(qū)間內(nèi)都是唯一的。這樣的函數(shù)稱為具有凸性的函數(shù)，或稱為單峰函數(shù)。02九月20238502九月202386凸函數(shù)的定義定義：設(shè)f(X)為定義在n維歐氏空間中一個凸集D上的函數(shù)，若對任何實(shí)數(shù)

(01)及D域中任意兩點(diǎn)X(1)與X(2)存在如下關(guān)系：則稱函數(shù)f(X)是定義在凸集D上的一個凸函數(shù)。

02九月202387Of(x)xx(1)x(k)x(2)f(x(1))f(x(2))f[ξx(1)+(1-ξ)x(2)]ξf(x(1))+(1-ξ)f(x(2))現(xiàn)用上圖所示定義于區(qū)間[a,b]的單變量函數(shù)來說明這一概念。若連接函數(shù)曲線上任意兩點(diǎn)的直線段，某一點(diǎn)x(k)的函數(shù)值恒低于此直線段上相應(yīng)的縱坐標(biāo)值時，這種函數(shù)就是凸函數(shù)，也就是單峰函數(shù)。02九月202388

若將式中的符號“≤”改為“

”則稱函數(shù)f(X)為嚴(yán)格凸函數(shù)。02九月20238902九月202390凸函數(shù)區(qū)間[a,b]單峰函數(shù)符號“≤”函數(shù)f(X)為凸函數(shù)符號“

”函數(shù)f(X)為嚴(yán)格凸函數(shù)

若將式中的符號“≤”改為“≥”，函數(shù)曲線上凸(有極大點(diǎn))通常稱為凹函數(shù)。顯然，若為凸函數(shù)，則-f(X)凹函數(shù)。02九月202391

三、凸函數(shù)的基本性質(zhì)1）若函數(shù)f1(X)和f2(X)為凸集上的兩個凸函數(shù)，對任意正數(shù)a和bf(X)＝af1(X)+bf2(X)

仍為D集上的凸函數(shù)；02九月2023922)若X(1)與X(2)為凸函數(shù)f(X)中的兩個最小點(diǎn)，則其連線上的一切點(diǎn)也都是f(X)的最小點(diǎn)。02九月202393四、凸函數(shù)的判定判別法1：若函數(shù)f(X)在D上具有連續(xù)一階導(dǎo)數(shù)，而D為D1內(nèi)部的一個凸集，則f(X)為D上的凸函數(shù)的充分必要條件為：對任意的X(1)與X(2)

，恒有02九月202394判別法2：若函數(shù)f(X)在凸集D上存在二階導(dǎo)數(shù)并且連續(xù)時，對f(X)在D上為凸函數(shù)的充分必要條件為：對于任意的XD，

f(X)的赫森矩陣H(X)處處是正半定矩陣。02九月202395若赫森矩陣H(X)對一切XD都是正定的，則f(X)是D上的嚴(yán)格凸函數(shù)，反之不一定成立。02九月202396五、函數(shù)的凸性與局部極值及全域最優(yōu)值之間的關(guān)系

設(shè)f(X)為定義在凸集D上的一個函數(shù)，一般來說，f(X)的極值點(diǎn)不一定是它的最優(yōu)點(diǎn)。但是，若f(X)為凸集D上的一個凸函數(shù)，則f(X)的任何極值點(diǎn)，同時也是它的最優(yōu)點(diǎn)。若f(X)還是嚴(yán)格凸函數(shù)，則它有唯一的最優(yōu)點(diǎn)。02九月202397六約束極值點(diǎn)存在條件1有約束的極值問題02九月202398gi(X)≥0不等式約束，hj(X)=0等式約束02九月202399

在約束條件下求得的函數(shù)極值點(diǎn)，稱為約束極值點(diǎn)。

2不等式約束問題的一階最優(yōu)性條件

02九月2023100起作用約束不起作用約束

02九月2023101x1x2x2x1f(X)f(X)g1(X)g4(X)Og2(X)g4(X)g1(X)g3(X)f(X)等值線6.2543.810.251234O-212X*(1)X*(2)(b)(a)D起作用約束下標(biāo)集合用I表示02九月2023102或

在優(yōu)化實(shí)用計算中常需判斷和檢查某個可行點(diǎn)是否約束極值點(diǎn)，這通常借助于庫恩-塔克(Kuhn—Tucker)條件(簡稱K-T條件)來進(jìn)行。02九月2023103K-T條件可闡述為：如果X(k)是一個局部極小點(diǎn)，則該點(diǎn)的目標(biāo)函數(shù)梯度

f(X(k))可表示成該點(diǎn)諸約束面梯度

gi(X(k))的如下線性組合：

gi(iI)在X(k)處可微；gi(iI)在X(k)處連續(xù)；

gi(X(k))(iI)線性無關(guān)02九月202310402九月2023105gi(iI)在X(k)處也可微，可寫成等價形式iI時，gi0，wi＝0iI時，gi=0，對wi無限制wig(X(k))=0，i=1，2，…，m稱為互補(bǔ)松弛條件；wi

0，i=1，2，…，m，亦稱拉格朗日乘子。02九月2023106

等式約束性問題的最優(yōu)性條件幾何意義是明顯的：考慮一個約束的情況：最優(yōu)性條件即：02九月2023107-▽f(x2*)x2*

▽h(x2*)h(x)-▽f(x1*)▽h(x1*)這里x1*---l.opt.▽f(x1*)與▽h(x1*)

共線，而x2*非l.opt.▽f(x2*)

與▽h(x2*)不共線。3一般約束問題的一階最優(yōu)性條件

02九月2023108

如果x*是l.opt.,對每一個約束函數(shù)來說，只有當(dāng)它是起作用約束時，才產(chǎn)生影響，如：02九月2023109g2(x)=0x*g1(x)=0g1(x*)=0,g1為起作用約束K-T條件可闡述為：如果X(k)是一個局部極小點(diǎn)，則該點(diǎn)的目標(biāo)函數(shù)梯度

f(X(k))可表示成該點(diǎn)諸約束面梯度

gi(X(k))的如下線性組合：

f、gi(iI)在X(k)處可微gi(iI)在X(k)處連續(xù)hj(X(k))(j=1，2，…，l)在X(k)處連續(xù)可微02九月202311002九月2023111gi(iI)在X(k)處也可微，可寫成等價形式02九月2023112wig(X（k）)=0，i=1，2，…，m仍稱為互補(bǔ)松弛條件

可以對K-T條件用圖形來說明。如果X(k)是一個局部極小點(diǎn)，則該點(diǎn)的目標(biāo)函數(shù)梯度

f(X(k))應(yīng)落在該點(diǎn)諸約束面梯度

gi(X(k))、

hj(X(k))在設(shè)計空間所組成的錐角范圍內(nèi)。02九月202311302九月2023114如圖所示，圖(a)中設(shè)計點(diǎn)X(k)不是約束極值點(diǎn)，圖(b)的設(shè)計點(diǎn)X(k)是約束極值點(diǎn)。

X(k)▽h(X(k))▽g2(X(k))▽f(X(k))▽g1(X(k))▽g3(X(k))(a)X(k)▽g2(X(k))▽g3(X(k))▽g1(X(k))▽h(X(k))▽f(X(k))(b)02九月2023115123412g1=0g2=0g4=0x1g3=0x2x*▽g2(x*)▽g1(x*)-▽f(x*)(3,2)T02九月2023116用K-T條件求解：02九月202311702九月2023118可能的K-T點(diǎn)出現(xiàn)在下列情況：①兩約束曲線的交點(diǎn)：g1與g2，g1與g3，g1與g4，g2與g3，g2與g4，g3與g4。②目標(biāo)函數(shù)與一條曲線相交的情況：g1，g2，g3，g4

對每一個情況求得滿足K-T條件的點(diǎn)(x1，x2)T及乘子w1，w2，w3，w4，且wi≥0時，即為一個K-T點(diǎn)。02九月2023119下面舉幾個情況：

g1與g2交點(diǎn)：x=(2,1)T∈S，I={1,2}則w3=w4=0

解02九月202312002九月202312102九月202312202九月2023123七最優(yōu)化設(shè)計的數(shù)值計算迭代方法無約束優(yōu)化問題和約束優(yōu)化問題當(dāng)其數(shù)學(xué)模型確定以后求其最優(yōu)解，實(shí)質(zhì)上都屬于目標(biāo)函數(shù)的極值問題。兩者的優(yōu)化求解方法聯(lián)系緊密，其中無約束優(yōu)化方法又是優(yōu)化方法中最基本的方法。02九月2023124迭代算法的概念迭代法是一種重要的逐次逼近的方法。這種方法用某個固定格式反復(fù)計算和校正所求問題的近似解（如方程的根、函數(shù)的極值點(diǎn)等），使之逐次精確化，最后得到滿足精度要求的結(jié)果。求一維方程在附近的一個根。

解：可將方程改寫為下列形式用所給的初始值近似代入上式的右端得到第一個近似解由于和有較大偏差，再將作為初始值，并且重復(fù)上面的計算步驟，如此繼續(xù)下去。這種逐步逼近的過程稱作迭代過程。02九月2023126該例求解該一維方程迭代格式是隨著迭代次數(shù)逐漸增大，直至相鄰兩次迭代點(diǎn)的偏差小于預(yù)先給定的精度值為止。02九月2023127無約束最優(yōu)化算法，每次迭代都按——選定方向S和一合適的步長

向前搜索，可以寫出迭代過程逐次搜索新點(diǎn)的向量方程式02九月2023128迭代過程的每一步向量方程式，都可寫成如下的迭代格式02九月2023129

式中：X(k)－第k步迭代的出發(fā)點(diǎn)；

X(k+1)－第k步迭代產(chǎn)生出的新點(diǎn)；

S(k)－是向量，代表第k步迭代的前進(jìn)方向(或稱搜索方向)；

(k)—是標(biāo)量，代表第k步沿S(k)方向的迭代步長(或稱步長因子)。

在一系列的迭代計算k=1,2,…過程中，產(chǎn)生一系列的迭代點(diǎn)(點(diǎn)列)X(0)，X(1)，…，X(k)，X(k+1)

。為實(shí)現(xiàn)極小化，目標(biāo)函數(shù)的值應(yīng)一次比一次減小，即02九月2023130f(X(0))

f(X(1))

…

f(X(k))

f(X(k＋1))

直至迭代計算滿足一定的精度時，則認(rèn)為目標(biāo)函數(shù)值近似收斂于其理論極小值。

02九月202313102九月2023132優(yōu)化迭代算法的分類

搜索算法是一種迭代算法，搜索方向和步長因子構(gòu)成了每一次迭代的修正量，表明它們是決定算法好壞的重要因素。在搜索方向上，使目標(biāo)函數(shù)取得極小值的步長因子，稱為該方向上最優(yōu)步長因子。在優(yōu)化設(shè)計中，求解最優(yōu)步長因子主要采用數(shù)值解法，即利用計算機(jī)通過反復(fù)的迭代計算，求解出最優(yōu)步長因子的近似值。目前已有很多優(yōu)化方法，各種方法的區(qū)別就在于確定方向和步長因子的方法不同。02九月2023133

1、直接搜索法

這種方法只需要進(jìn)行函數(shù)值的計算與比較來確定優(yōu)化的方向和步長。例如一維搜索中的黃金分割法、二次插值法等，在多維問題中的隨機(jī)方向法、共軛方向法和復(fù)合形法等。02九月20231342、間接搜索法

這種方法需要利用函數(shù)的一階或二階偏導(dǎo)數(shù)矩陣來確定優(yōu)化方向和步長，例如梯度法以負(fù)梯度矢量方向?yàn)樗阉鞣较?，就需要計算函?shù)的一階偏導(dǎo)數(shù)矩陣。牛頓法則同時需要求出目標(biāo)函數(shù)的一階偏導(dǎo)數(shù)矩陣和二階偏導(dǎo)數(shù)矩陣的逆陣才能確定迭代方向和步長。02九月2023135

數(shù)值計算迭代方法：直接從目標(biāo)函數(shù)f(X)出發(fā)，構(gòu)造一種使目標(biāo)函數(shù)值逐次下降逼近，利用計算機(jī)進(jìn)行迭代格式一步步搜索、調(diào)優(yōu)并最后逼近到函數(shù)極值點(diǎn)或達(dá)到最優(yōu)點(diǎn)02九月2023136根據(jù)確定搜索方向和步長的方法不同，數(shù)值計算尋優(yōu)可有許多方法，但其共同點(diǎn)是：1)要具有簡單的邏輯結(jié)構(gòu)并能進(jìn)行同一迭代格式的反復(fù)的運(yùn)算：02九月20231372)這種計算方法所取得的結(jié)果不是理論精確解，而是近似解.

其精度是可以根據(jù)需要加以控制的。02九月2023138

一、迭代法的基本思想及其格式迭代法是適應(yīng)于計算機(jī)工作特點(diǎn)的一種數(shù)值計算方法。其基本思想是：在設(shè)計空間從一個初始設(shè)計點(diǎn)X(0)開始，應(yīng)用某一規(guī)定的算法，沿某一方向S(0)和步長

(0)產(chǎn)生改進(jìn)設(shè)計的新點(diǎn)X(1)

，使得f(X(1))

f(X(0))

，02九月2023139然后再從點(diǎn)X(1)開始，仍應(yīng)用同一算法，沿某一方向S(1)和步長

(1)

，產(chǎn)生又有改進(jìn)的設(shè)計新點(diǎn)X(2)

，使得f(X(2))

f(X(1))

，這樣一步一步地搜索下去。02九月2023140使目標(biāo)函數(shù)值步步下降，直至得到滿足所規(guī)定精度要求的、逼近理論極小點(diǎn)的X*點(diǎn)為止。這種尋找最優(yōu)點(diǎn)的反復(fù)過程稱為數(shù)值迭代過程。下圖為二維無約束最優(yōu)化迭代過程示意圖02九月202314102九月2023142x1x2OX*X(4)X(3)X(2)X(1)X(0)二、迭代計算的終止準(zhǔn)則希望迭代過程進(jìn)行到最終迭代點(diǎn)到達(dá)理論極小點(diǎn)或者使最終迭代點(diǎn)與理論極小點(diǎn)之間的距離足夠小到允許的精度才終止迭代。02九月2023143實(shí)際上對于一個待求的優(yōu)化問題，其理論極小點(diǎn)并不知道。只能從迭代過程獲得的迭代點(diǎn)序列X(0)，X(1)，…

，X(k)，X(k+1)

，…所提供的信息02九月2023144根據(jù)一定的準(zhǔn)則判斷出已取得足夠精確的近似極小點(diǎn)時，迭代即可終止。最后所得的點(diǎn)即認(rèn)為是接近理論極小點(diǎn)的近似極小點(diǎn)。對無約束最優(yōu)化問題常用的迭代過程終止準(zhǔn)則一般有以下幾種。02九月2023145

1)點(diǎn)距準(zhǔn)則

當(dāng)相鄰兩迭代點(diǎn)X(k)，X(k+1)之間的距離已達(dá)到充分小時，即小于或等于規(guī)定的某一很小正數(shù)

時，迭代終止。02九月2023146一般用兩個迭代點(diǎn)向量差的模來表示，即

也可用迭代點(diǎn)在各個坐標(biāo)軸上的分量來表示02九月20231472)函數(shù)下降量準(zhǔn)則

當(dāng)相鄰兩迭代點(diǎn)X(k