3-2-優(yōu)化理論基礎(chǔ)

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

x1,x2,…,xn的值時(shí)目標(biāo)函數(shù)f(X)=f(x1,x2,…,xn)必相應(yīng)有一確定的函數(shù)值16八月20244給定一個(gè)f(X)有無(wú)限多組值x1,x2,…,xn與之對(duì)應(yīng)當(dāng)f(X)=a時(shí)X=[x1,x2,…,xn]T在設(shè)計(jì)空間中對(duì)應(yīng)有一個(gè)點(diǎn)集目標(biāo)函數(shù)的等值面（線）該點(diǎn)集是一個(gè)曲面(二維是曲線，大于三維稱超曲面)16八月20245f(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*16八月20246給定一系列的a值即a=a1,a2,…,an時(shí)一組超曲面族f(X)=a1,a2,…,an

等值面族該組超曲面族16八月20247等值面特性即在一個(gè)特定的等值面上，盡管設(shè)計(jì)方案很多，但每一個(gè)設(shè)計(jì)方案的目標(biāo)函數(shù)值都是相等的。二維無(wú)約束最優(yōu)化設(shè)計(jì)問(wèn)題幾何意義以x1,x2和f(X)為坐標(biāo)f(X)=f(x1,x2)為沿軸方向的高度等值線是等值面在二維設(shè)計(jì)空間中的特定形態(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*16八月2024816八月20249等值線族當(dāng)給定一系列不同的a值時(shí)，可以得到一組平面曲線：f(X)=f(x1,x2)=a1f(X)=f(x1,x2)=a2…這組曲線構(gòu)成目標(biāo)函數(shù)的等值線族16八月202410等值線的分布反映目標(biāo)函數(shù)值的變化等值線越向里，目標(biāo)函數(shù)值越小有中心的曲線族目標(biāo)函數(shù)的無(wú)約束極小點(diǎn)就是等值線族的一個(gè)共同中心X*16八月202411幾何意義---求目標(biāo)函數(shù)無(wú)約束極小點(diǎn)也就是求其等值線族的共同中心。由二維設(shè)計(jì)空間等值線的討論，可推廣到分析多維問(wèn)題。16八月202412注意，對(duì)于三維問(wèn)題在設(shè)計(jì)空間中是等值面高于三維的問(wèn)題在設(shè)計(jì)空間中則是等值超曲面16八月202413例二維約束優(yōu)化問(wèn)題x1x2f(x)f(x)g(x)g1(x)g2(x)O16八月202414二維目標(biāo)函數(shù)等值線族

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

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

對(duì)二維優(yōu)化問(wèn)題進(jìn)行幾何描述。16八月202419約束線、可行域、目標(biāo)函數(shù)等值線、約束極值點(diǎn)213x221-1-2-3-1-2-4-5x1f(X)X*g1(X)g2(X)0幾何意義上來(lái)說(shuō)明約束最優(yōu)解和無(wú)約束最優(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*)。16八月20242016八月202421x1x2x2x1f(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)D16八月202422二維問(wèn)題關(guān)于約束最優(yōu)解和無(wú)約束最優(yōu)解幾何意義的討論．同樣可推廣到高維問(wèn)題n個(gè)設(shè)計(jì)變量x1,x2,…,xn，組成設(shè)計(jì)空間。在這個(gè)空間中的每一個(gè)點(diǎn)代表一個(gè)設(shè)計(jì)方案，此時(shí)n個(gè)變量具有確定的值。3-3局部最優(yōu)解和全域最優(yōu)解

16八月202423目標(biāo)函數(shù)不是單峰函數(shù)有多個(gè)極值點(diǎn)X1*,X2*,…,16八月202424X2*X1*f(X)x2x116八月202425局部最優(yōu)解X1*和f(X1*)、X2*和f(X2*)全域最優(yōu)解目標(biāo)函數(shù)值是全區(qū)域中所有局部最優(yōu)解中的最小者對(duì)應(yīng)的解16八月202426如圖，目標(biāo)函數(shù)f(X)的等值線繪于圖上，有兩個(gè)不等式約束g1(X)0,g2(X)0構(gòu)成兩個(gè)可行域D1和D2。16八月202427局部最優(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)解。16八月202428期望求出全域最優(yōu)解實(shí)際只能求出局部最優(yōu)解措施局部最優(yōu)解之間比較，取最小的一個(gè)3-4無(wú)約束目標(biāo)函數(shù)的極值點(diǎn)存在條件

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

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

在x(1)附近，函數(shù)f(x)的值以f(x(1))為最大；在x(2)附近，函數(shù)值以f(x(2))為最小。16八月202431因此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)的極值。16八月202432需要注意，這里所謂極值是相對(duì)于—點(diǎn)的附近鄰域各點(diǎn)而言的，僅具有局部的性質(zhì)，所以這種極值又稱為局部極值。16八月202433函數(shù)的最大值與最小值是指整個(gè)區(qū)間而言的。如圖中函數(shù)的最大值為f(b)，函數(shù)的最小值為f(a)。函數(shù)的極值并不一定是最大值或最小值。16八月202434二、極值點(diǎn)存在的條件

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

(1)極值點(diǎn)存在的必要條件16八月202435在高等數(shù)學(xué)中已經(jīng)學(xué)過(guò)：如果函數(shù)f(x)的一階導(dǎo)數(shù)f’(x)存在，則欲使x*為極值點(diǎn)的必要條件為：f’(x*)＝016八月202436仍以圖中所示一元函數(shù)為例，由圖可見，在x(1)與x(2)處的f’(x(1))與f’(x(2))均等于零，即函數(shù)在該兩點(diǎn)處的切線與x軸平行。但使f’(x)＝0的點(diǎn)并不一定都是極值點(diǎn)。16八月20243716八月202438f(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)(對(duì)存在導(dǎo)數(shù)的函數(shù))必為駐點(diǎn)駐點(diǎn)不一定是極值點(diǎn)駐點(diǎn)是否為極值點(diǎn)可以通過(guò)二階導(dǎo)數(shù)f’’(x)來(lái)判斷。16八月202439(2)極值點(diǎn)存在的充分條件若在駐點(diǎn)附近f’’(x)0則該點(diǎn)為極大點(diǎn)；若在駐點(diǎn)附近f’’(x)0則該點(diǎn)為極小點(diǎn)。16八月202440在圖中的x(3)附近，其右側(cè)f’’(x)0，但其左側(cè)f’’(x)0，因此它不是極值點(diǎn)?？梢?，函數(shù)二階導(dǎo)數(shù)的符號(hào)成為判斷極值點(diǎn)的充分條件。16八月202441函數(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ù)組成的向量16八月202443梯度的模是函數(shù)各維一階偏導(dǎo)數(shù)平方和的開方梯度與它的模的比值稱為梯度的單位向量16八月202444函數(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è)計(jì)空間的位置不同而異，這只是反映了函數(shù)在點(diǎn)X(K)

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

3、函數(shù)的梯度

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

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

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

16八月202454可簡(jiǎn)寫為16八月202455式中

16八月202456

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階對(duì)稱矩陣，或稱為f(X(k))的赫森(Hessian)矩陣，記作H(X(k))。16八月202457公式中只取到泰勒級(jí)數(shù)二次項(xiàng)，稱為函數(shù)的二次近似表達(dá)式。極值點(diǎn)存在的必要條件。n元函數(shù)在定義域內(nèi)極值點(diǎn)X*存在的必要條件

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

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

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

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

f(X*)=0，于是有16八月202462在X*點(diǎn)附近的鄰域內(nèi)，若對(duì)一切的X恒有亦即16八月202463

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

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

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

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

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

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

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

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

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

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

16八月202473聯(lián)解得到16八月202474計(jì)算點(diǎn)的赫森矩陣

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

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

16八月202479x1x2x1x2OODX(2)X(1)X(2)X(1)D(a)(b)一、凸集與非凸集

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

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

S,

[0,1]，必有

x(1)＋(1-

)x(2)

S，則稱S為凸集。規(guī)定：?jiǎn)吸c(diǎn)集{x}為凸集，空集

