第三章無(wú)約束優(yōu)化方法

第三章無(wú)約束優(yōu)化方法第一頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.1引言一.

目的：求一組n維設(shè)計(jì)變量X=[x1,x2,…,xn]T,使目標(biāo)函數(shù)達(dá)到

min.f(x)X∈Rn即求目標(biāo)函數(shù)的最優(yōu)解：最優(yōu)點(diǎn)x*和最優(yōu)值f(x*)。二.意義：

為約束優(yōu)化方法的研究提供了策略思想、概念基礎(chǔ)和基本方法；為約束優(yōu)化問(wèn)題的間接解法提供了有效而方便的方法；對(duì)于某些工程問(wèn)題，進(jìn)行分析后，便于提供解決的有效方法；約束優(yōu)化問(wèn)題的求解往往可以通過(guò)一系列無(wú)約束優(yōu)化方法實(shí)現(xiàn)；無(wú)約束優(yōu)化問(wèn)題的解法是優(yōu)化設(shè)計(jì)方法的基本組成部分。第二頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.1引言三.內(nèi)容：一維搜索：求最優(yōu)步長(zhǎng)因子α(k)多維（變量）優(yōu)化：確定搜索方向S(k)黃金分割切線法平分法插值法格點(diǎn)法坐標(biāo)輪換法最速下降法共軛方向法鮑威爾法梯度法共軛梯度法牛頓法單形替換法變尺度法第三頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.1引言四.無(wú)約束優(yōu)化方法計(jì)算步驟：1、選擇一個(gè)初始點(diǎn)x(0)，這一點(diǎn)越靠近極小點(diǎn)x*越好。2、若已經(jīng)取得某設(shè)計(jì)點(diǎn)x(k)，并且該點(diǎn)不是近似極小點(diǎn)，則在x(k)點(diǎn)根據(jù)函數(shù)f(x)的性質(zhì)，選擇一個(gè)方向S(k)，并且沿此方向搜索函數(shù)值是下降的，稱下降方向。3、當(dāng)搜索方向S(k)確定后，由x(k)點(diǎn)出發(fā)，沿S(k)方向進(jìn)行搜索，定出步長(zhǎng)因子(k)，得到新的設(shè)計(jì)點(diǎn)：

x(k+1)=x(k)+(k)S(k)，并滿足f(x(k+1))<f(x(k))4、若x(k+1)滿足迭代計(jì)算終止條件，x(k+1)點(diǎn)作為x*；否則從該點(diǎn)出發(fā)，返回第二步繼續(xù)搜索迭代。第四頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四開始給定x和S的初始值計(jì)算使f（x+S）極小x＝x+S

滿足收斂條件？結(jié)束形成新的S無(wú)約束優(yōu)化算法粗框圖第五頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四

無(wú)約束優(yōu)化數(shù)值計(jì)算方法采用的是搜索方法，其基本思想是從給定的初始點(diǎn)出發(fā)，沿某一個(gè)搜索方向進(jìn)行不斷的搜索，確定最佳步長(zhǎng)使函數(shù)值沿搜索方向下降最大，其迭代公式為x(k+1)=x(k)+(k)S(k)各種無(wú)約束優(yōu)化方法的區(qū)別在于確定其搜索方向的S(k)的方法不同。所以，搜索方向的構(gòu)成問(wèn)題是無(wú)約束優(yōu)化問(wèn)題的關(guān)鍵。五.無(wú)約束優(yōu)化方法的關(guān)鍵問(wèn)題：§3.1引言第六頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四六.無(wú)約束優(yōu)化方法的分類：§3.1引言

無(wú)約束優(yōu)化方法的分類依據(jù)就是根據(jù)(k)和S(k)的確定方法而定的。若根據(jù)構(gòu)成搜索方向所使用的信息性質(zhì)的不同，可以分為兩類。

1、間接法又稱解析法，是利用目標(biāo)函數(shù)導(dǎo)數(shù)的無(wú)約束優(yōu)化方法，如最速下降法、共軛梯度法、牛頓法及變尺度法等。

2、直接法

只利用目標(biāo)函數(shù)值的無(wú)約束優(yōu)化方法，如坐標(biāo)輪換法、鮑威爾法及單形替換法等。第七頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.2一維搜索方法一.一維搜索：定義:

在第K次迭代時(shí)，從已知點(diǎn)X(k)出發(fā)，沿給定方向求最優(yōu)步長(zhǎng)因子α(k)，使f(X(k)+α

S(k))達(dá)到最小值的過(guò)程，稱為一維搜索。方法：1.解析法：

f(x(k+1)

)=min.f(x(k)+α

S(k))=f(x(k)+α(k)S(k))

步驟:①f(X(k)+αS(k))沿S(k)

方向x(k)

臺(tái)勞展開；②取二次近似：第八頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四對(duì)α求導(dǎo)，令其為零。

2.數(shù)值迭代法：直接法——應(yīng)用序列消去原理：分?jǐn)?shù)法、黃金分割法近似法——利用多項(xiàng)式函數(shù)逼近（曲線擬合）原理：

二次插值法、三次插值法④求得最優(yōu)步長(zhǎng)因子：§3.2一維搜索方法第九頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四二.迭代法求解一維搜索問(wèn)題的基本思想：

先選定一個(gè)初始點(diǎn)x0，從x0出發(fā)沿某一選定方向p0求f(x)的極小點(diǎn)，設(shè)其為x1；然后再?gòu)膞1出發(fā)沿某一選定方向p1求f(x)的極小點(diǎn)，設(shè)其為x2；如此下去，從xk出發(fā)沿某一選定方向pk求的極小點(diǎn)xk+1，…

