現(xiàn)代設(shè)計(jì)方法學(xué) 優(yōu)化設(shè)計(jì)

優(yōu)化設(shè)計(jì):概述:優(yōu)化建模及數(shù)學(xué)基礎(chǔ):一維無約束問題尋優(yōu):多維無約束問題尋優(yōu):多維約束問題尋優(yōu):優(yōu)化實(shí)例

第一節(jié)第二節(jié)第三節(jié)第四節(jié)第五節(jié)第六節(jié)第一節(jié):概述1.1引言

1.4優(yōu)化設(shè)計(jì)分類1.2優(yōu)化設(shè)計(jì)數(shù)學(xué)模型

1.3優(yōu)化設(shè)計(jì)三大要素

1.5優(yōu)化設(shè)計(jì)迭代算法生產(chǎn)甲種產(chǎn)品每件需使用材料9kg、3個(gè)工時(shí)、4kw電，獲利潤(rùn)60元。生產(chǎn)乙種產(chǎn)品每件需用材料4kg、10個(gè)工時(shí)、5kw電，可獲利120元。若每天能供應(yīng)材料360kg，有300個(gè)工時(shí)，能供200kw電。試確定兩種產(chǎn)品每天的產(chǎn)量，使每天可能獲得的利潤(rùn)最大？

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

ABCDDAEabx§1.1引言model:sets:object/1..3/:f;endsetsdata:a,b=3,4;!兩個(gè)直角邊長(zhǎng)，修改很方便;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應(yīng)用(引例)§1.1引言現(xiàn)在WW(WirelessWidgets)公司擁有6個(gè)倉庫，向其8個(gè)銷售商供應(yīng)它的產(chǎn)品。要求每個(gè)倉庫供應(yīng)不能超量，每個(gè)銷售商的需求必須得到滿足。WW公司需要決策具體的從每個(gè)倉庫運(yùn)輸多少產(chǎn)品到每個(gè)銷售商。以使得所花的運(yùn)輸費(fèi)用最少？§1.1引言3、每件產(chǎn)品運(yùn)輸費(fèi)用($):銷售商[右]V1V2V3V4V5V6V7V8倉庫[下]Wh162674259Wh249538582Wh352197433Wh476739271Wh523957265Wh655228143二、問題的已知數(shù)據(jù)：§1.1引言§1.1

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

X0X*

f(X*)f(X)

傳統(tǒng)設(shè)計(jì)：可行解

優(yōu)化設(shè)計(jì)：最優(yōu)解?！?.1

引言

二.傳統(tǒng)設(shè)計(jì)與優(yōu)化設(shè)計(jì)的區(qū)別方案設(shè)計(jì)詳細(xì)設(shè)計(jì)制造樣機(jī)測(cè)試評(píng)估，性能，質(zhì)量可否通過？傳統(tǒng)設(shè)計(jì)不通過投產(chǎn)通過方案設(shè)計(jì)建模評(píng)估詳細(xì)設(shè)計(jì)實(shí)驗(yàn)驗(yàn)證優(yōu)化設(shè)計(jì)改進(jìn)投產(chǎn)三.優(yōu)化設(shè)計(jì)的發(fā)展經(jīng)典優(yōu)化設(shè)計(jì):20世紀(jì)40年代起，數(shù)學(xué)規(guī)劃論和計(jì)算機(jī)技術(shù)的發(fā)展使最優(yōu)化設(shè)計(jì)計(jì)算成為可能。優(yōu)化設(shè)計(jì)從無約束→有約束優(yōu)化問題；連續(xù)變量→離散變量；確定型→隨機(jī)型模型；單目標(biāo)優(yōu)化→多目標(biāo)優(yōu)化。古典優(yōu)化思想:17世紀(jì)發(fā)明微積分中的極值問題。現(xiàn)代優(yōu)化設(shè)計(jì)：模擬退火算法、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)算法、蟻群優(yōu)化算法等。從狹義優(yōu)化設(shè)計(jì)（零部件參數(shù)）轉(zhuǎn)向廣義優(yōu)化設(shè)計(jì)（面向產(chǎn)品全系統(tǒng)、設(shè)計(jì)全過程、全壽命周期）。例如,針對(duì)涉及多領(lǐng)域復(fù)雜系統(tǒng)的多學(xué)科設(shè)計(jì)優(yōu)化?！?.1