為凸集。注:

x(1)＋(1-

)x(2)=x(2)＋

(x(1)-x(2))

是連接x(1)與x(2)的線段。16八月202482凸集非凸集凸集16八月202483二、凸函數(shù)最優(yōu)值最優(yōu)值與極值之間的關(guān)系目標(biāo)函數(shù)的凸性性質(zhì)16八月202484凸函數(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ù)來(lái)說(shuō)明函數(shù)的凸性。如圖所示，圖(a)在x(1)、x(2)區(qū)間曲線為下凸的，圖(b)的曲線是上凸的，它們的極值點(diǎn)(極小點(diǎn)或極大點(diǎn))在區(qū)間內(nèi)都是唯一的。這樣的函數(shù)稱為具有凸性的函數(shù)，或稱為單峰函數(shù)。16八月20248516八月202486凸函數(shù)的定義定義：設(shè)f(X)為定義在n維歐氏空間中一個(gè)凸集D上的函數(shù)，若對(duì)任何實(shí)數(shù)

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

16八月202487Of(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ù)來(lái)說(shuō)明這一概念。若連接函數(shù)曲線上任意兩點(diǎn)的直線段，某一點(diǎn)x(k)的函數(shù)值恒低于此直線段上相應(yīng)的縱坐標(biāo)值時(shí)，這種函數(shù)就是凸函數(shù)，也就是單峰函數(shù)。16八月202488

