優化設計:概述:優化建模及數學基礎:一維無約束問題尋優:多維無約束問題尋優:多維約束問題尋優:優化實例

第一節第二節第三節第四節第五節第六節第一節:概述1.1引言

1.4優化設計分類1.2優化設計數學模型

1.3優化設計三大要素

1.5優化設計迭代算法生產甲種產品每件需使用材料9kg、3個工時、4kw電，獲利潤60元。生產乙種產品每件需用材料4kg、10個工時、5kw電，可獲利120元。若每天能供應材料360kg，有300個工時，能供200kw電。試確定兩種產品每天的產量，使每天可能獲得的利潤最大？

分析：每天生產的甲、乙兩種產品分別為x1,x2件§1.1引言（工時約束）（電力約束）（材料約束）(利潤最大)用薄鋼板制造一個體積為5立方米的汽車貨箱，由于運輸的貨物要求，其長度不小于4米。為了使耗費的鋼板最少并減少質量，問應如何選取貨箱的長寬高？設計變量目標函數：約束條件：§1.1引言在某建筑工地中要制作10000套鋼筋，每套由2.9米、2.1米、1.5米長鋼筋組成。它們的直徑和材料相同.目前市場上采購到同類的鋼筋的長度每根均為7.4米.問應購進多少7.4米長的鋼筋才能滿足工程的需要?1首先分析套裁方案,方案如表:§1.1引言2設以表示按第i種方案下料的原材料數量,則可得該問題的數學模型為:§1.1引言給定一個直角三角形，求包含該三角形的最小正方形。

ABCDDAEabx§1.1引言model:sets:object/1..3/:f;endsetsdata:a,b=3,4;!兩個直角邊長，修改很方便;enddataf(1)=a*@sin(x);f(2)=b*@cos(x);f(3)=a*@cos(x)+b*@sin(x);min=@smax(f(1),f(2),f(3));@bnd(0,x,1.57);EndLINGO應用(引例)§1.1引言現在WW(WirelessWidgets)公司擁有6個倉庫，向其8個銷售商供應它的產品。要求每個倉庫供應不能超量，每個銷售商的需求必須得到滿足。WW公司需要決策具體的從每個倉庫運輸多少產品到每個銷售商。以使得所花的運輸費用最少？§1.1引言3、每件產品運輸費用($):銷售商[右]V1V2V3V4V5V6V7V8倉庫[下]Wh162674259Wh249538582Wh352197433Wh476739271Wh523957265Wh655228143二、問題的已知數據：§1.1引言§1.1

引言一.優化(Optimum)定義：在規定的范圍內（或條件下），尋找給定函數取得的最大值（或最小值）的條件。目的：為了在完成某一任務時所作的努力最少、付出最小，而使其收益最大、效果最好。

X0X*

f(X*)f(X)

傳統設計：可行解

優化設計：最優解。§1.1

引言

二.傳統設計與優化設計的區別方案設計詳細設計制造樣機測試評估，性能，質量可否通過？傳統設計不通過投產通過方案設計建模評估詳細設計實驗驗證優化設計改進投產三.優化設計的發展經典優化設計:20世紀40年代起，數學規劃論和計算機技術的發展使最優化設計計算成為可能。優化設計從無約束→有約束優化問題；連續變量→離散變量；確定型→隨機型模型；單目標優化→多目標優化。古典優化思想:17世紀發明微積分中的極值問題。現代優化設計：模擬退火算法、遺傳算法、人工神經網絡算法、蟻群優化算法等。從狹義優化設計（零部件參數）轉向廣義優化設計（面向產品全系統、設計全過程、全壽命周期）。例如,針對涉及多領域復雜系統的多學科設計優化。§1.1

引言§1.2

優化設計的數學模型例：軸的一端作用載荷F=10000N，扭矩T=100N·m；軸長不得小于8cm；材料的許用彎曲應力[σw]=120MPa，許用扭剪應力[τ]=80MPa，許用撓度[f]=0.01cm；密度[ρ]=7.8t/m，彈性模量E=2×105MPa。

分析：設計目標是軸的質量最輕:Q→min.要求：設計銷軸，在滿足上述條件的同時，軸的質量最輕。

限制：彎曲強度：σmax≤[σw]

扭轉強度：τ≤[τ]

剛度：f≤[f]

結構尺寸：l≥8

d≥0lFdT§1.2

優化設計的數學模型目標函數Q=(πd2lρ)/4→min.

約束函數σmax=Fl/(0.1d3)≤[σw]

τ=T/(0.2d3)≤[τ]

f=64Fl3/(3Eπd4)≤[f]

l≥8

d≥0整理得：X=[x1,x2]T=[d,l]T

min.f(x)=0.785x12x2

s.t.g1(x)=8.33x2-

x13≤0

g2(x)=6.25-x13≤0

g3(x)=0.34x23-x14≤0

g4(x)=8-x2≤0

g5(x)=-x1≤0優化設計數學模型統一形式：求設計變量極小化函數滿足約束：§1.2

優化設計的數學模型

一個完整的規格化的優化數學模型包含有三部分:設計變量X；目標函數；約束條件和。它們又被稱為：優化數學模型的三要素。

當涉及問題要求極大化f(X)目標函數時，只要將式中目標函數改寫為－f(X)即可。同樣，當不等式約束為：“≥０”時，只要將不等式兩端同乘以“－1”，即可得到“≤”的一般形式。§1.2

優化設計的數學模型§1.3優化設計的三大要素一.設計變量：