，直到求得的xk滿足要求為止。求得的值是逐漸下降的：

稱pk為第k次的搜索方向，因此，在過(guò)xk的pk方向上，任意一點(diǎn)可以表示為x=xk+t*pk，目標(biāo)函數(shù)值為f(xk+t*pk)，目標(biāo)函數(shù)實(shí)際上成了一元函數(shù)。所以沿pk方向求f(x)的極小點(diǎn)，就是求一元函數(shù)f(xk+t*pk)的極小問(wèn)題，表示為：總結(jié)：將優(yōu)化問(wèn)題轉(zhuǎn)化為一系列的一維搜索問(wèn)題§3.2一維搜索方法第十頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四沿方向S的一維搜索第十一頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.2一維搜索方法單峰區(qū)間解析概念：

在區(qū)間[α1，α3]內(nèi)，函數(shù)只有一個(gè)峰值，則此區(qū)間為單峰區(qū)間。單峰區(qū)間內(nèi)，一定存在一點(diǎn)α*，當(dāng)任意一點(diǎn)α2＞α*時(shí)，f(α2)＞f(α*)，說(shuō)明：?jiǎn)畏鍏^(qū)間內(nèi)，函數(shù)可以有不可微點(diǎn)，也可以是不連續(xù)函數(shù)；三.搜索區(qū)間的確定：f(x)0α1α3α0αf(x)α3α1f(α)αα3α2α*α10當(dāng)α2＜α*時(shí)，仍有f(α2)＞f(α*)，則α*是最優(yōu)點(diǎn)，也即為最優(yōu)步長(zhǎng)因子α(k)。α2確定的搜索區(qū)間必定是一個(gè)含有最優(yōu)點(diǎn)α*的單峰區(qū)間。第十二頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.2一維搜索方法2。單峰區(qū)間幾何概念：

指函數(shù)在區(qū)間內(nèi)只有一個(gè)極小點(diǎn)。在極小點(diǎn)左邊的函數(shù)值應(yīng)是嚴(yán)格下降，在極小點(diǎn)右邊的函數(shù)值應(yīng)是嚴(yán)格上升，即單峰區(qū)間內(nèi)的函數(shù)值具有的特征是：“高—低—高”。進(jìn)退法確定的單峰區(qū)間三.搜索區(qū)間的確定：第十三頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.2一維搜索方法3.定步長(zhǎng)搜索法:4.加速步長(zhǎng)搜索法：f2=f(α1+t0)α1f1第十四頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四解：計(jì)算試點(diǎn)例3-1

用進(jìn)退法求單變量函數(shù)的搜索區(qū)間。初始點(diǎn)，步長(zhǎng)比較兩試點(diǎn)函數(shù)值，由于作前進(jìn)搜索比較兩試點(diǎn)函數(shù)值，由于作前進(jìn)搜索比較兩試點(diǎn)函數(shù)值，由于作前進(jìn)搜索此時(shí)，三個(gè)試點(diǎn)函數(shù)值已經(jīng)出現(xiàn)“高－低－高”特征，得搜索區(qū)間為第十五頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.2一維搜索方法四.黃金分割法(0.618)：1.序列消去原理：f(α)αα3(1)α12α*α1(1)0α3(2)α11α21α22α1(2)α1(3)α3(3)第十六頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.2一維搜索方法黃金分割法消去示例：第十七頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.2一維搜索方法2.黃金分割與0.618：bd

古希臘建筑師認(rèn)為：邊長(zhǎng)為b，d的矩形建筑物，若邊長(zhǎng)能符合以下條件，則最美觀：歐幾里德幾何稱這種邊長(zhǎng)分割為黃金分割。

序列消去法中，為提高效率，減少計(jì)算量和存儲(chǔ)量，希望第十八頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四黃金分割法的算法框圖第十九頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四解：在搜索區(qū)間內(nèi)取兩試點(diǎn)并且計(jì)算它們函數(shù)值

比較兩試點(diǎn)函數(shù)值，縮短搜索區(qū)間，由于，消去右區(qū)間，令：例3-2用黃金分割法求單變量函數(shù)的極小點(diǎn)。初始搜索區(qū)間，迭代精度第二十頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四判斷迭代終止條件：

不滿足迭代終止條件。再取兩試點(diǎn)并且比較它們的函數(shù)值，繼續(xù)縮短搜索區(qū)間。搜索區(qū)間經(jīng)過(guò)6次縮短（中間迭代過(guò)程略）后，區(qū)間長(zhǎng)度為：可以終止迭代，得到近似極小點(diǎn)和最優(yōu)解

第二十一頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.2一維搜索方法五.二次插值法（拋物線法）：1.基本原理：步驟：第二十二頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.2一維搜索方法2.步驟(續(xù))：3.結(jié)果分析：?jiǎn)栴}：若不滿足精度，如何縮小區(qū)間，再擬合（分四種情況分析）？

②令：第二十三頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四單谷搜索區(qū)間縮短情況x1x2x3xP*f2fP*x1x1x1x2x2x2xP*xP*xP*x3x3x3f2f2f2fP*fP*fP*bacd第二十四頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四入口xp*>x2?f2*>fP*?f2<fP*?x3x2f3

f2x2xp*f2

fP*x1x2f1

f2x2xp*f2

fP*出口YYYNNNabcdx3xp*f3

fP*x1xp*f1

fP*二次插值法區(qū)間縮短流程圖第二十五頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.2一維搜索方法

與黃金分割法相比，二次插值法充分利用函數(shù)值的信息；收斂快；調(diào)用函數(shù)次數(shù)少。4.方法評(píng)價(jià):5.迭代終止條件:當(dāng)滿足如下兩個(gè)條件，可終止迭代：