引言§1.2

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

分析：設(shè)計(jì)目標(biāo)是軸的質(zhì)量最輕:Q→min.要求：設(shè)計(jì)銷軸，在滿足上述條件的同時(shí)，軸的質(zhì)量最輕。

限制：彎曲強(qiáng)度：σmax≤[σw]

扭轉(zhuǎn)強(qiáng)度：τ≤[τ]

剛度：f≤[f]

結(jié)構(gòu)尺寸：l≥8

d≥0lFdT§1.2

優(yōu)化設(shè)計(jì)的數(shù)學(xué)模型目標(biāo)函數(shù)Q=(πd2lρ)/4→min.

約束函數(shù)σ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優(yōu)化設(shè)計(jì)數(shù)學(xué)模型統(tǒng)一形式：求設(shè)計(jì)變量極小化函數(shù)滿足約束：§1.2

優(yōu)化設(shè)計(jì)的數(shù)學(xué)模型

一個(gè)完整的規(guī)格化的優(yōu)化數(shù)學(xué)模型包含有三部分:設(shè)計(jì)變量X；目標(biāo)函數(shù)；約束條件和。它們又被稱為：優(yōu)化數(shù)學(xué)模型的三要素。

當(dāng)涉及問題要求極大化f(X)目標(biāo)函數(shù)時(shí)，只要將式中目標(biāo)函數(shù)改寫為－f(X)即可。同樣，當(dāng)不等式約束為：“≥０”時(shí)，只要將不等式兩端同乘以“－1”，即可得到“≤”的一般形式?！?.2

優(yōu)化設(shè)計(jì)的數(shù)學(xué)模型§1.3優(yōu)化設(shè)計(jì)的三大要素一.設(shè)計(jì)變量：

設(shè)計(jì)變量：在優(yōu)化設(shè)計(jì)過程中是變化的，需要優(yōu)選的量。優(yōu)化設(shè)計(jì)問題有n個(gè)設(shè)計(jì)變量，用xi表示

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

例：右圖三維空間中第1設(shè)計(jì)點(diǎn)：X(1)=[x1(1),x2(1),x3(1)]T第2設(shè)計(jì)點(diǎn)：X(2)=[x1(2),x2(2),x3(2)]T

代表設(shè)計(jì)空間中的一個(gè)點(diǎn)，也代表第k個(gè)設(shè)計(jì)方案?？赡苁强尚蟹桨?、也可能不是可行方案。X(1)

X(2)

ΔX(1)

x1x2x30n=2:X=[x1,

x2]T

是二維設(shè)計(jì)向量；n=3:X=[x1,

x2,x3]T為三維設(shè)計(jì)向量，設(shè)計(jì)變量x1,x2,x3

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

設(shè)計(jì)變量的個(gè)數(shù)，稱為維數(shù)，它決定了優(yōu)化問題的大小范圍：

n＝1～10小型優(yōu)化問題；

n＝11～50中型優(yōu)化問題；

n>50大型優(yōu)化問題。設(shè)計(jì)變量可分為連續(xù)變量和離散變量。§1.3優(yōu)化設(shè)計(jì)的三大要素§1.3優(yōu)化設(shè)計(jì)的三大要素設(shè)計(jì)約束：設(shè)計(jì)變量值(設(shè)計(jì)點(diǎn))的選擇不僅要使目標(biāo)函數(shù)達(dá)到最優(yōu)值，同時(shí)還會(huì)受一定的條件限制，這些制約條件稱設(shè)計(jì)約束。

不等式約束：gu(X)

≤0u=1,2,…,m

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

)例：有三個(gè)不等式約束

g1(X)=-

x1

≤0g2(X)=-x2

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

再加一個(gè)等式約束

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

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

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