設計變量：在優化設計過程中是變化的，需要優選的量。優化設計問題有n個設計變量，用xi表示

(i=1,2,…,n)。設計向量：用X=[x1,x2,…,xn]T表示，是定義在n維歐氏空間中的一個向量。設計參數：在優化設計過程中保持不變或預先確定數值。§1.3優化設計的三大要素設計點:X(k)（x1(k),x2(k),…,xn(k)）：

例：右圖三維空間中第1設計點：X(1)=[x1(1),x2(1),x3(1)]T第2設計點：X(2)=[x1(2),x2(2),x3(2)]T

代表設計空間中的一個點，也代表第k個設計方案。可能是可行方案、也可能不是可行方案。X(1)

X(2)

ΔX(1)

x1x2x30n=2:X=[x1,

x2]T

是二維設計向量；n=3:X=[x1,

x2,x3]T為三維設計向量，設計變量x1,x2,x3

組成一個三維空間；n>3:設計空間是一個想象的超越空間，稱n維實屬空間。§1.3優化設計的三大要素x1(k)x1X(k)x2(k)x20x1(k)x1X(k)x2(k)x20x3(k)x3在工程設計中，當有些設計變量的取值要求是離散型量，則稱離散設計變量，如齒輪的齒數、模數。

設計變量的個數，稱為維數，它決定了優化問題的大小范圍：

n＝1～10小型優化問題；

n＝11～50中型優化問題；

n>50大型優化問題。設計變量可分為連續變量和離散變量。§1.3優化設計的三大要素§1.3優化設計的三大要素設計約束：設計變量值(設計點)的選擇不僅要使目標函數達到最優值，同時還會受一定的條件限制，這些制約條件稱設計約束。

不等式約束：gu(X)

≤0u=1,2,…,m

等式約束：hv(X)=0v=1,2,…,p(p＜n

)例：有三個不等式約束

g1(X)=-

x1

≤0g2(X)=-x2

≤0g3(X)=x12+x22-1≤0

再加一個等式約束

h(X)=x1-x2=0二.約束函數h(X)=0x1x2g1(X)=0g2(X)=0g3(X)=00不等式約束將設計空間劃分為兩部分：

一部分：滿足約束，即gj(X)＜0；

另一部分：則不滿足約束，即gj(X)＞0。故將該分界線或分界面稱為約束邊界。等式約束本身也是約束邊界，此時只有約束邊界上的點滿足約束，邊界兩邊的所有部分都不滿足約束。

§1.3優化設計的三大要素g(X)=0g(X)>0g(X)<0x1x20h(X)=0h(X)≠0x1x20h(X)≠0§1.3優化設計的三大要素可行設計點：可行域內任意一點稱為可行設計點，代表一個可行方案。極限設計點：在約束面上的點稱為極限設計點。非可行設計點:在可行域外的點稱為非可行設計點，代表不可采用的設計方案。Dx1x2g1(X)=0g2(X)=0g3(X)=00§1.3優化設計的三大要素目標函數：優化設計的過程是從可行設計解中，找出一組最優解的過程。需要一個準則來評價當前設計點（解）的最優性。

f(X)=f(x1,x2,…,xn)多目標函數：由于評價準則的非唯一性，目標函數為多個時稱為多目標函數。

f(X)=[f1(X),f2(X),…,fq(X)]三.目標函數§1.3優化設計的三大要素說明：①f(X)必須是X的函數，應隨設計點的變化f(X)的值上升、下降；②f(X)應該是實函數，是可計算的；③f(X)可以是有物理意義，有單位的，也可以沒有物理意義。例如銷軸的質量：Q=f(X)=(π×d2

×

l×ρ)/4，∵πρ/4是常數，∴f(X)=d2l=x12x2由于每一條曲線上的各點都具有相等的目標函數值，所以這些曲線稱為目標函數的等值線。四.目標函數的等值線(面):就是當目標函數f(X)的值依次等于一系列常數ci

(i=1,2,…)時，設計變量X取得一系列值的集合。§1.3優化設計的三大要素x1x20F(X)=εx1x2等值線的“心”（以二維為例）一個“心”：是單峰函數的極（小）值點，是全局極（小）值點。沒有“心”：例，線性函數的等值線是平行的，無“心”，認為極值點在無窮遠處。多個“心”：不是單峰函數，每個極（小）值點只是局部極（小）值點，必須通過比較各個極值點的值，才能確定極（小）值點。等值線的形狀：同心圓族、橢圓族，近似橢圓族、直線等等值線的疏密：沿等值線密的方向，函數值變化快；沿等值線疏的方向，函數值變化慢。等值線的疏密定性反應函數值變化率。x2優化問題的幾何解釋X*g3(X)=0g2(X)=0g1(X)=0g4(X)=0x10g2(X)=0g3(X)=0g1(X)=00x1x2X*g1(X)=0x1x20x1x20g1(X)=0g2(X)=0x1x20g1(X)=0g2(X)=0g2(X)=0X*X*X*§1.4優化設計的分類一.按模型性質分：

1.確定型優化問題：靜態優化問題（與時間無關）動態優化問題（隨時間變化）

2.不確定型優化問題（隨機優化問題）二.按約束情況分1.按有無約束分：無約束優化問題約束優化問題

2.按約束性質分：區域約束（幾何約束、邊界約束）性能約束（功能約束、性態約束）§1.4

優化設計的分類四.按目標函數和約束函數的特性分：

1.線性規劃問題

2.非線性規劃問題