如果和兩點(diǎn)的距離很小，即：

如果和充分接近，即：第二十六頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四二次插值法的算法框圖第二十七頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四解：1）確定初始插值結(jié)點(diǎn)與函數(shù)值

2）計(jì)算插值函數(shù)極小點(diǎn)

例3-3用二次插值法求一維函數(shù)的最優(yōu)解。初始單谷搜索區(qū)間，迭代精度第二十八頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四

由于判別式成立，表明落在單谷搜索區(qū)間之內(nèi)

3）縮短單谷搜索區(qū)間

由于和，則舍棄左邊的區(qū)間，構(gòu)成縮短后的新搜索區(qū)間。即：第二十九頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四4）檢驗(yàn)迭代終止條件

滿足迭代終止條件，輸出最優(yōu)解

第三十頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四六.切線法：

一維搜索函數(shù)，假定已給出較好的近似點(diǎn)，連續(xù)可微的函數(shù)在極小點(diǎn)附近與一個(gè)二次函數(shù)很接近，所以可以在附近用一個(gè)二次函數(shù)來(lái)逼近函數(shù)：

以二次函數(shù)的極小點(diǎn)作為極小點(diǎn)的一個(gè)新近似點(diǎn)，根據(jù)極值必要條件：§3.2一維搜索方法第三十一頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四解：

1)求函數(shù)的一階、二階導(dǎo)函數(shù)：例3-4

給定函數(shù)，初始值為，控制誤差，試用切線法求其極小點(diǎn)。

2)求

3)求第三十二頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四4.000594.000664.039604.334745.1666784.0472086.86992109.44586184.3332240.005513.3829932.30199153.3518-524.000664.039604.334745.16667343210k值

4)迭代值如下：第三十三頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四切線法流程圖NY開始結(jié)束k=k+1給定

k=0第三十四頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四１.收斂速度快；２.需要計(jì)算函數(shù)的一階和二階導(dǎo)數(shù)，增加迭代工作量；３.要求初始點(diǎn)選得比較好，離極小點(diǎn)不遠(yuǎn)，否則有可能使極小化序列發(fā)散或收斂到非極小點(diǎn)。切線法優(yōu)缺點(diǎn):§3.2一維搜索方法第三十五頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.2一維搜索方法取具有極小點(diǎn)的單峰函數(shù)的探索區(qū)間[a,b]的坐標(biāo)中點(diǎn)作為計(jì)算點(diǎn)，計(jì)算目標(biāo)函數(shù)在該點(diǎn)處的導(dǎo)數(shù)為，并利用函數(shù)在極小點(diǎn)處的導(dǎo)數(shù)為零而在其左側(cè)為負(fù)、右側(cè)為正的原理，來(lái)判斷極小點(diǎn)所在的那一半探索區(qū)間，以消掉另一半?yún)^(qū)間。這樣逐次迭代下去，總能將探索區(qū)間收斂到一個(gè)局部極小點(diǎn)附近，求得極小點(diǎn)的近似解。收斂速度雖然較慢，但縮短率也達(dá)到0.5，特別是每次迭代計(jì)算量較少，可靠性較好，所以仍然是一個(gè)受歡迎的方法。七.平分法：第三十六頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.2一維搜索方法平分法的迭代計(jì)算步驟:給定計(jì)算，若，則停止迭代并取否則進(jìn)行下一步。計(jì)算，若或，則停止迭代并取若則取為縮短后的搜索區(qū)間轉(zhuǎn)第二步若則取為縮短后的搜索區(qū)間轉(zhuǎn)第二步當(dāng)求解困難時(shí):

可直接計(jì)算并比較兩者大小，用序列消去法原理消去掉近一半的區(qū)域，再重新迭代，直到將探索區(qū)間縮短至精度要求為止。第三十七頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四例3-5

試用平分法求的極小點(diǎn)和極小值，設(shè)解：

1)取

2)計(jì)算

3)縮短搜索區(qū)間為取

4)計(jì)算

5)所以函數(shù)的極小點(diǎn)為,極小值為:第三十八頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.2一維搜索方法設(shè)一維函數(shù)為f(x)，搜索區(qū)間為[a,b]，一維收斂精度為。在區(qū)間[a,b]的內(nèi)部取n個(gè)等分點(diǎn)：x1,x2,…,xn。區(qū)間被分為n+1等分，各分點(diǎn)坐標(biāo)為對(duì)應(yīng)各點(diǎn)的函數(shù)值為y1,y2,…,yn+2。比較其大小，取最小者ym=min{yk,k=1,2,…,n＋2}，則在區(qū)間[xm-1,xm+1]內(nèi)必包含極小點(diǎn)，取[xm-1,xm+1]為縮短后新區(qū)間，若新區(qū)間滿足收斂條件:xm+1-xm+1，則最優(yōu)解為x*=xm，y*=ym

若不能滿足精度要求，把當(dāng)前區(qū)間作為初始搜索區(qū)間，重復(fù)上述步驟直至滿足精度為止。八.格點(diǎn)法：第三十九頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四

新區(qū)間y1ym-1ymym+1Yn＋2x1axm-1xmxm+1Xn＋2b格點(diǎn)法區(qū)間搜索原理第四十頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四格點(diǎn)法流程圖YN開始p=y,m=ky<p給定