§1.3優(yōu)化設(shè)計(jì)的三大要素g(X)=0g(X)>0g(X)<0x1x20h(X)=0h(X)≠0x1x20h(X)≠0§1.3優(yōu)化設(shè)計(jì)的三大要素可行設(shè)計(jì)點(diǎn)：可行域內(nèi)任意一點(diǎn)稱為可行設(shè)計(jì)點(diǎn)，代表一個(gè)可行方案。極限設(shè)計(jì)點(diǎn)：在約束面上的點(diǎn)稱為極限設(shè)計(jì)點(diǎn)。非可行設(shè)計(jì)點(diǎn):在可行域外的點(diǎn)稱為非可行設(shè)計(jì)點(diǎn)，代表不可采用的設(shè)計(jì)方案。Dx1x2g1(X)=0g2(X)=0g3(X)=00§1.3優(yōu)化設(shè)計(jì)的三大要素目標(biāo)函數(shù)：優(yōu)化設(shè)計(jì)的過程是從可行設(shè)計(jì)解中，找出一組最優(yōu)解的過程。需要一個(gè)準(zhǔn)則來評(píng)價(jià)當(dāng)前設(shè)計(jì)點(diǎn)（解）的最優(yōu)性。

f(X)=f(x1,x2,…,xn)多目標(biāo)函數(shù)：由于評(píng)價(jià)準(zhǔn)則的非唯一性，目標(biāo)函數(shù)為多個(gè)時(shí)稱為多目標(biāo)函數(shù)。

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

×

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

(i=1,2,…)時(shí)，設(shè)計(jì)變量X取得一系列值的集合?！?.3優(yōu)化設(shè)計(jì)的三大要素x1x20F(X)=εx1x2等值線的“心”（以二維為例）一個(gè)“心”：是單峰函數(shù)的極（?。┲迭c(diǎn)，是全局極（?。┲迭c(diǎn)。沒有“心”：例，線性函數(shù)的等值線是平行的，無“心”，認(rèn)為極值點(diǎn)在無窮遠(yuǎn)處。多個(gè)“心”：不是單峰函數(shù)，每個(gè)極（小）值點(diǎn)只是局部極（?。┲迭c(diǎn)，必須通過比較各個(gè)極值點(diǎn)的值，才能確定極（?。┲迭c(diǎn)。等值線的形狀：同心圓族、橢圓族，近似橢圓族、直線等等值線的疏密：沿等值線密的方向，函數(shù)值變化快；沿等值線疏的方向，函數(shù)值變化慢。等值線的疏密定性反應(yīng)函數(shù)值變化率。x2優(yōu)化問題的幾何解釋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優(yōu)化設(shè)計(jì)的分類一.按模型性質(zhì)分：

1.確定型優(yōu)化問題：靜態(tài)優(yōu)化問題（與時(shí)間無關(guān)）動(dòng)態(tài)優(yōu)化問題（隨時(shí)間變化）

2.不確定型優(yōu)化問題（隨機(jī)優(yōu)化問題）二.按約束情況分1.按有無約束分：無約束優(yōu)化問題約束優(yōu)化問題

2.按約束性質(zhì)分：區(qū)域約束（幾何約束、邊界約束）性能約束（功能約束、性態(tài)約束）§1.4

優(yōu)化設(shè)計(jì)的分類四.按目標(biāo)函數(shù)和約束函數(shù)的特性分：

1.線性規(guī)劃問題

2.非線性規(guī)劃問題

五.按目標(biāo)函數(shù)的個(gè)數(shù)分：