五.按目標函數的個數分：

1.單目標優化問題2.多目標優化問題六.按設計變量性質分1.連續變量2.離散變量3.隨機變量數學模型求解：數學解析法：把優化對象用數學模型描述出來后，用數學解析法來求出最優解。它是優化設計的理論基礎。但它僅限于維數較少且易求導的優化問題的求解。圖解法數：直接用作圖的方法來求解優化問題，通過畫出目標函數和約束函數的圖形，求出最優解。特點是簡單直觀，但僅限于n≤2的低維優化問題的求解。數值迭代法：完全是依賴于計算機的數值計算特點而產生的，它是具有一定邏輯結構并按一定格式反復迭代計算，逐步逼近優化問題最優解的一種方法。采用數值迭代法可以求解各種優化問題。§1.5優化設計的迭代算法

三個問題：

●怎樣選定搜索方向S(k)；

●如何確定迭代步長α(k)；

●如何判斷是否找到了最優點X*，終止迭代。數值迭代法的迭代格式①在設計空間給出初始迭代點；②從初始迭代點出發，按照確定的搜索方向和迭代步長，求得第一個改進設計點，它應該使目標函數值減小；③再以第一個改進設計點為新的初始點，重復上述步驟，反復迭代，得到一個不斷改進的點列及一相應的遞減函數值數列。x1x20X(0)X(1)X(3)X(2)X*X(4)（１）點距足夠小準則式中，——給定的計算精度，一般可取。（２）函數下降量足夠小準則

（３）函數梯度充分小準則2.迭代計算的終止準則

第二章優化設計的數學基礎2.1多元函數的導數與梯度2.4凸集、凸函數與凸規劃2.2多元函數的泰勒展開2.3無約束優化極值條件2.5等式約束優化極值條件2.6不等式約束優化極值條件§2.1

多元函數的導數與梯度一、方向導數二元函數f(x1，x2)在X

(0)的偏導數為：分別表示沿坐標軸x1和x2方向在X

(0)處的f(X)變化率。f(X)在X0點沿d方向的方向導數:§2.1

多元函數的導數與梯度表示沿d方向在X(0)處的f(X)變化率。Δddθ2Δx2Δx1x1x20x1(0)x2(0)X

(0)θ1n維函數f(X)在X

(0)點沿d方向的方向導數:§2.1

多元函數的導數與梯度x1x2x3x2(0)x1(0)x3(0)0X(0)θ2θ1dθ3二、梯度對于二維函數f(X)在X

(0)點處的梯度:設為d方向的單位向量，則有§2.1

多元函數的導數與梯度投影形式：§2.1

多元函數的導數與梯度方向導數最大值發生在:結論:

d方向取梯度方向時,函數值的變化率最大。可見梯度方向是函數值變化最大的方向§2.1

多元函數的導數與梯度x1x20-▽f(X

(0))▽f(X

(0))最速上升方向最速下降方向下降方向上升方向d:等值線的切線方向，X

(0)函數值變化率為零的方向進一步推導到n維:沿d方向的方向向量即§2.1

多元函數的導數與梯度梯度重要性質：

①梯度是X

(0)點處最大的方向導數；②梯度方向是過點的等值線的法線方向；③梯度是X(0)點處的局部性質；④梯度指向函數變化率最大的方向；⑤正梯度方向是函數值最速上升的方向，負梯度方向是函數值最速下降的方向。§2.1

多元函數的導數與梯度

x1x20X(0)▽f(X(0))-▽f(X(0))最速上升方向最速下降方向下降方向上升方向變化率為零的方向例:求函數f(X)=x12+x22-4x1+4在點[3,2]T的梯度。在點X(0)=[3,2]T處的梯度為：解：§2.1

多元函數的導數與梯度例：試求目標函數f(X)=3x12-4x1x2+x22在點X(0)=[0,1]T處的

最速下降方向，并求沿這個方向移動一個單位長度后

新點的目標函數值。函數在X(0)=[0,1]T處的最速下降方向是解：由于§2.1

多元函數的導數與梯度新點是這個方向上的單位向量是：§2.1

多元函數的導數與梯度§2.2

多元函數的泰勒展開一元函數泰勒展開:二元函數泰勒展開:§2.2

多元函數的泰勒展開二元函數泰勒展開矩陣形式:其中:稱為海賽（Hessian）矩陣§2.2

多元函數的泰勒展開n元函數泰勒展開矩陣形式:§2.3

無約束優化問題的極值條件一元函數極值條件:必要條件極小值極大值偶次階導數不為零為極值點奇次階導數不為零為拐點§2.3

無約束優化問題的極值條件二元函數極值必要條件:即:二元函數極值充分條件:海塞矩陣各階主子式均大于零。§2.3

無約束優化問題的極值條件求函數f(X)=x12+x22-4x1-2x2+5的極值解：1）根據極值的必要條件求駐點2）利用海塞矩陣判斷駐點是否為極值點§2.3

無約束優化問題的極值條件一階主子式：二階主子式：為極值點，f(X

(0))=0為極值§2.3

無約束優化問題的極值條件n元函數極值充分條件:海塞矩陣為正定。函數f(X)在X*附近的一切X均滿足不等式函數f(X)在X*處取得局部極小值，稱X*為局部極小點。而優化問題一般是要求目標函數在某一區域內的全局極小點。§2.4

凸集、凸函數與凸規劃一、凸集一個點集（或區域），如果連接其中任意兩點的線段都全部包含在該集合內，就稱該點集為凸集，否則為非凸集。§2.4