m=0,k=1，p=足夠大的數(shù)k=nk=k+1|b-a|<εNYYN第四十一頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四相同點(diǎn)：都是利用區(qū)間消去法原理將初始搜索區(qū)間不斷縮短，從而求得極小點(diǎn)的數(shù)值近似解。不同點(diǎn)：試驗(yàn)點(diǎn)位置的確定方法不同。直接法中試驗(yàn)點(diǎn)的位置是由某種給定的規(guī)律確定的，并未考慮函數(shù)值的分布。黃金分割法是按照等比例0.618縮短率確定的，僅僅利用了試驗(yàn)點(diǎn)函數(shù)值進(jìn)行大小的比較；間接法中，試驗(yàn)點(diǎn)的位置是按函數(shù)值近似分布的極小點(diǎn)確定的，利用了函數(shù)值本身或其導(dǎo)數(shù)信息。當(dāng)函數(shù)具有較好的解析性質(zhì)時(shí)，間接方法比直接方法效果更好?！?.2一維搜索方法九.間接法與直接法的異同點(diǎn)：第四十二頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.2一維搜索方法1.掌握進(jìn)退法確定單谷搜索區(qū)間；2.掌握黃金分割法的原理和程序設(shè)計(jì)；3.掌握二次插值法的原理和程序設(shè)計(jì)；4.掌握切線法的原理和流程；5.了解平分法和格點(diǎn)法。十.學(xué)習(xí)要求：試用二次插值法求的近似極小點(diǎn)和極小值，已知十一.習(xí)題：第四十三頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四一.坐標(biāo)輪換法：1.基本思想：2.搜索方向與步長(zhǎng)：

每次以一個(gè)變量坐標(biāo)軸作為搜索方向，將n維的優(yōu)化問(wèn)題轉(zhuǎn)化為一維搜索問(wèn)題。例，第k輪迭代的第i次搜索，是固定除xi外的n-1個(gè)變量，沿xi變量坐標(biāo)軸作一維搜索，求得極值點(diǎn)xi(k)…n次搜索后獲得極值點(diǎn)序列x1(k),x2(k,…,xn(k)，若未收斂，則開始第k+1次迭代，直至收斂到最優(yōu)點(diǎn)x*?！?.3

坐標(biāo)輪換法、共軛方向法和Poweel法第四十四頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四一.坐標(biāo)輪換法：3.方法評(píng)價(jià)：

方法簡(jiǎn)單，容易實(shí)現(xiàn)。當(dāng)維數(shù)增加時(shí)，效率明顯下降。收斂慢，以振蕩方式逼近最優(yōu)點(diǎn)。

受目標(biāo)函數(shù)的性態(tài)影響很大。如圖a)所示，二次就收斂到極值點(diǎn)；如圖b)所示，多次迭代后逼近極值點(diǎn)；如圖c)所示，目標(biāo)函數(shù)等值線出現(xiàn)山脊（或稱陡谷），在脊線的尖點(diǎn)A處沒(méi)有一個(gè)坐標(biāo)方向可以使函數(shù)值下降，只有在銳角所包含的范圍搜索才可以達(dá)到函數(shù)值下降的目的，故坐標(biāo)輪換法對(duì)此類函數(shù)會(huì)失效?！?.3

坐標(biāo)輪換法、共軛方向法和Poweel法第四十五頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四i=n坐標(biāo)輪換法的流程圖

開始給定：x0,k=1i=1,x0k=x0xik=x0k-1沿ei方向一維搜索求ixik=xi-1k+

ikeix=xkf=f(x)||xnk-x0k||x*=x

f*=f(x*)結(jié)束i=i+1x0k+1=xnkk=k+1NYNY第四十六頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四此問(wèn)題可用一維優(yōu)化方法求解，這里用微分學(xué)求解：解：1.作第一輪迭代計(jì)算得：1)沿e1方向進(jìn)行一維搜索例4-1

用坐標(biāo)輪換法求目標(biāo)函數(shù)的無(wú)約束最優(yōu)解，給定初始點(diǎn)，精度要求其中為第一輪的起始點(diǎn)。?。喊醋顑?yōu)步長(zhǎng)原則確定2)以為新起點(diǎn)，沿e2方向一維搜索：按最優(yōu)步長(zhǎng)原則確定得：3)按迭代終止條件檢驗(yàn)

2.作第二輪迭代計(jì)算，如此共進(jìn)行9輪得到結(jié)果第四十七頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四二.共軛方向法：1.共軛方向的由來(lái)：2.共軛方向的定義：

共軛方向概念是在研究具有正定矩陣G的二次函數(shù)

的極小化問(wèn)題時(shí)形成的。其基本思想是在不用導(dǎo)數(shù)的前提下，在迭代中逐次構(gòu)造G的共軛方向?！?.3

坐標(biāo)輪換法、共軛方向法和Poweel法第四十八頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四3.共軛方向法的二次收斂性：

正定的二元二次函數(shù)的等值線為一組橢圓，任選初始點(diǎn)x0，沿某個(gè)下降方向S0作一維搜索，得x1

此時(shí)，x1點(diǎn)的梯度必然與方向S0垂直，即有：x0x*x11S1-f(x1)S10S0

S0與某一等值線相切于x1點(diǎn)。下一次的迭代，若選擇負(fù)梯度方向?yàn)樗阉鞣较颍瑢a(chǎn)生鋸齒現(xiàn)象。為避免鋸齒的產(chǎn)生，我們?nèi)〉较騍0直指極小點(diǎn)x*，如圖所示。若選定這樣的方向，則對(duì)于二元二次函數(shù)只需進(jìn)行S0

和S1兩次搜索就可以求得極小點(diǎn)x*，即§3.3

坐標(biāo)輪換法、共軛方向法和Poweel法第四十九頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四3.共軛方向法的二次收斂性（續(xù)）：