1.單目標(biāo)優(yōu)化問題2.多目標(biāo)優(yōu)化問題六.按設(shè)計(jì)變量性質(zhì)分1.連續(xù)變量2.離散變量3.隨機(jī)變量數(shù)學(xué)模型求解：數(shù)學(xué)解析法：把優(yōu)化對(duì)象用數(shù)學(xué)模型描述出來后，用數(shù)學(xué)解析法來求出最優(yōu)解。它是優(yōu)化設(shè)計(jì)的理論基礎(chǔ)。但它僅限于維數(shù)較少且易求導(dǎo)的優(yōu)化問題的求解。圖解法數(shù)：直接用作圖的方法來求解優(yōu)化問題，通過畫出目標(biāo)函數(shù)和約束函數(shù)的圖形，求出最優(yōu)解。特點(diǎn)是簡(jiǎn)單直觀，但僅限于n≤2的低維優(yōu)化問題的求解。數(shù)值迭代法：完全是依賴于計(jì)算機(jī)的數(shù)值計(jì)算特點(diǎn)而產(chǎn)生的，它是具有一定邏輯結(jié)構(gòu)并按一定格式反復(fù)迭代計(jì)算，逐步逼近優(yōu)化問題最優(yōu)解的一種方法。采用數(shù)值迭代法可以求解各種優(yōu)化問題?！?.5優(yōu)化設(shè)計(jì)的迭代算法

三個(gè)問題：

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

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

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

（３）函數(shù)梯度充分小準(zhǔn)則2.迭代計(jì)算的終止準(zhǔn)則

第二章優(yōu)化設(shè)計(jì)的數(shù)學(xué)基礎(chǔ)2.1多元函數(shù)的導(dǎo)數(shù)與梯度2.4凸集、凸函數(shù)與凸規(guī)劃2.2多元函數(shù)的泰勒展開2.3無約束優(yōu)化極值條件2.5等式約束優(yōu)化極值條件2.6不等式約束優(yōu)化極值條件§2.1

多元函數(shù)的導(dǎo)數(shù)與梯度一、方向?qū)?shù)二元函數(shù)f(x1，x2)在X

(0)的偏導(dǎo)數(shù)為：分別表示沿坐標(biāo)軸x1和x2方向在X

(0)處的f(X)變化率。f(X)在X0點(diǎn)沿d方向的方向?qū)?shù):§2.1

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

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

(0)點(diǎn)沿d方向的方向?qū)?shù):§2.1

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

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

多元函數(shù)的導(dǎo)數(shù)與梯度投影形式：§2.1

多元函數(shù)的導(dǎo)數(shù)與梯度方向?qū)?shù)最大值發(fā)生在:結(jié)論:

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

多元函數(shù)的導(dǎo)數(shù)與梯度x1x20-▽f(X

(0))▽f(X

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

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

多元函數(shù)的導(dǎo)數(shù)與梯度梯度重要性質(zhì)：

①梯度是X

(0)點(diǎn)處最大的方向?qū)?shù)；②梯度方向是過點(diǎn)的等值線的法線方向；③梯度是X(0)點(diǎn)處的局部性質(zhì)；④梯度指向函數(shù)變化率最大的方向；⑤正梯度方向是函數(shù)值最速上升的方向，負(fù)梯度方向是函數(shù)值最速下降的方向?！?.1

多元函數(shù)的導(dǎo)數(shù)與梯度

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

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

最速下降方向，并求沿這個(gè)方向移動(dòng)一個(gè)單位長(zhǎng)度后

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

多元函數(shù)的導(dǎo)數(shù)與梯度新點(diǎn)是這個(gè)方向上的單位向量是：§2.1

多元函數(shù)的導(dǎo)數(shù)與梯度§2.2

多元函數(shù)的泰勒展開一元函數(shù)泰勒展開:二元函數(shù)泰勒展開:§2.2

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

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

無約束優(yōu)化問題的極值條件一元函數(shù)極值條件:必要條件極小值極大值偶次階導(dǎo)數(shù)不為零為極值點(diǎn)奇次階導(dǎo)數(shù)不為零為拐點(diǎn)§2.3

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

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

無約束優(yōu)化問題的極值條件一階主子式：二階主子式：為極值點(diǎn)，f(X

(0))=0為極值§2.3

無約束優(yōu)化問題的極值條件n元函數(shù)極值充分條件:海塞矩陣為正定。函數(shù)f(X)在X*附近的一切X均滿足不等式函數(shù)f(X)在X*處取得局部極小值，稱X*為局部極小點(diǎn)。而優(yōu)化問題一般是要求目標(biāo)函數(shù)在某一區(qū)域內(nèi)的全局極小點(diǎn)?！?.4