凸集、凸函數與凸規劃x1x20凸集非凸集x1x2yx2x1x1x20y凸集性質:

1)凸集乘一個實數后依然是凸集

2)兩個凸集的和依然是凸集

3)兩個凸集的交集還是凸集§2.4

凸集、凸函數與凸規劃0A2AA+BAB0AB二、凸函數x1、x2為凸集域內的任意兩點，如存在不等式：§2.4

凸集、凸函數與凸規劃稱f(x)是定義在凸集上的一個凸函數。x1x2xab0xf(x)三、凸性條件1.一階導數判斷2.二階導數（

Hessian矩陣)判斷§2.4

凸集、凸函數與凸規劃Hessian矩陣G(X)在R上處處半正定。主子式>0時矩陣正定主子式≥0時矩陣半正定主子式＜0時矩陣負定主子式≤0時矩陣半負定四、凸規劃對于約束優化問題若，都為凸函數，則此問題為凸規劃。§2.4

凸集、凸函數與凸規劃凸規劃的任何局部最優解就是全局最優解等式約束優化形式：求解消元法拉格朗日乘子法§2.5

等式約束優化極值條件1.消元法（降維法）§2.5

等式約束優化極值條件降維處理：1.消元法（降維法）§2.5

等式約束優化極值條件降維處理：方法直觀易理解，但是實際操作很困難變為無約束優化問題：2、拉格朗日乘子法（升維法）改造后優化模型：§2.5

等式約束優化極值條件原優化模型：拉格朗日函數待定系數2、拉格朗日乘子法（升維法）§2.5

等式約束優化極值條件n+l個方程n+l個未知變量例:用拉格朗日乘子法求下列問題的最優解解構造拉格朗日函數令▽L=0,得到求解得：一、一元函數在給定區間上的極值條件§2.6不等式優化極值條件引入松弛變量a1,b1，將不等式約束變成等式約束。根據拉格朗日乘子法，此問題的極值條件：§2.6不等式優化極值條件二、庫恩－塔克條件：§2.6不等式優化極值條件J代表所有起作用的約束在約束的極小值處，函數f(x)的負梯度方向一定能表示成所有起作用約束梯度的非負線性組合庫恩－塔克條件的幾何意義§2.6不等式優化極值條件Xk為最優點Xk不是最優點x1x20可行域Xk▽g1(Xk)▽g2(Xk)點Xk處的切平面-▽f(Xk)f(X)=Cg2(X)=0g1(X)=0x1x20點Xk處的切平面▽g1(Xk)▽g2(Xk)-▽f(Xk)g2(X)=0g1(X)=0f(X)=CxkK-T條件的作用：判別邊界設計點x(k)

為最優點的依據作為約束優化的收斂條件。x1x20▽g1▽g3-▽f-▽f-▽f▽g1▽g2▽g2▽g3f=5f=4f=2.25f=1f=0.25g2(X)=0g3(X)=0g1(X)=0ABC第三章一維搜索方法3.3一維搜索的試探法3.1搜索區間的確定3.2區間消去法原理3.4一維搜索的插值法求解一維目標函數f(X)最優解的過程，稱為一維優化(一維搜索)，所使用的方法稱為一維優化方法。由前數值迭代法可知，求某目標函數的最優值時，迭代過程每一步的格式都是從某一定點X(k)

出發，沿著某一使目標函數下降的規定方向S(k)搜索，以找出此方向的極小點X(k+1)

。這一過程是各種最優化方法的一種基本過程。一維搜索方法一般分兩步進行：

■

首先確定一個包含函數極小點的初始區間，即確定

函數的搜索區間，該區間必須是單峰區間；

■然后采用縮小區間或插值逼近的方法得到最優步長，

最終求出該搜索區間內的一維極小點。§3.1搜索區間的確定根據函數的變化情況，可將區間分為單峰區間和多峰區間。所謂單峰區間，就是在該區間內的函數變化只有一個峰值，即函數的極小值。

即在單峰區間內的極小值點X*的左側：函數呈下降趨勢，而在單峰區間內的極小值點X*

的右側：函數呈上升趨勢。也就是說，單峰區間的函數值呈“高-低-高”的變化特征。§3.1搜索區間的確定x*abx0f(x)

目前在一維優化搜索中確定單峰區間常用的方法是進退試算法。

進退試算法的基本思想為：

1)按照一定的規律給出若干試算點，

2)依次比較各試算點的函數值的大小，

3)直到找到相鄰三點函數值按“高-低-高”

變化的單峰區間為止§3.1搜索區間的確定

進退試算法的運算步驟如下：(2)將α0及α0+h代入目標函數f(x)進行計算并比較大小(1)給定初始點α0和初始步長h§3.1搜索區間的確定f(x)x0aba0f(a0)a0+hf(a0+h)a0+3hf(a0+3h)f(x)x0aba0-hf(a0-h)a0f(a0)a0+hf(a0+h)若f(α0+h)≤f(α0+3h)，則所計算的相鄰三點

的函數值已具“高-低-高”特征，這時可確定搜索區間

(3)若f(α0)>f(α0+h)，則表明極小點在試算點

的右側，需做前進試算。

否則，將步長再加倍，并重復上述運算。§3.1搜索區間的確定在做前進運算時，為加速計算，可將步長h

增加2倍，并取計算新點為α0+h+2h=α0+3h

(4)若f(α0)<f(α0+h)，則表明極小點在試算點