由于，當(dāng)時(shí)，由是的極小點(diǎn)，應(yīng)滿足極值必要條件，故即：

等式兩端同乘以,得，故兩個(gè)向量，是G的共軛向量。

因此，若要使第二個(gè)迭代點(diǎn)成為正定二元二次函數(shù)的極小點(diǎn)，只要使兩次一維搜索的方向，關(guān)于函數(shù)的二階導(dǎo)數(shù)矩陣G共軛就可以了。

對(duì)于正定二次n維函數(shù)，從任意的初始點(diǎn)出發(fā)，沿著這n個(gè)共軛方向進(jìn)行一維搜索，就可以得到目標(biāo)函數(shù)的極小點(diǎn)。因此，對(duì)于二次函數(shù)來(lái)說(shuō)，經(jīng)過(guò)n步搜索就可以達(dá)到函數(shù)的極小點(diǎn)。對(duì)于非二次n維函數(shù)，可以用二階泰勒級(jí)數(shù)將函數(shù)在極小點(diǎn)附近展開，省略去高于二次的項(xiàng)后可以得到函數(shù)的二次近似，同樣按照二次函數(shù)構(gòu)成共軛方向?！?.3

坐標(biāo)輪換法、共軛方向法和Poweel法第五十頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四4.二維函數(shù)的共軛方向：

二維函數(shù)，任意給定某個(gè)方向，按這個(gè)方向上的兩條平行線進(jìn)行一維搜索求得的極小點(diǎn)為和，它們應(yīng)該是方向?yàn)榈膬蓷l平行線與目標(biāo)函數(shù)等值線的切點(diǎn)。

連接兩個(gè)切點(diǎn)和構(gòu)成向量：

可以證明，如果二維函數(shù)的海塞矩陣H是正定的，則S1向量與向量S2滿足條件：

具有這種性質(zhì)的方向?yàn)殛P(guān)于正定矩陣H的共軛方向?！?.3

坐標(biāo)輪換法、共軛方向法和Poweel法第五十一頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四

所以有：4.二維函數(shù)的共軛方向（續(xù)）：證明：

設(shè)二維函數(shù)在極值點(diǎn)X*附近的二次泰勒展開式為：

由此得函數(shù)的一階導(dǎo)數(shù)：

由于S1為等值線的切線，故方向S1應(yīng)垂直于X(1)

,X(2)

的梯度方向：§3.3

坐標(biāo)輪換法、共軛方向法和Poweel法第五十二頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四

所以有：4.二維函數(shù)的共軛方向（續(xù)2）：

兩式相減得：

由，上式可簡(jiǎn)化為：§3.3

坐標(biāo)輪換法、共軛方向法和Poweel法第五十三頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四5.二維函數(shù)共軛方向法的迭代過(guò)程：

1.令循環(huán)次數(shù)k＝1，取初始點(diǎn)，初始搜索方向?yàn)樽鴺?biāo)方向

4.取下次循環(huán)的初始點(diǎn)，替換掉原來(lái)的第一方向，構(gòu)成新的搜索方向：

5.k=k+1，轉(zhuǎn)步驟2。

2.從出發(fā)，依次沿和進(jìn)行一維搜索，分別得到相應(yīng)的極小點(diǎn)和。

3.構(gòu)建新方向，沿方向進(jìn)行搜索，得到第k次的極小點(diǎn)§3.3

坐標(biāo)輪換法、共軛方向法和Poweel法第五十四頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四6.多維二次函數(shù)共軛方向的構(gòu)建：

如果n維函數(shù)的海賽矩陣是正定的，一組非零向量滿足：

則向量系：是關(guān)于海賽矩陣H共軛，即他們是n個(gè)互為共軛的方向。

§3.3

坐標(biāo)輪換法、共軛方向法和Poweel法第五十五頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四8.方法評(píng)價(jià)：

計(jì)算步驟復(fù)雜;

是二次收斂方法，收斂快。對(duì)非正定函數(shù)，也很有效;

是比較穩(wěn)定的方法。7.說(shuō)明：

若是正定二次函數(shù)，n輪迭代后收斂于最優(yōu)點(diǎn)x*。若是非正定二次函數(shù)，則迭代次數(shù)增加。

若是n維問(wèn)題，步驟相同。搜索方向：第一輪迭代，沿初始方向組Si(1)(i=1,2,…,n)的n個(gè)方向和共軛方向S(1)，搜索n+1次得極值點(diǎn)xn+1(1)

；第二輪迭代，沿方向組Si(2)(i=1,2,…,n；i≠m)的n-1個(gè)方向和共軛方向S(1)，構(gòu)筑共軛方向S(2)搜索n+1次得極值點(diǎn)xn+1(2)

。其中，為保證搜索方向的線性無(wú)關(guān)，去除了Sm(2)方向。

在第k輪迭代中，為避免產(chǎn)生線性相關(guān)或近似線性相關(guān)，需要去除前一輪中的某個(gè)方向Sm(k)。——去除的原則請(qǐng)自學(xué)?！?.3

坐標(biāo)輪換法、共軛方向法和Poweel法第五十六頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四共軛方向法的程序框圖第五十七頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四9.共軛方向法的缺陷：

共軛方向法的迭代過(guò)程可能會(huì)產(chǎn)生不理想的情況，在以后某環(huán)的迭代中可能出現(xiàn)基本方向組為線性相關(guān)向量系。以后的搜索將在維數(shù)下降后的設(shè)計(jì)空間中進(jìn)行，無(wú)法收斂到n維設(shè)計(jì)空間中目標(biāo)函數(shù)的極小點(diǎn)。