凸集、凸函數(shù)與凸規(guī)劃一、凸集一個(gè)點(diǎn)集（或區(qū)域），如果連接其中任意兩點(diǎn)的線段都全部包含在該集合內(nèi)，就稱該點(diǎn)集為凸集，否則為非凸集?！?.4

凸集、凸函數(shù)與凸規(guī)劃x1x20凸集非凸集x1x2yx2x1x1x20y凸集性質(zhì):

1)凸集乘一個(gè)實(shí)數(shù)后依然是凸集

2)兩個(gè)凸集的和依然是凸集

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

凸集、凸函數(shù)與凸規(guī)劃0A2AA+BAB0AB二、凸函數(shù)x1、x2為凸集域內(nèi)的任意兩點(diǎn)，如存在不等式：§2.4

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

Hessian矩陣)判斷§2.4

凸集、凸函數(shù)與凸規(guī)劃Hessian矩陣G(X)在R上處處半正定。主子式>0時(shí)矩陣正定主子式≥0時(shí)矩陣半正定主子式＜0時(shí)矩陣負(fù)定主子式≤0時(shí)矩陣半負(fù)定四、凸規(guī)劃對(duì)于約束優(yōu)化問題若，都為凸函數(shù)，則此問題為凸規(guī)劃?！?.4

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

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

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

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

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

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

為最優(yōu)點(diǎn)的依據(jù)作為約束優(yōu)化的收斂條件。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搜索區(qū)間的確定3.2區(qū)間消去法原理3.4一維搜索的插值法求解一維目標(biāo)函數(shù)f(X)最優(yōu)解的過程，稱為一維優(yōu)化(一維搜索)，所使用的方法稱為一維優(yōu)化方法。由前數(shù)值迭代法可知，求某目標(biāo)函數(shù)的最優(yōu)值時(shí)，迭代過程每一步的格式都是從某一定點(diǎn)X(k)

出發(fā)，沿著某一使目標(biāo)函數(shù)下降的規(guī)定方向S(k)搜索，以找出此方向的極小點(diǎn)X(k+1)

。這一過程是各種最優(yōu)化方法的一種基本過程。一維搜索方法一般分兩步進(jìn)行：

■

首先確定一個(gè)包含函數(shù)極小點(diǎn)的初始區(qū)間，即確定

函數(shù)的搜索區(qū)間，該區(qū)間必須是單峰區(qū)間；

■然后采用縮小區(qū)間或插值逼近的方法得到最優(yōu)步長(zhǎng)，

最終求出該搜索區(qū)間內(nèi)的一維極小點(diǎn)。§3.1搜索區(qū)間的確定根據(jù)函數(shù)的變化情況，可將區(qū)間分為單峰區(qū)間和多峰區(qū)間。所謂單峰區(qū)間，就是在該區(qū)間內(nèi)的函數(shù)變化只有一個(gè)峰值，即函數(shù)的極小值。

即在單峰區(qū)間內(nèi)的極小值點(diǎn)X*的左側(cè)：函數(shù)呈下降趨勢(shì)，而在單峰區(qū)間內(nèi)的極小值點(diǎn)X*

的右側(cè)：函數(shù)呈上升趨勢(shì)。也就是說，單峰區(qū)間的函數(shù)值呈“高-低-高”的變化特征?！?.1搜索區(qū)間的確定x*abx0f(x)

目前在一維優(yōu)化搜索中確定單峰區(qū)間常用的方法是進(jìn)退試算法。

進(jìn)退試算法的基本思想為：

1)按照一定的規(guī)律給出若干試算點(diǎn)，

2)依次比較各試算點(diǎn)的函數(shù)值的大小，

3)直到找到相鄰三點(diǎn)函數(shù)值按“高-低-高”

變化的單峰區(qū)間為止§3.1搜索區(qū)間的確定

進(jìn)退試算法的運(yùn)算步驟如下：(2)將α0及α0+h代入目標(biāo)函數(shù)f(x)進(jìn)行計(jì)算并比較大小(1)給定初始點(diǎn)α0和初始步長(zhǎng)h§3.1搜索區(qū)間的確定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)，則所計(jì)算的相鄰三點(diǎn)