若將式中的符號(hào)“≤”改為“

”則稱函數(shù)f(X)為嚴(yán)格凸函數(shù)。16八月20248916八月202490凸函數(shù)區(qū)間[a,b]單峰函數(shù)符號(hào)“≤”函數(shù)f(X)為凸函數(shù)符號(hào)“

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

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

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

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

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

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

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

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

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

16八月2024100起作用約束不起作用約束

16八月2024101x1x2x2x1f(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表示16八月2024102或

在優(yōu)化實(shí)用計(jì)算中常需判斷和檢查某個(gè)可行點(diǎn)是否約束極值點(diǎn)，這通常借助于庫(kù)恩-塔克(Kuhn—Tucker)條件(簡(jiǎn)稱K-T條件)來(lái)進(jìn)行。16八月2024103K-T條件可闡述為：如果X(k)是一個(gè)局部極小點(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)線性無(wú)關(guān)16八月202410416八月2024105gi(iI)在X(k)處也可微，可寫成等價(jià)形式iI時(shí)，gi0，wi＝0iI時(shí)，gi=0，對(duì)wi無(wú)限制wig(X(k))=0，i=1，2，…，m稱為互補(bǔ)松弛條件；wi

0，i=1，2，…，m，亦稱拉格朗日乘子。16八月2024106

等式約束性問(wèn)題的最優(yōu)性條件幾何意義是明顯的：考慮一個(gè)約束的情況：最優(yōu)性條件即：16八月2024107-▽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一般約束問(wèn)題的一階最優(yōu)性條件

16八月2024108

如果x*是l.opt.,對(duì)每一個(gè)約束函數(shù)來(lái)說(shuō)，只有當(dāng)它是起作用約束時(shí)，才產(chǎn)生影響，如：16八月2024109g2(x)=0x*g1(x)=0g1(x*)=0,g1為起作用約束K-T條件可闡述為：如果X(k)是一個(gè)局部極小點(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ù)可微16八月202411016八月2024111gi(iI)在X(k)處也可微，可寫成等價(jià)形式16八月2024112wig(X（k）)=0，i=1，2，…，m仍稱為互補(bǔ)松弛條件

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

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

gi(X(k))、

hj(X(k))在設(shè)計(jì)空間所組成的錐角范圍內(nèi)。16八月202411316八月2024114如圖所示，圖(a)中設(shè)計(jì)點(diǎn)X(k)不是約束極值點(diǎn)，圖(b)的設(shè)計(jì)點(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)16八月2024115123412g1=0g2=0g4=0x1g3=0x2x*▽g2(x*)▽g1(x*)-▽f(x*)(3,2)T16八月2024116用K-T條件求解：16八月202411716八月2024118可能的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

對(duì)每一個(gè)情況求得滿足K-T條件的點(diǎn)(x1，x2)T及乘子w1，w2，w3，w4，且wi≥0時(shí)，即為一個(gè)K-T點(diǎn)。16八月2024119下面舉幾個(gè)情況：

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

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

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

向前搜索，可以寫出迭代過(guò)程逐次搜索新點(diǎn)的向量方程式16八月2024128迭代過(guò)程的每一步向量方程式，都可寫成如下的迭代格式16八月2024129

式中：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)方向的迭代步長(zhǎng)(或稱步長(zhǎng)因子)。

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

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

f(X(1))

…

f(X(k))

f(X(k＋1))

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

16八月202413116八月2024132優(yōu)化迭代算法的分類

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

1、直接搜索法

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

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

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

其精度是可以根據(jù)需要加以控制的。16八月2024138

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

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

，使得f(X(1))

f(X(0))

，16八月2024139然后再?gòu)狞c(diǎn)X(1)開始，仍應(yīng)用同一算法，沿某一方向S(1)和步長(zhǎng)

(1)

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

，使得f(X(2))

f(X(1))

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

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

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

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

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

時(shí)，迭代終止。16八月2024146一般用兩個(gè)迭代點(diǎn)向量差的模來(lái)表示，即

也可用迭代點(diǎn)在各個(gè)坐標(biāo)軸上的分量來(lái)表示16八月20241472)函數(shù)下降量準(zhǔn)則

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