的左側，需做后退試算。在做后退運算時，應將步長變為-h

，并從

點出α0發，得到后退點為α0-h

若f(α0-h)>f(α0)，則搜索區間可取為否則，將步長加倍，繼續后退，重復上述步驟，直到滿足單峰區間條件為止。§3.1搜索區間的確定f(b1)f(a1)f(b1)f(a1)f(b1)af(a1)搜索區間確定之后，采用區間消去法逐步縮短搜索區間，找到極小點的數值近似解。假定在搜索區間內[a,b]任取兩點a1、b1,且a1<b1f1＝f（a1），

f2＝f（b1）一、基本思想a1a1

a1

b1baabb

b1b1§3.2區間消去法原理f1>f2

f1<f2

f1=f2

f(x)

f(x)

f(x)

(1)f1<f2,新區間為[a,b1](2)f1>f2,新區間為[a1,b](3)f1=f2,新區間為[a1,b1]對于上述縮短后的新區間，可在其內再取一個新點，然后將此點和該區間內剩下的那一點進行函數值大小的比較，以再次按照上述方法，進一步縮短區間，這樣不斷進行下去，直到所保留的區間縮小到給定的誤差范圍內，而得到近似最優解。新區間為[a1,b]f(b1)af(a1)

a1

b1bf(b1)f(a1)a1ab

b1f(b1)f(a1)a1bab1一、適用范圍

適用于[a,b]區間上的任何單谷函數求極小值問題。對函數除要求“單峰”外不作其他要求，甚至可以不連續。適應面相當廣。基本原理為區間消去法§3.3黃金分割法黃金分割法插入兩點：f(a2)af(a1)

a1

a2bf(a2)af(a1)

a1b

a2黃金分割法還要求在保留下來的區間內再插入一點所形成的區間新三段，與原來區間的三段具有相同的比例分布。§3.3黃金分割法λα2α1λ2ab11-λα1α3λ(1-λ)α2λa黃金分割法程序框圖開始輸入a,

b,

,

YN結束YNaf(x2)f(x1)b

x1

x2b

x2f(x2)

x1例3-1用黃金分割法求函數f(x)=3x3-4x+2的極小點，

初始點x0=0,步長h=1,精度

ε=0.2。解：1）確定初始區間

x1=x0=0,f1=f(x1)=2

x2=x0+h=0+1=1

f2=f(x2)=1

由于f1>f2,應繼續向前探測

x3=

x0+2h=0+2=2

f3=f(x3)=18由于f2<f3,可知初始區間已經找到，即

[a,b]=[x1,x3]=[0,2]§3.3黃金分割法f(x1)=2x1=0f(x2)=1x2=1f(x3)=18x3=2ab2）用黃金分割法縮小區間

第一次縮小區間：

x1=0+0.382×(2-0)=0.764,f1=0.282x2=0+0.618×(2-0)=1.236,f2=2.72

由于f1<f2,故新區間[a,b]=[a,x2]=[0,1.236]由于b-a＝1.236>0.2,應繼續縮小區間§3.3黃金分割法f(x1)=0.282x1=0.764f(x2)=2.72x2=1.236abb§3.3黃金分割法第二次縮小區間：令x2=x1=0.764,

f2=f1=0.282

x1=0+0.382×(1.236-0)=0.472,f1=0.317由于f1>f2,故新區間[a,b]=[x1,b]=[0.472,1.236]由于b-a=1.236-0.472=0.764>0.2,應繼續縮小區間f(x1)=0.282x1=0.764f(x2)=2.72x2=1.236abbx2f(x2)x1f(x1)a

第三次縮小區間：令x1=x2=0.764,

f1=f2=0.282

x2=0.472+0.618×(1.236-0.472)=0.944,f2=0.747由于f1<f2,故新區間[a,b]=[a,x2]=[0.472,0.944]由于b-a=0.944-0.472=0.472>0.2,應繼續縮小區間。§3.3黃金分割法

第四次縮小區間：令x2=x1=0.764,

f2=f1=0.282

x1=0.472+0.382×(0.944-0.472)=0.652,f1=0.223由于f1<f2,故新區間[a,b]=[a,x2]=[0.472,0.764]由于b-a=0.764-0.472=0.292>0.2,應繼續縮小區間。第五次縮小區間：令x2=x1=0.652,

f2=f1=0.223

x1=0.472+0.382×(0.764-0.472)=0.584,f1=0.262由于f1>f2,故新區間[a,b]=[x1,b]=[0.584,0.764]因為b-a=0.764-0.584=0.18<0.2,停止迭代。黃金分割法求的的極小點與極小值：

x=0.5×(0.584+0.764)=0.674,f(x)=0.222§3.3黃金分割法求導運算求的極小點與極小值：

x=0.667,f(x)=0.222一、牛頓法§3.4插值方法利用一點的函數值、一階導數以及二階導數構造二次多項式。用構造的二次多項式的極小點作為原函數極小點的近似。x*xf(x)

x2φ0(x)

x0f(x)

φ1(x)

x1一、牛頓法設f(x)為一個連續可微的函數，則在點x0附近進行泰勒展開并保留到二次項：用二次函數φ(x)的極小點x1作為f(x)極小點的一個近似點。根據極值必要條件:§3.4插值方法xf(x)

x1x2φ0(x)

x*f(x)

φ1(x)

x0即依此類推可得牛頓迭代公式：一、牛頓法§3.4插值方法x2x1x0x*f(x)

f(x)

φ0(x)

φ1(x)