的函數(shù)值已具“高-低-高”特征，這時(shí)可確定搜索區(qū)間

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

的右側(cè)，需做前進(jìn)試算。

否則，將步長(zhǎng)再加倍，并重復(fù)上述運(yùn)算?！?.1搜索區(qū)間的確定在做前進(jìn)運(yùn)算時(shí)，為加速計(jì)算，可將步長(zhǎng)h

增加2倍，并取計(jì)算新點(diǎn)為α0+h+2h=α0+3h

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

的左側(cè)，需做后退試算。在做后退運(yùn)算時(shí)，應(yīng)將步長(zhǎng)變?yōu)?h

，并從

點(diǎn)出α0發(fā)，得到后退點(diǎn)為α0-h

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

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

a1

b1baabb

b1b1§3.2區(qū)間消去法原理f1>f2

f1<f2

f1=f2

f(x)

f(x)

f(x)

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

a1

b1bf(b1)f(a1)a1ab

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

適用于[a,b]區(qū)間上的任何單谷函數(shù)求極小值問題。對(duì)函數(shù)除要求“單峰”外不作其他要求，甚至可以不連續(xù)。適應(yīng)面相當(dāng)廣?；驹頌閰^(qū)間消去法§3.3黃金分割法黃金分割法插入兩點(diǎn)：f(a2)af(a1)

a1

a2bf(a2)af(a1)

a1b

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

b,

,

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

x1

x2b

x2f(x2)

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

初始點(diǎn)x0=0,步長(zhǎng)h=1,精度

ε=0.2。解：1）確定初始區(qū)間

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

x2=x0+h=0+1=1

f2=f(x2)=1

由于f1>f2,應(yīng)繼續(xù)向前探測(cè)

x3=

x0+2h=0+2=2

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

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

第一次縮小區(qū)間：

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

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

f2=f1=0.282

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

第三次縮小區(qū)間：令x1=x2=0.764,

f1=f2=0.282

x2=0.472+0.618×(1.236-0.472)=0.944,f2=0.747由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0.472,0.944]由于b-a=0.944-0.472=0.472>0.2,應(yīng)繼續(xù)縮小區(qū)間?！?.3黃金分割法

第四次縮小區(qū)間：令x2=x1=0.764,

f2=f1=0.282

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

f2=f1=0.223

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

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

x=0.667,f(x)=0.222一、牛頓法§3.4插值方法利用一點(diǎn)的函數(shù)值、一階導(dǎo)數(shù)以及二階導(dǎo)數(shù)構(gòu)造二次多項(xiàng)式。用構(gòu)造的二次多項(xiàng)式的極小點(diǎn)作為原函數(shù)極小點(diǎn)的近似。x*xf(x)

x2φ0(x)

x0f(x)

φ1(x)

x1一、牛頓法設(shè)f(x)為一個(gè)連續(xù)可微的函數(shù)，則在點(diǎn)x0附近進(jìn)行泰勒展開并保留到二次項(xiàng)：用二次函數(shù)φ(x)的極小點(diǎn)x1作為f(x)極小點(diǎn)的一個(gè)近似點(diǎn)。根據(jù)極值必要條件:§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)，相當(dāng)于用一斜直線φ

′(x)代替曲線f

′(x)。這樣各個(gè)近似點(diǎn)是通過對(duì)作f

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

f(x)

φ0(x)

φ1(x)

f′

(x)

f′

(x)

x*x0φ′1(x)

x2x1牛頓法程序框圖

開始計(jì)算，YN給定初始點(diǎn)，誤差,令k=0計(jì)算，結(jié)束數(shù)值\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，試用牛頓法計(jì)算其極小點(diǎn)。給定初始點(diǎn)x0=3，ε=0.001，計(jì)算公式：函數(shù)的二階導(dǎo)數(shù)：解：函數(shù)的一階導(dǎo)數(shù)：§3.4插值方法

優(yōu)點(diǎn)：1）收斂速度快。

