32優(yōu)化理論基礎

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

x1,x2,…,xn的值時目標函數(shù)f(X)=f(x1,x2,…,xn)必相應有一確定的函數(shù)值02九月20234給定一個f(X)有無限多組值x1,x2,…,xn與之對應當f(X)=a時X=[x1,x2,…,xn]T在設計空間中對應有一個點集目標函數(shù)的等值面（線）該點集是一個曲面(二維是曲線，大于三維稱超曲面)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ù)值都是相等的。二維無約束最優(yōu)化設計問題幾何意義以x1,x2和f(X)為坐標f(X)=f(x1,x2)為沿軸方向的高度等值線是等值面在二維設計空間中的特定形態(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等值線族當給定一系列不同的a值時，可以得到一組平面曲線：f(X)=f(x1,x2)=a1f(X)=f(x1,x2)=a2…這組曲線構成目標函數(shù)的等值線族02九月202310等值線的分布反映目標函數(shù)值的變化等值線越向里，目標函數(shù)值越小有中心的曲線族目標函數(shù)的無約束極小點就是等值線族的一個共同中心X*02九月202311幾何意義---求目標函數(shù)無約束極小點也就是求其等值線族的共同中心。由二維設計空間等值線的討論，可推廣到分析多維問題。02九月202312注意，對于三維問題在設計空間中是等值面高于三維的問題在設計空間中則是等值超曲面02九月202313例二維約束優(yōu)化問題x1x2f(x)f(x)g(x)g1(x)g2(x)O02九月202314二維目標函數(shù)等值線族

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

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

對二維優(yōu)化問題進行幾何描述。02九月202319約束線、可行域、目標函數(shù)等值線、約束極值點213x221-1-2-3-1-2-4-5x1f(X)X*g1(X)g2(X)0幾何意義上來說明約束最優(yōu)解和無約束最優(yōu)解設已知目標函數(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二維問題關于約束最優(yōu)解和無約束最優(yōu)解幾何意義的討論．同樣可推廣到高維問題n個設計變量x1,x2,…,xn，組成設計空間。在這個空間中的每一個點代表一個設計方案，此時n個變量具有確定的值。3-3局部最優(yōu)解和全域最優(yōu)解

02九月202323目標函數(shù)不是單峰函數(shù)有多個極值點X1*,X2*,…,02九月202324X2*X1*f(X)x2x102九月202325局部最優(yōu)解X1*和f(X1*)、X2*和f(X2*)全域最優(yōu)解目標函數(shù)值是全區(qū)域中所有局部最優(yōu)解中的最小者對應的解02九月202326如圖，目標函數(shù)f(X)的等值線繪于圖上，有兩個不等式約束g1(X)0,g2(X)0構成兩個可行域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)為全域極小點，亦即X3*(3)和f(X3*(3))為全域最優(yōu)解。02九月202328期望求出全域最優(yōu)解實際只能求出局部最優(yōu)解措施局部最優(yōu)解之間比較，取最小的一個3-4無約束目標函數(shù)的極值點存在條件

一、函數(shù)的極值與極值點以一元函數(shù)為例說明函數(shù)的極值與極值點。如圖所示為定義在區(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

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

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

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

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

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

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

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

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

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

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

3、函數(shù)的梯度

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

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

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

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

02九月202356

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

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

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

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

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

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

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

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

則X*為極小點

否則，當恒有則X*為極大點

根據(jù)矩陣理論知，由式得極小點的充分條件為：02九月202364亦即駐點赫森矩陣H(X*)必須為正定

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

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

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

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

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

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

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

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

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

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

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

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

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

S,

[0,1]，必有

x(1)＋(1-

)x(2)

S，則稱S為凸集。規(guī)定：單點集{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)值與極值之間的關系目標函數(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)的曲線是上凸的，它們的極值點(極小點或極大點)在區(qū)間內(nèi)都是唯一的。這樣的函數(shù)稱為具有凸性的函數(shù)，或稱為單峰函數(shù)。02九月20238502九月202386凸函數(shù)的定義定義：設f(X)為定義在n維歐氏空間中一個凸集D上的函數(shù)，若對任何實數(shù)

(01)及D域中任意兩點X(1)與X(2)存在如下關系：則稱函數(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ù)曲線上任意兩點的直線段，某一點x(k)的函數(shù)值恒低于此直線段上相應的縱坐標值時，這種函數(shù)就是凸函數(shù)，也就是單峰函數(shù)。02九月202388

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

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

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

若將式中的符號“≤”改為“≥”，函數(shù)曲線上凸(有極大點)通常稱為凹函數(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)中的兩個最小點，則其連線上的一切點也都是f(X)的最小點。02九月202393四、凸函數(shù)的判定判別法1：若函數(shù)f(X)在D上具有連續(xù)一階導數(shù)，而D為D1內(nèi)部的一個凸集，則f(X)為D上的凸函數(shù)的充分必要條件為：對任意的X(1)與X(2)

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

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

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

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

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起作用約束下標集合用I表示02九月2023102或

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

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

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

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

gi(X(k))(iI)線性無關02九月202310402九月2023105gi(iI)在X(k)處也可微，可寫成等價形式iI時，gi0，wi＝0iI時，gi=0，對wi無限制wig(X(k))=0，i=1，2，…，m稱為互補松弛條件；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ù)來說，只有當它是起作用約束時，才產(chǎn)生影響，如：02九月2023109g2(x)=0x*g1(x)=0g1(x*)=0,g1為起作用約束K-T條件可闡述為：如果X(k)是一個局部極小點，則該點的目標函數(shù)梯度

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

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仍稱為互補松弛條件

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

f(X(k))應落在該點諸約束面梯度

gi(X(k))、

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

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點出現(xiàn)在下列情況：①兩約束曲線的交點：g1與g2，g1與g3，g1與g4，g2與g3，g2與g4，g3與g4。②目標函數(shù)與一條曲線相交的情況：g1，g2，g3，g4

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

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

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

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

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

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

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

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

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

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

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

f(X(1))

…

f(X(k))

f(X(k＋1))

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

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

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

1、直接搜索法

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

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

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

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

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

(0)產(chǎn)生改進設計的新點X(1)

，使得f(X(1))

f(X(0))

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

(1)

，產(chǎn)生又有改進的設計新點X(2)

，使得f(X(2))

f(X(1))

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

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

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

1)點距準則

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

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

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

當相鄰兩迭代點X(k