以三維問(wèn)題為例，設(shè)從初始點(diǎn)出發(fā)，沿著坐標(biāo)軸方向，進(jìn)行第一環(huán)搜索，在各個(gè)方向獲得極小點(diǎn)為：

由該環(huán)搜索的初始點(diǎn)與終點(diǎn)產(chǎn)生的新生方向：§3.3

坐標(biāo)輪換法、共軛方向法和Poweel法第五十八頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四9.共軛方向法的缺陷（續(xù)）：

如果其中第三維優(yōu)化步長(zhǎng)等于或非常接近0，即表示沿著則坐標(biāo)軸方向的搜索沒(méi)有前進(jìn)或前進(jìn)很少，則共軛方向：

表明向量與向量是線性相關(guān)的。

第2環(huán)搜索的基本方向組中，是與線性相關(guān)或接近線性相關(guān)，即向量在和組成的平面內(nèi)。以后的搜索將在維數(shù)下降（不包含方向）的平面中進(jìn)行，無(wú)法收斂到空間中目標(biāo)函數(shù)的極小點(diǎn)?！?.3

坐標(biāo)輪換法、共軛方向法和Poweel法第五十九頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四三.Poweel法：1.基本步驟：1.給定初始點(diǎn)，選取由n個(gè)線性無(wú)關(guān)的向量組成的初始方向組，置。2.從出發(fā)，順次沿作一維搜索得。接著以為起點(diǎn)，沿方向：移動(dòng)一個(gè)的距離，得到：

分別稱為一輪迭代的始點(diǎn)、終點(diǎn)和反射點(diǎn)。它們所對(duì)應(yīng)的函數(shù)值分別為：

同時(shí)計(jì)算各中間點(diǎn)處的函數(shù)值，并記為：§3.3

坐標(biāo)輪換法、共軛方向法和Poweel法第六十頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.3

坐標(biāo)輪換法、共軛方向法和Poweel法1.基本步驟（續(xù)）：

計(jì)算n個(gè)函數(shù)值之差：3.為了構(gòu)造第k＋1環(huán)基本方向組，采用如下判別式：

按以下兩種情況處理：

其中最大者記作：鮑威爾判別式

a.上式中至少一個(gè)不等式成立，則第k+1環(huán)的基本方向仍用老方向組.,k+1的環(huán)初始點(diǎn)取:

第六十一頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四1.基本步驟（續(xù)2）：b.兩式均不成立，則淘汰函數(shù)值下降最大的方向，并用第k環(huán)的新生方向補(bǔ)入k+1環(huán)基本方向組的最后，即k+1環(huán)的方向組為：

k+1環(huán)的初始點(diǎn)取，是第k環(huán)沿方向搜索的極小點(diǎn)。§3.3

坐標(biāo)輪換法、共軛方向法和Poweel法第六十二頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四鮑威爾法的流程圖第六十三頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四一.梯度法（最速下降法）：1.基本思想：2.負(fù)梯度方向?yàn)樽钏傧陆捣较虻淖C明：

目標(biāo)函數(shù)負(fù)梯度向量方向代表最速下降方向，因此選擇負(fù)梯度向量方向?yàn)樗阉鞣较?，期望很快找到最?yōu)點(diǎn)。S由方向?qū)?shù)概念可得：設(shè)：取最小值－1時(shí)，S為梯度的負(fù)方向?！?.4梯度法和共軛梯度法第六十四頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四4.迭代格式：3.搜索方向：a.任意給定一個(gè)初始步長(zhǎng)，使其滿足：根據(jù)一元函數(shù)的極值必要條件和多元復(fù)合函數(shù)的求導(dǎo)公式，得：或負(fù)梯度方向或單位負(fù)梯度向量5.最佳步長(zhǎng)的選?。篵.沿負(fù)梯度方向作一維搜索，求最佳步長(zhǎng)，對(duì)目標(biāo)函數(shù)求極小，以得到最佳步長(zhǎng)：即：§3.4梯度法和共軛梯度法第六十五頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四

最速下降法向極小點(diǎn)的逼近路徑是鋸齒形路線，越接近極小點(diǎn)，鋸齒越細(xì)，前進(jìn)速度越慢。

這是因?yàn)?，梯度是函?shù)的局部性質(zhì)，從局部上看，在該點(diǎn)附近函數(shù)的下降最快，但從總體上看則走了許多彎路，因此函數(shù)值的下降并不快。5.最佳步長(zhǎng)的選?。ɡm(xù)）：

此式表明，相鄰的兩個(gè)迭代點(diǎn)的梯度是彼此正交的。也即在梯度的迭代過(guò)程中，相鄰的搜索方向相互垂直。6.搜索路徑：§3.4梯度法和共軛梯度法第六十六頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四（1）任選初始迭代點(diǎn)x(0)，選收斂精度。（2）確定x(k)點(diǎn)的梯度(開始k=0)。（3）判斷是否滿足終止條件，若滿足輸出最優(yōu)解，結(jié)束計(jì)算。否則轉(zhuǎn)下步。（4）從x(k)點(diǎn)出發(fā)，沿

方向作一維搜索求最優(yōu)步長(zhǎng)(k)。得下一迭代點(diǎn)。令k=k+1返回步驟（2）。7.迭代終止條件：

采用梯度準(zhǔn)則：8.迭代步驟：§3.4梯度法和共軛梯度法第六十七頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四梯度法流程圖NY開始給定：x(0)，

k=0x*=x(k)f*=f(x(k))結(jié)束x(k)=

x(0)k=k+1第六十八頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.4梯度法和共軛梯度法9.方法評(píng)價(jià)：