缺點(diǎn)：1）要計(jì)算函數(shù)的一階和二階導(dǎo)數(shù)，增加每次迭代的工作量。

2）數(shù)值微分計(jì)算函數(shù)二階導(dǎo)數(shù)，舍入誤差將嚴(yán)重影響牛頓法的收斂速度，f

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

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

在給定的單峰區(qū)間中，利用目標(biāo)函數(shù)上的三個(gè)點(diǎn)來構(gòu)造一個(gè)二次插值函數(shù)，以近似地表達(dá)原目標(biāo)函數(shù)f(a)，并求這個(gè)插值函數(shù)的極小點(diǎn)近似作為原目標(biāo)函數(shù)的極小點(diǎn)。

§3.4插值方法f(x)xf1x1f2x2f3x3xpx*y0xxp1x1x2xpx3xy0x*y1y2ypy3x1x2xpx*y1y2ypyp1xpxp1x1x2xpx3xy0x*y1y2ypy3x2x3xy0x*y2ypy3yp1構(gòu)造的二次插值函數(shù)曲線通過原函數(shù)上的三個(gè)點(diǎn):

解得系數(shù)可求得二、二次插值法（拋物線法）§3.4插值方法二次插值法程序框圖開始計(jì)算，YN給定,縮短區(qū)間名稱置換結(jié)束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)連續(xù)，不要求其一階可微；（2）收斂速度比黃金分割法快，但可靠性不如黃金分割

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

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

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

xp=0.607,fp=0.243

由于fp<f2,xp>x2,新區(qū)間[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,新區(qū)間[a,b]=[a,x2]=[0,1]|x2-xp|=|1-0.555|=0.445>0.2,應(yīng)繼續(xù)迭代。yp→y2y2→y3xpx3x2x1x2x3xx2x3xp第四章無約束優(yōu)化方法4.1最速下降法4.2牛頓型方法4.3共軛梯度法4.6鮑威爾方法4.4變尺度法4.5坐標(biāo)輪換法4.7單形替換法無約束優(yōu)化問題表達(dá)形式：求設(shè)計(jì)變量使目標(biāo)函數(shù)數(shù)值迭代算法公式:從選定的某初始點(diǎn)X0出發(fā)，沿著以一定規(guī)律產(chǎn)生的搜索方向d

k,取適當(dāng)?shù)牡介L(zhǎng)ak,逐次搜尋函數(shù)值下降的新迭代點(diǎn)Xk+1,使之逐步逼近最優(yōu)點(diǎn)X*。概述無約束優(yōu)化方法分類間接法:利用目標(biāo)函數(shù)的一階或二階導(dǎo)數(shù)直接法:利用目標(biāo)函數(shù)值最速下降法、牛頓法、共軛梯度法、變尺度法坐標(biāo)輪換法、鮑威爾方法、單形替換法等

把初始點(diǎn)X0

、搜索方向d

k、迭代步長(zhǎng)ak

稱為優(yōu)化方法算法的三要素。其中搜索方向d

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

(最速下降方向)，使函數(shù)值在該點(diǎn)附近的范圍內(nèi)下降最快?！?.1最速下降法x1x20為了使目標(biāo)函數(shù)值沿搜索方向-▽f(Xk)

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

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

§4.1最速下降法算出一維搜索最佳步長(zhǎng)

§4.1最速下降法第一次迭代設(shè)計(jì)點(diǎn)位置和函數(shù)值

繼續(xù)作下去，經(jīng)10次迭代后，得到最優(yōu)解

最速下降法評(píng)價(jià)：迭代過程簡(jiǎn)單，對(duì)初始點(diǎn)選擇要求不高。梯度方向目標(biāo)函數(shù)值下降迅速只是個(gè)局部性質(zhì)，從整體來看，不一定是收斂最快的方向。梯度法相鄰兩次搜索方向的正交性，決定了迭代全過程的搜索路線呈鋸齒狀，在遠(yuǎn)離極小點(diǎn)時(shí)逼近速度較快，而在接近極小點(diǎn)時(shí)逼近速度較慢?！?.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鄰域內(nèi)用一個(gè)二次函數(shù)φ(X)來近似代替原目標(biāo)函數(shù)，并將φ(X)的極小點(diǎn)作為對(duì)目標(biāo)函數(shù)f(X)