在x0處用一拋物線φ(x)代替曲線f(x)，相當于用一斜直線φ

′(x)代替曲線f

′(x)。這樣各個近似點是通過對作f

′(x)切線求得與軸的交點找到的，所以有時牛頓法又稱作切線法。x2x1x0x*f(x)

f(x)

φ0(x)

φ1(x)

f′

(x)

f′

(x)

x*x0φ′1(x)

x2x1牛頓法程序框圖

開始計算，YN給定初始點，誤差,令k=0計算，結束數值\k

0

1

2

3

435.1667

4.33474

4.03960

4.00066-52

153.35183

32.30199

3.38299

0.0055124

184.33332

109.44586

86.86992

84.04720

5.1667

4.33474

4.03960

4.00066

4.00059

2.1667

0.83196

0.29514

0.03894

0.00007例3-2給定f(x)=x4-4x3-6x2-16x+4，試用牛頓法計算其極小點。給定初始點x0=3，ε=0.001，計算公式：函數的二階導數：解：函數的一階導數：§3.4插值方法

優點：1）收斂速度快。

缺點：1）要計算函數的一階和二階導數，增加每次迭代的工作量。

2）數值微分計算函數二階導數，舍入誤差將嚴重影響牛頓法的收斂速度，f

'(x)的值越小問題越嚴重。

3）牛頓法要求初始點離極小點不太遠，否則可能使極小化序列發散或收斂到非極小點。一、牛頓法§3.4插值方法二、二次插值法（拋物線法）

在給定的單峰區間中，利用目標函數上的三個點來構造一個二次插值函數，以近似地表達原目標函數f(a)，并求這個插值函數的極小點近似作為原目標函數的極小點。

§3.4插值方法f(x)xf1x1f2x2f3x3xpx*y0xxp1x1x2xpx3xy0x*y1y2ypy3x1x2xpx*y1y2ypyp1xpxp1x1x2xpx3xy0x*y1y2ypy3x2x3xy0x*y2ypy3yp1構造的二次插值函數曲線通過原函數上的三個點:

解得系數可求得二、二次插值法（拋物線法）§3.4插值方法二次插值法程序框圖開始計算，YN給定,縮短區間名稱置換結束x1x2xpx3xy0x*y1y2ypy3x1x2xpx3x0x*yy1y2ypy3二次插值法程序編制換名方法(1)1)

x2<xp

y2≥yp

y2<ypy2→y1yp→y2xpx1x2x3xy2yp→y3xpx1x2x3xx1x2x3二次插值法程序編制換名方法(2)2)

x2>xp

y2≥ypyp→y2y2→y3xpx1x2x3xx3x2

y2<ypyp→y1y2xpx1x2x3xx1（1）二次插值法只要求f(x)連續，不要求其一階可微；（2）收斂速度比黃金分割法快，但可靠性不如黃金分割

法好，程序也較長。特點：§3.4插值方法二、二次插值法（拋物線法）例3-3用二次插值法求函數f(X)=3x3-4x+2的極小點，

給定x0=0,ε=0.2。解1）確定初始區間:[a,b]=[0,2]2）用二次插值法逼近極小點相鄰三點的函數值:x1=0,x2=1,x3=2;f1=2,

f2=1,f3=18.代入公式：xp＝0.555,fp=0.292在新區間，相鄰三點的函數值:x1=0,x2=0.555,x3=1;f1=2,f2=0.292,f3=1.

xp=0.607,fp=0.243

由于fp<f2,xp>x2,新區間[a,b]=[x2,b]=[0.555,1]|x2-xp|=|0.555-0.607|=0.052<0.2,迭代終止。

x*=0.607,f*=0.243由于fp<f2,xp<x2,新區間[a,b]=[a,x2]=[0,1]|x2-xp|=|1-0.555|=0.445>0.2,應繼續迭代。yp→y2y2→y3xpx3x2x1x2x3xx2x3xp第四章無約束優化方法4.1最速下降法4.2牛頓型方法4.3共軛梯度法4.6鮑威爾方法4.4變尺度法4.5坐標輪換法4.7單形替換法無約束優化問題表達形式：求設計變量使目標函數數值迭代算法公式:從選定的某初始點X0出發，沿著以一定規律產生的搜索方向d

k,取適當的迭代步長ak,逐次搜尋函數值下降的新迭代點Xk+1,使之逐步逼近最優點X*。概述無約束優化方法分類間接法:利用目標函數的一階或二階導數直接法:利用目標函數值最速下降法、牛頓法、共軛梯度法、變尺度法坐標輪換法、鮑威爾方法、單形替換法等

把初始點X0

、搜索方向d

k、迭代步長ak

稱為優化方法算法的三要素。其中搜索方向d

k從根本上決定若一個算法的成敗、收斂速率的快慢等。無約束優化方法主要不同點在于構造搜索方向上的差別。概述滿足收斂條件？無約束優化算法程序示意圖開始給定X0、d0N形成新的d計算最佳步長，使極小結束Y搜索方向d取該點負梯度方向-▽f(X)

(最速下降方向)，使函數值在該點附近的范圍內下降最快。§4.1最速下降法x1x20為了使目標函數值沿搜索方向-▽f(Xk)