迭代過(guò)程簡(jiǎn)單，對(duì)初始點(diǎn)的選擇，要求不高。梯度方向目標(biāo)函數(shù)值下降迅速只是個(gè)局部性質(zhì)，從整體來(lái)看，不一定是收斂最快的方向。以二維二次函數(shù)為例，相鄰兩次的搜索方向是正交的，所以搜索路徑是曲折的鋸齒形的；對(duì)于高維的非線性函數(shù)，接近極值點(diǎn)處，容易陷入穩(wěn)定的鋸齒形搜索路徑。第六十九頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四例4-1

二維無(wú)約束目標(biāo)函數(shù)試用梯度法求其極小值，初始點(diǎn)，精度

解：

1）計(jì)算目標(biāo)函數(shù)在初始點(diǎn)的梯度、梯度的模和單位負(fù)梯度方向第七十頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四2）計(jì)算最佳搜索步長(zhǎng)3）計(jì)算第一次迭代更新值和目標(biāo)函數(shù)值4）當(dāng)?shù)?次時(shí)，滿足終止條件，得到最有值第七十一頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.4梯度法和共軛梯度法二.共軛梯度法（旋轉(zhuǎn)梯度法）：1.基本思想：2.共軛方向：

對(duì)梯度法作一個(gè)修正，將搜索方向由負(fù)梯度方向旋轉(zhuǎn)一個(gè)角度，使相鄰的兩次搜索方向由正交變?yōu)楣曹棧蔀槎问諗俊?.共軛系數(shù)：推導(dǎo)過(guò)程請(qǐng)自學(xué)。β(k)S(k)第七十二頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四步驟：

5.方法評(píng)價(jià)：

迭代程序簡(jiǎn)單，容易實(shí)現(xiàn)，存儲(chǔ)量較小。開始采用梯度方向，目標(biāo)函數(shù)值下降快，后又為旋轉(zhuǎn)梯度方向，具有二次收斂速度，收斂快。§3.4梯度法和共軛梯度法第七十三頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四開始k=0，計(jì)算：-f(x0)

||f(xk+1)

||？結(jié)束求(k)

，x(k+1)=

x(k)+(k)S(k)計(jì)算：f(xk+1)

x*=xk+1f(x*)=f(xk+1)YN給定：x(0)，

kn？x0=xk+1YNSk+1=-f(xk+1)

+

kSkK=K+1共軛梯度法流程圖第七十四頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四例4-2

二維無(wú)約束目標(biāo)函數(shù)試用共軛梯度法求其極小值，初始點(diǎn)，精度

解：

1）計(jì)算目標(biāo)函數(shù)在初始點(diǎn)的梯度、梯度的模和單位負(fù)梯度方向第七十五頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四2）計(jì)算新迭代點(diǎn)的梯度和搜索方向的修正量，進(jìn)行第2次搜索

第七十六頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四可見，共軛梯度法具有兩次收斂性，對(duì)于二維函數(shù)只要經(jīng)過(guò)兩次迭代就可以達(dá)到極值點(diǎn)。

第七十七頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.5

牛頓法和變尺度法一.牛頓法（二階梯度法）：

1.基本思想：

將f(x)在x(k)

點(diǎn)作臺(tái)勞展開，取二次函數(shù)式Φ(x)作為近似函數(shù),以Φ(x)的極小值點(diǎn)作為f(x)的近似極小值點(diǎn)。說(shuō)明：

f(x)若是正定二次函數(shù)，一般迭代一次即可；若是嚴(yán)重非線性函數(shù)，則可能不收斂，或收斂到鞍點(diǎn)。第七十八頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四2.修正牛頓法（阻尼牛頓法）：一.牛頓法（二階梯度法）：

可通過(guò)如下極小化過(guò)程求得：

避免了迭代后函數(shù)上升的現(xiàn)象，保持了牛頓法二次收斂的特性，對(duì)初始點(diǎn)的選取并沒(méi)有苛刻的要求。阻尼牛頓法的計(jì)算步驟：1）給定初始點(diǎn)，收斂精度，置§3.5

牛頓法和變尺度法第七十九頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.5

牛頓法和變尺度法3.方法評(píng)價(jià)：

使用牛頓法時(shí)，若目標(biāo)函數(shù)是嚴(yán)重非線性函數(shù)，則是否收斂將與初始點(diǎn)有很大關(guān)系；而使用修正牛頓法，能保證每次迭代目標(biāo)函數(shù)值下降，從而放寬了對(duì)初始點(diǎn)的要求。若初始點(diǎn)選得合適，牛頓法的收斂速度相當(dāng)快。牛頓法求逆矩陣的工作量大，計(jì)算量與存儲(chǔ)量均隨n2上升。3）求，其中為沿進(jìn)行一維搜索的最佳步長(zhǎng)4）檢查收斂精度。若，則，否則，令，返回2）繼續(xù)進(jìn)行搜索。2）計(jì)算：第八十頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四阻尼牛頓法流程圖第八十一頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.5

牛頓法和變尺度法

變尺度法也稱擬牛頓法，它是基于牛頓法的思想而又作了重大改進(jìn)的一類方法。

梯度法只需計(jì)算函數(shù)的一階偏導(dǎo)數(shù)，計(jì)算量小，當(dāng)?shù)c(diǎn)遠(yuǎn)離最優(yōu)點(diǎn)時(shí)，函數(shù)值下降很快，但當(dāng)?shù)c(diǎn)接近最優(yōu)點(diǎn)時(shí)收斂速度極慢。DFP變尺度法是由Davidon于1959年提出的一種變尺度法；BFGS變尺度法是由Broydon等提出的改進(jìn)算法，提高了算法的穩(wěn)定性。