求優(yōu)的下一個(gè)迭代點(diǎn)。經(jīng)多次迭代，使之逼近目標(biāo)函數(shù)f(X)的極小點(diǎn)?！?.2牛頓型方法設(shè)為的極小值點(diǎn)：牛頓法迭代公式:

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

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

:阻尼因子，沿牛頓方向進(jìn)行一維搜索的最佳步長(zhǎng)，由下式求得：

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

法求逆矩陣，進(jìn)而不能構(gòu)造牛頓法方向；

（2）

不僅要計(jì)算梯度，還要求海賽矩陣及其逆矩陣，計(jì)算量和存儲(chǔ)量大。

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

則這n個(gè)向量線性無關(guān)。2）在n維空間中互相共軛的非零向量個(gè)數(shù)不超過n。

3）從任意初始點(diǎn)出發(fā)，順次沿n個(gè)G的共軛方向d0,d1,d2,…,進(jìn)行一維搜索，最多經(jīng)過

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

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

y1=x1,y2=5x2則函數(shù)f(X)變?yōu)椋骸?.4變尺度法利用最速下降法經(jīng)10次迭代后，得到最優(yōu)解

例題：搜索最佳步長(zhǎng)可由極值條件：由沿負(fù)梯度方向進(jìn)行一維搜索：§4.4變尺度法經(jīng)變換后，只需一次迭代，就可找到最優(yōu)解。這是因?yàn)榻?jīng)過尺度變換：等值線由橢圓變成圓。從而算得一步計(jì)算后設(shè)計(jì)點(diǎn)的位置及其目標(biāo)函數(shù)：x0x1x2x1x20y2y1Y0基本思想最速下降法法構(gòu)造簡(jiǎn)單，只用到一階偏導(dǎo)數(shù)，計(jì)算量小，迭代初期收斂速度快，但當(dāng)?shù)阶顑?yōu)點(diǎn)附近時(shí)收斂速度很慢；牛頓法收斂很快，對(duì)于二次函數(shù)只需迭代一次便達(dá)到最優(yōu)點(diǎn)，對(duì)非二次函數(shù)也能較快迭代到最優(yōu)點(diǎn)，但要計(jì)算二階偏導(dǎo)數(shù)矩陣及其逆陣，對(duì)維數(shù)較高的優(yōu)化問題，其計(jì)算工作和存儲(chǔ)量都太大。

變量的尺度變換是放大或縮小各個(gè)坐標(biāo)。通過尺度變換可以把函數(shù)的偏心程度降到最低限度。

§4.4變尺度法進(jìn)行尺度變換在新的坐標(biāo)系中，函數(shù)f(X)的二次項(xiàng)變?yōu)椋耗康模簻p少二次項(xiàng)的偏心如G是正定，則總存在矩陣Q，使得：對(duì)于二次函數(shù):§4.4變尺度法

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

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

，則得到阻尼牛頓法；如當(dāng)矩陣Ak

不斷地迭代而能很好地逼近時(shí)，就可以不再需要計(jì)算二階導(dǎo)數(shù)。變尺度法的關(guān)鍵在于尺度矩陣Ak的產(chǎn)生?！?.4變尺度法1）對(duì)變尺度矩陣的要求：2.構(gòu)造尺度矩陣Ak①要求｛Ak｝中的每一個(gè)矩陣都是對(duì)稱正定矩陣

∵要求dk=-Ak

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

Tdk<0∴－▽f(Xk)

TAk

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

▽f(Xk)＞0

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

Ak＋1

＝Ak

＋△Ak

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

應(yīng)該是一輪迭代的始點(diǎn)和終點(diǎn)，不是某搜索方向的前后迭代點(diǎn)。NN開始初始點(diǎn),誤差,坐標(biāo)輪換法的流程圖Y結(jié)束Y沿著ei方向一維搜索ai計(jì)算，例:用坐標(biāo)輪換