能夠獲得最大的下降值，其步長因子ak應取一維搜索的最佳步長:§4.1最速下降法可以得最佳步長設：根據一元函數極值的必要條件復合函數求導公式得§4.1最速下降法由此可知，在最速下降法中，相鄰兩個迭代點上的函數梯度相互垂直(正交)。而搜索方向就是負梯度方向，因此相鄰兩個搜索方向互相垂直。相鄰兩個搜索方向的關系迭代點向函數極小點靠近的過程，走的是曲折的路線。形成“之”字形的鋸齒現象。在遠離極小點的位置，每次迭代可使函數值有較多的下降。在接近極小點的位置，由于鋸齒現象使每次迭代行進的距離縮短，收斂速度減慢。

最速下降法的搜索路徑§4.1最速下降法x1x20最速下降法程序框圖開始計算，YN給定初始點，誤差,令k=0計算，計算，結束§4.1最速下降法例4－1用最速下降法求下列目標函數的極小點。初始點為X(0)=[2,2]T解初始點梯度為：沿負梯度方向進行一維搜索:為一維搜索最佳步長，應滿足極值必要條件

§4.1最速下降法算出一維搜索最佳步長

§4.1最速下降法第一次迭代設計點位置和函數值

繼續作下去，經10次迭代后，得到最優解

最速下降法評價：迭代過程簡單，對初始點選擇要求不高。梯度方向目標函數值下降迅速只是個局部性質，從整體來看，不一定是收斂最快的方向。梯度法相鄰兩次搜索方向的正交性，決定了迭代全過程的搜索路線呈鋸齒狀，在遠離極小點時逼近速度較快，而在接近極小點時逼近速度較慢。§4.1最速下降法X(k)S(k)S(k+1)X(k+1)X(k+2)X(k+3)X*f(X)=Ckf(X)=Ck+1f(X)=Ck+31、牛頓法

在Xk鄰域內用一個二次函數φ(X)來近似代替原目標函數，并將φ(X)的極小點作為對目標函數f(X)

求優的下一個迭代點。經多次迭代，使之逼近目標函數f(X)的極小點。§4.2牛頓型方法設為的極小值點：牛頓法迭代公式:

§4.2牛頓型方法例4－2用牛頓法求下列目標函數的極小點。初始點為X0=[2,2]T解初始點梯度：海賽矩陣:帶入到牛頓迭代公式：海賽矩陣逆陣：§4.2牛頓型方法牛頓法缺陷：

從牛頓法迭代公式的推演中可以看到，迭代點的位置是按照極值條件確定的，其中并未含有沿下降方向搜尋的概念。因此對于非二次函數，如果采用上述牛頓迭代公式，有時會使函數值上升。§4.2牛頓型方法2、阻尼牛頓法

:阻尼因子，沿牛頓方向進行一維搜索的最佳步長，由下式求得：

§4.2牛頓型方法開始N給定初始點，誤差,令k=0計算，計算，計算，阻尼牛頓法程序框圖§4.2牛頓型方法結束Y牛頓型方法評價：（1）若迭代點的海賽矩陣為奇異，則很難甚至無

法求逆矩陣，進而不能構造牛頓法方向；

（2）

不僅要計算梯度，還要求海賽矩陣及其逆矩陣，計算量和存儲量大。

§4.2牛頓型方法為了克服最速下降法的鋸齒現象，提高收斂速度;同時克服牛頓型方法需要計算二階導數及其逆陣，計算量大的現象，發展了一類共軛方向法。該方法的搜索方向是共軛方向。一、共軛方向的概念§4.3共軛梯度法式中：c為常數，X,b為2維列向量，G為n階對稱正定矩陣。二元二次函數為避免鋸齒的發生，取下一次的迭代搜索方向直接指向極小點，如果選定這樣的搜索方向，對于二元二次函數只需進行兩次直線搜索就可以求到極小點。§4.3共軛梯度法和應具有什么樣的關系？X0a0d0X1-▽f(X1)a1d1對于二次函數在X*處取得極小點的必要條件:等式兩邊同乘得:滿足上式的兩個向量,是G的共軛方向。X0a0d0X1-▽f(X1)a1d1二.共軛方向的性質1）非零向量系d0,d1,d2,…,dn-1是對G共軛，

則這n個向量線性無關。2）在n維空間中互相共軛的非零向量個數不超過n。

3）從任意初始點出發，順次沿n個G的共軛方向d0,d1,d2,…,進行一維搜索，最多經過

n次迭代就可以找到二次函數f(X)極小點。§4.3共軛梯度法二.共軛方向的性質§4.3共軛梯度法X0a0d0X1a1d1共軛梯度法是共軛方向法的一種，共軛向量由迭代點的負梯度構造出來，所以稱共軛梯度法。從點Xk出發，沿G某一方向dk作一維搜索,到達Xk+1而在點Xk、Xk+1處的梯度分別為：§4.3共軛梯度方法三.共軛梯度法得出共軛方向與梯度之間的關系。此式表明沿方向dk進行一維搜索，其終點Xk+1與始點Xk的梯度值差▽f(Xk+1)-▽f(Xk)與dk的共軛方向dk+1正交。

§4.3共軛梯度方法如果方向dk+1與方向dk對G共軛:共軛梯度法的幾何說明§4.3共軛梯度方法Xkdk▽f(Xk)dk+1X*Xk+1▽f(Xk+1)▽f(Xk+1)-▽f(Xk)共軛梯度法遞推公式(推導過程自學)：其中:§4.3共軛梯度方法開始初始點,誤差,計算，計算，共軛梯度法程序框圖結束YYK=n－1?NN共軛梯度法評價：1)搜索方向是對負梯度方向的修正，因此具有最速下降法的優點（收斂速度比最速下降法快）；2)共軛梯度法需求一階導數，所用公式及算法簡單，所需存儲量少（適用于大規模問題）。§4.3共軛梯度方法迭代公式：x1x20Xk例，已知初始點[1,1]T解：1）第一次沿負梯度方向搜尋為一維搜索最佳步長，應滿足迭代精度。§4.3共軛梯度方法得:2）第二次迭代：代入目標函數得因,收斂。由從而有：仍從，即出發進行最速下降法尋優。此時：目標函數引入變換:

y1=x1,y2=5x2則函數f(X)變為：§4.4變尺度法利用最速下降法經10次迭代后，得到最優解

例題：搜索最佳步長可由極值條件：由沿負梯度方向進行一維搜索：§4.4變尺度法經變換后，只需一次迭代，就可找到最優解。這是因為經過尺度變換：等值線由橢圓變成圓。從而算得一步計算后設計點的位置及其目標函數：x0x1x2x1x20y2y1Y0基本思想最速下降法法構造簡單，只用到一階偏導數，計算量小，迭代初期收斂速度快，但當迭代到最優點附近時收斂速度很慢；牛頓法收斂很快，對于二次函數只需迭代一次便達到最優點，對非二次函數也能較快迭代到最優點，但要計算二階偏導數矩陣及其逆陣，對維數較高的優化問題，其計算工作和存儲量都太大。

變量的尺度變換是放大或縮小各個坐標。通過尺度變換可以把函數的偏心程度降到最低限度。

§4.4變尺度法進行尺度變換在新的坐標系中，函數f(X)的二次項變為：目的：減少二次項的偏心如G是正定，則總存在矩陣Q，使得：對于二次函數:§4.4變尺度法

用矩陣Q-1右乘等式兩邊，得：用矩陣Q左乘等式兩邊，得：所以§4.4變尺度法上式說明：二次函數矩陣G的逆陣，可以通過尺度變換矩陣來求得。Ak

是需要構造n×n的一個對稱方陣，稱為尺度矩陣如Ak=I,則得到最速下降法；

，則得到阻尼牛頓法；如當矩陣Ak

不斷地迭代而能很好地逼近時，就可以不再需要計算二階導數。變尺度法的關鍵在于尺度矩陣Ak的產生。§4.4變尺度法1）對變尺度矩陣的要求：2.構造尺度矩陣Ak①要求｛Ak｝中的每一個矩陣都是對稱正定矩陣

∵要求dk=-Ak

▽f(Xk)為下降方向∴要求▽f(Xk)

Tdk<0∴－▽f(Xk)

TAk

▽f(Xk)<0∴▽f(Xk)TAk

▽f(Xk)＞0

既要求Ak為對稱正定x1x20-▽f(Xk)▽f(Xk)最速上升方向最速下降方向下降方向上升方向Xk1）對變尺度矩陣的要求：2.構造尺度矩陣Ak②要求｛Ak｝之間的迭代具有簡單的形式

Ak＋1

＝Ak

＋△Ak

△Ak為校正矩陣③要求｛Ak｝必須滿足擬牛頓條件擬牛頓條件中修正矩陣的不斷修正，在迭代中逐步逼近于DFP法:式中2）具體構造方法：從初始矩陣A0=I(單位矩陣)開始，通過對公式2.構造尺度矩陣Ak開始初始點,誤差,計算，計算，變尺度法程序框圖結束YYK=n－1NN變尺度法評價：1)收斂速度快，且只需求一階導數，不需要求出海賽矩陣（適用于大規模問題，20個變量以上）；2)由于舍入誤差和一維搜索的不精確，可能導致尺度矩陣奇異，進而在穩定性方面不夠理想。可進一步改進（BFGS算法）。解：1）取初始點，為了按DFP法構造第一次搜尋方向d0，需計算初始點處的梯度取初始變尺度矩陣為單位矩陣A0=I，則第一次搜尋方向為例:用DFP算法求下列問題的極值：一維搜索最佳步長應滿足得:2）再按DFP法構造點X(1)處的搜尋方向d1，需計算沿d0方向進行一維搜索，得代入校正公式==第二次搜尋方向為再沿d1進行一維搜索，得a1為一維搜索最佳步長，應滿足,得3）判斷X(2)是否為極值點梯度:海賽矩陣:梯度為零向量,海賽矩陣正定。可見滿足極值充要條件，因此為極小點。§4.5坐標輪換法一.坐標輪換法：1.基本思想：每次搜索只允許一個變量變化，其余變量保持不變，即沿坐標方向輪流進行搜索的尋優方法。它把多變量的優化問題輪流地轉化成單變量（其余變量視為常量）的優化問題，因此又稱這種方法為變量輪換法。此種方法只需目標函數的數值信息而不需要目標函數的導數。x1x20X11X12X21X*X00X22計算步驟:⑴任選初始點,確定搜索方向第一輪的起點，置n個坐標軸方向矢量為單位坐標矢量§4.5坐標輪換法⑵迭代計算k為迭代輪數的序號，取k=1，2，……；i為該輪中一維搜索的序號，取i=1，2，……n步長α一般通過一維優化方法求出其最優步長。⑶判斷是否中止迭代如滿足，迭代中止，并輸出最優解最優解否則，令k←k+1返回步驟（2）§4.5坐標輪換法

應該是一輪迭代的始點和終點，不是某搜索方向的前后迭代點。NN開始初始點,誤差,坐標輪換法的流程圖Y結束Y沿著ei方向一維搜索ai計算，例:用坐標輪換