牛頓法不僅需要計(jì)算一階偏導(dǎo)數(shù)，而且要計(jì)算二階偏導(dǎo)數(shù)及其逆陣，計(jì)算量很大，但牛頓法具有二次收斂性，當(dāng)?shù)c(diǎn)接近最優(yōu)點(diǎn)時(shí)，收斂速度很快。

若迭代過(guò)程先用梯度法，后用牛頓法并避開牛頓法的海賽矩陣的逆矩陣的煩瑣計(jì)算，則可以得到一種較好的優(yōu)化方法，這就是“變尺度法”產(chǎn)生的構(gòu)想。一.變尺度法:第八十二頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.5

牛頓法和變尺度法二.DFP變尺度法:1.變尺度的定義：每確定一次搜索方向，調(diào)整一次模（尺度）的大小，稱為變尺度。2.基本思想：

發(fā)揚(yáng)梯度法和牛頓法各自的優(yōu)點(diǎn)，避免兩者各自的缺點(diǎn)，將兩者結(jié)合起來(lái)，形成變尺度法。第八十三頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.5

牛頓法和變尺度法3.變尺度矩陣的構(gòu)造：原則：

使目標(biāo)函數(shù)值有下降性，則變尺度矩陣應(yīng)為實(shí)對(duì)稱矩陣（請(qǐng)證明）；使算法有二次收斂性，則S(k)(k=1,2,…)應(yīng)關(guān)于H(k)

是共軛的；構(gòu)造變尺度矩陣的遞推公式：4.修正矩陣:

第八十四頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.5

牛頓法和變尺度法步驟：1、選定初始點(diǎn)和收斂精度；2、計(jì)算初始點(diǎn)處的梯度，選取初始對(duì)稱正定矩陣A0，置k=0；3、計(jì)算搜索方向Sk=

-Akgk

；4、沿Sk方向一維搜索，計(jì)算gk+1、sk=xk+1-xk、yk=gk+1-gk。5、判斷是否滿足終止準(zhǔn)則，若滿足輸出最優(yōu)解，否則轉(zhuǎn)6。6、當(dāng)?shù)鷑次還未找到極小點(diǎn)，重置Ak為單位矩陣，并以當(dāng)前點(diǎn)為初始點(diǎn)返回2，否則轉(zhuǎn)7。7、計(jì)算Ak+1=Ak+ΔAk，置k=k+1返回3。第八十五頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四6.方法評(píng)價(jià)：

DFP變尺度法以逐次逼近的方法實(shí)現(xiàn)H-1

的計(jì)算，當(dāng)目標(biāo)函數(shù)的一階導(dǎo)數(shù)易求時(shí)，以一階代替二階導(dǎo)數(shù)的計(jì)算是有效的方法。算法的第一步是梯度法，最速下降；接近x*時(shí)，又采用二次收斂的共軛方向，總的收斂速度較快。

H(k)

近似代表x(k)點(diǎn)的二階導(dǎo)數(shù)，當(dāng)其為零時(shí)，可判斷x(k)為鞍點(diǎn)。

H(k)

的計(jì)算較復(fù)雜，存儲(chǔ)量較大。算法穩(wěn)定性較差，由于計(jì)算機(jī)有舍入誤差，容易使H(k)

的正定性破壞，趨于奇異。

§3.5

牛頓法和變尺度法第八十六頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四DFP變尺度法流程圖第八十七頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四例4-3

二維無(wú)約束目標(biāo)函數(shù)試用DFP算法求其極小值。解：

1）取初始點(diǎn)，為了按DFP法構(gòu)造第一次搜索方向，需要計(jì)算初始點(diǎn)處的梯度：并取初始變尺度矩陣為單位矩陣A0=I，則第一次搜索方向?yàn)椋貉胤较蜻M(jìn)行一維搜索，得：其中，為一維搜索最佳步長(zhǎng)，應(yīng)滿足：第八十八頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四2）再按DFP法構(gòu)造點(diǎn)處的搜索方向，需要計(jì)算：得：代入DFP校正公式，得：第八十九頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四

得：則第二次搜索方向?yàn)椋浩渲?，為一維搜索最佳步長(zhǎng)，應(yīng)滿足：沿d1進(jìn)行一維搜索：第九十頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四3)為了判斷x2點(diǎn)是否為極值點(diǎn)，需計(jì)算x2點(diǎn)處的梯度及其海賽矩陣：

梯度為零向量，海賽矩陣為正定矩陣，可見x2點(diǎn)滿足極值充分必要條件，因此x2為極小點(diǎn)。函數(shù)的極值解為：第九十一頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四DFP算法由于舍入誤差和一維搜索的不精確，有可能導(dǎo)致Ak奇異，而使數(shù)值穩(wěn)定性方面不夠理想。所以1970年提出更穩(wěn)定的算法，稱為BFGS算法，其校正公式為：

因?yàn)樽兂叨确ǖ挠行源偈蛊洳粩喟l(fā)展，所以出現(xiàn)過(guò)許多變尺度法的算法，1970年黃（huang）從共軛條件出發(fā)對(duì)變尺度法做了統(tǒng)一處理，寫出了統(tǒng)一公式：一.BFGS變尺度法:

可以看出，當(dāng)取，就是DFP法的公式。當(dāng)取，就是BFGS法的公式§3.5

牛頓法和變尺度法第九十二頁(yè)，共一百零一頁(yè)，編輯于2023年，星期四§3.6

單形替換法一.單形替換法基本思想:單純形：在一定的空間中的最簡(jiǎn)單的圖形，如三角形，四面體等。

先算出n維空間