機(jī)械優(yōu)化設(shè)計(jì)課件

優(yōu)化設(shè)計(jì)的理論與數(shù)學(xué)基礎(chǔ)1、一元函數(shù)f(x)在k點(diǎn)的泰勒展開式

f(x)=f(x(k))+f’(x(k))(x-x(k))+f”(x(k))(x-x(k))2/2!2、多元函數(shù)f(x)在k點(diǎn)的泰勒展開式及海賽（Hessian)矩陣F(x)=F(x(k))+

FT?

[x-x(k)]+[x-x(k)]T

2F?[x-x(k)]/2梯度

F=海賽矩陣H(x)=

2F=2.1目標(biāo)函數(shù)的泰勒（Taylor)展開式3、二次型函數(shù)

F(x)=xTAx對(duì)于二次函數(shù)F(x)=xTAx。若對(duì)于任意不為零的x=[x1,x2,…,xn],恒有F(x)>0,則相應(yīng)的系數(shù)矩陣A稱為正定矩陣。若恒有F(x)

≥0,則稱A為半正定矩陣。2.2目標(biāo)函數(shù)的等值線（面）設(shè)n維目標(biāo)函數(shù)F(x)=F(x1,x2,…,xn),在n維設(shè)計(jì)空間的任意一點(diǎn)x有確定的函數(shù)值F;反之，對(duì)于某一確定的函數(shù)值將有若干個(gè)設(shè)計(jì)點(diǎn)xi(i=1,2,…)與之相應(yīng)。如果是連續(xù)問題，將有無限多個(gè)確定的設(shè)計(jì)點(diǎn)對(duì)應(yīng)同一個(gè)函數(shù)值，則這些設(shè)計(jì)點(diǎn)在設(shè)計(jì)空間中構(gòu)成的點(diǎn)集稱為等值面（三維空間）、超等值面（四維以上）。對(duì)于二維問題，則稱等值線。2.3無約束優(yōu)化最優(yōu)解的條件一、一元函數(shù)極值條件對(duì)于連續(xù)可微的一元函數(shù)f(x),如在x*點(diǎn)有極值，其必要條件為：f’(x*)=0若x*為有極小值點(diǎn)，其充分條件為：f”(x*)>0二、二元函數(shù)極值條件對(duì)于連續(xù)可微函數(shù)F(x)=F(x1,x2)在x*點(diǎn)有極值，其必要條件為：F(x*)=Θ

三、多維函數(shù)極值條件對(duì)于連續(xù)可微函數(shù)F(x)=F(x1,x2，…,xn)在x*點(diǎn)有極值，其必要條件為：F(x*)=Θ

當(dāng)海賽矩陣正定時(shí)，點(diǎn)x*為極小值2.4凸集與凸函數(shù)2.4.1凸集與非凸集2.4.2凸函數(shù)一、凸函數(shù)的數(shù)學(xué)定義:

若F(x)滿足：則稱F(x)為定義在凸集上的凸函數(shù)二、凸函數(shù)的基本性質(zhì)

1）若F(x)為凸函數(shù)，則λF(x)也是凸函數(shù)。λ為任意正實(shí)數(shù)。

2)若F(x1)、F(x2)為凸函數(shù)，則F(x1)+F(x2)也是凸函數(shù)。

3)若F(x1)、F(x2)為凸函數(shù)，則αF(x1)+βF(x2)也是凸函數(shù)。三、凸函數(shù)的判別法：海賽矩陣半正定四、局部極小點(diǎn)與全局極小點(diǎn)包括無約束優(yōu)化與約束優(yōu)化問題在內(nèi)，用優(yōu)化方法所求出的點(diǎn)一般都是局部極小點(diǎn)，稱為局部最優(yōu)點(diǎn)；而我們所需要的是整體極小點(diǎn)，稱為全局最優(yōu)點(diǎn)。2.5關(guān)于優(yōu)化方法中搜尋方向的理論基礎(chǔ)對(duì)任何一個(gè)優(yōu)化方法的研究都離不開初始點(diǎn)x(0)的選取、搜尋方向S的確定以及步長a的確定?；蚍Q初始點(diǎn)x(0)、搜尋方向S以及步長a為優(yōu)化方法的三要素。而尤以搜尋方向S為關(guān)鍵,它是優(yōu)化方法特性以及優(yōu)劣的根本標(biāo)志。不同的優(yōu)化方法取不同的方向S，它是矢量，在n維優(yōu)化方法中,S=[S1S2

…Sn]。以下說明產(chǎn)生搜尋方向的數(shù)學(xué)理論基礎(chǔ)。

由目標(biāo)函數(shù)的等值線上可大致的看出函數(shù)的變化情況，而三維以上的超等值面是不能畫出來的。為了確切表達(dá)函數(shù)在某一點(diǎn)的變化形態(tài)則要用微分的辦法具體分析。一、方向?qū)?shù)導(dǎo)數(shù)是描寫函數(shù)變化率的一個(gè)量。設(shè)有連續(xù)可微的n維目標(biāo)函數(shù)F（x）F（x）在點(diǎn)的一階偏導(dǎo)數(shù)為，……，它們分別表示函數(shù)F（x）在點(diǎn)沿各座標(biāo)軸方向的變化率。2.5.1函數(shù)的最速下降方向以二維函數(shù)F（x）為例，見圖。從點(diǎn)，沿某一方向（與ox1，ox2軸夾角分別為，）前進(jìn)到點(diǎn)其增量

其模長函數(shù)F（x）在點(diǎn)沿S方向的方向?qū)?shù)為

或記為方向?qū)?shù)表示函數(shù)F（x）在點(diǎn)沿S方向的變化率。圖中，過o，

兩點(diǎn)連線所豎立的垂直平面與函數(shù)F（x）曲面交線mm，該曲線在k點(diǎn)的斜率即為函數(shù)F（x）沿S方向的導(dǎo)數(shù)。沿S方向的導(dǎo)數(shù)為n維函數(shù)F（x）在點(diǎn)……+式中，為方向S和各座標(biāo)軸的夾角。稱cos，cos，……，cos為矢量S的方向余鉉。上式可簡寫為或……⑴……為函數(shù)F（x）在點(diǎn)的梯度，記作gradF（），矢量的模長為簡記為定義矢量：⑵是方向S的單位矢量，其模長為將方向?qū)?shù)式寫為用記號(hào)＜，S＞表示矢量

與S之間的夾角，則表示的方向?qū)?shù)又可寫為

……二、函數(shù)的最速下降方向函數(shù)F（x）在點(diǎn)變化率的值取決于方向S，不同方向變化率大小不同-1≤cos＜,S＞≤1,當(dāng)方向S與梯度矢量方向一致時(shí)，方向?qū)?shù)達(dá)到最大值，即函數(shù)的變化率最大，其值為梯度的模長梯度優(yōu)化設(shè)計(jì)的幾個(gè)重要特征

梯度是在設(shè)計(jì)空間里的一個(gè)矢量。該矢量的方向是指矢量的最速上升方向，即在梯度方向函數(shù)的變化率最大

函數(shù)在某點(diǎn)的梯度矢量指出了該點(diǎn)極小鄰域內(nèi)函數(shù)的最速上升方向，因而只有局部性。函數(shù)在其定義域范圍內(nèi)的各點(diǎn)都對(duì)應(yīng)著一個(gè)確定的梯度，即不同點(diǎn)x的最速上升方向不同

函數(shù)最速下降方向，在優(yōu)化設(shè)計(jì)理論中占有重要地位。函數(shù)負(fù)梯度-必為函數(shù)最速下降方向，不同設(shè)計(jì)點(diǎn)函數(shù)F（x）具有各自的最速下降方向

函數(shù)F（x）在點(diǎn)的梯度矢量是函數(shù)等值線（面）在該點(diǎn)的法矢量以二維函數(shù)為例，如圖取函數(shù)值為Fk及Fk+ΔF，等值線為x1ox2平面上相對(duì)應(yīng)的兩條曲線過等值線上點(diǎn)，沿S方向的方向?qū)?shù)為對(duì)于上述兩條等值線，函數(shù)的增量為定ΔF，而過點(diǎn)的最大方向?qū)?shù)必沿著等值線間距離最短的方向，既沿著||ΔS||最小的方向，必為過點(diǎn)等值線的法線方向2.5.2共軛方向

共軛方向是指若干個(gè)方向矢量組成的方向組，各方向具有某種共同的性質(zhì)，他們之間存在著特定的關(guān)系。一、共軛方向的基本概念首先以二元二次函數(shù)為例予以說明共軛方向概念，設(shè)函數(shù)式中2*2階對(duì)稱正定矩陣函數(shù)F（x）的梯度為▽F（x）=Ax+B由于函數(shù)F（x）中的A矩陣對(duì)稱正定，所以等值線為一組橢圓，如右圖

按任意給定的方向S1，做F（x）=F1與F（x）=F2兩條等值切線，兩切線互為平行，切點(diǎn)分別為，。連接兩切點(diǎn)構(gòu)成新的矢量

函數(shù)F（x）在兩點(diǎn)處的梯度分別為將上兩式相減，得

按梯度的特性，梯度是等值線的法矢量，所以，點(diǎn)的梯度必須與矢量S1相垂直，因正交矢量點(diǎn)積為0，故有：或?qū)⑹舰賻肷鲜?，有……?/p>

綜上所述，兩個(gè)二維矢量S1，S2，對(duì)于2×2階對(duì)稱正定矩陣A，如能滿足式②，稱矢量S1與S2對(duì)A共軛------①

推廣到n維設(shè)計(jì)空間，若有兩個(gè)n維矢量S1、S2，對(duì)n×n階對(duì)稱正定矩陣A能滿足：稱n維空間矢量S1，S2對(duì)A共軛，記作共軛矢量代表的方向稱為共軛方向在兩個(gè)矢量相共軛的基礎(chǔ)上，定義共軛矢量如下：

設(shè)A為n×n階實(shí)對(duì)稱矩陣，有一組非0的n維矢量S1，S2……，Sq，若滿足i≠j則稱矢量系Si（i=1，2……q≤n）對(duì)于矩陣A共軛二、共軛矩陣的幾個(gè)性質(zhì)

共軛矢量之所以引起優(yōu)化研究者的重視，因?yàn)樗哪承┬再|(zhì)對(duì)提高優(yōu)化方法的收斂速率極為有效。⑴矢量S1與S2正交關(guān)系，是矢量S1與S2對(duì)A共軛的特殊情形對(duì)于式②，如果矩陣A是單位矩陣E時(shí)，則矢量S1與S2的共軛就是矢量的正交即為也可以說，矢量共軛的概念實(shí)際上就是正交概念的廣義化。在某一α空間里對(duì)矩陣A共軛的兩矢量，可通過尺度變換成為另一β空間里的兩個(gè)正交矢量。對(duì)于由k個(gè)非零矢量S1，S2……Sk組成的矢量系{Si}，若存在著i≠j稱該矢量為正交矢量系顯然，在n維設(shè)計(jì)空間里，單位坐標(biāo)矢量系：e1，e2……en為正交矢量系⑵若矢量系S1，S2……Sn對(duì)于對(duì)稱正定矩陣A共軛，則它必為線性獨(dú)立（線性無關(guān)）矢量系。對(duì)于n維設(shè)計(jì)空間而言，線性獨(dú)立矢量系中的矢量個(gè)數(shù)不能超過維數(shù)n，即共軛矢量系中矢量個(gè)數(shù)最多等于n。對(duì)于矢量系的線性獨(dú)立問題簡述如下:

設(shè)有非零矢量系：S1，S2……Sn，若存在一組不全為零的實(shí)數(shù)α1，α

2，……α

n，使成立，則該矢量系稱為線性相關(guān)矢量系。

如果只有在α

1=α

2=……=α

n=0，即系數(shù)全部為零才有上式成立，則該矢量系為線性獨(dú)立矢量系

③

在③式線性相關(guān)矢量系中，若某矢量Si的系數(shù)α

i≠0，則可寫成可知，線性相關(guān)矢量系中Si可表示為其余矢量的線性組合。

任意兩個(gè)矢量S1與S2，如果它們是共線的，則矢量S1與S2必線性相關(guān)。因?yàn)閷?duì)于共線兩矢量S1與S2，一定可以找到系數(shù)α

1與α

2，使

在二維平面里，由三個(gè)及三個(gè)以上的矢量組成的矢量系，也必定是線性相關(guān)的。例如二維平面的三個(gè)矢量取一組系數(shù)α

1=1，α

2=1/4，α

3=1，使矢量系{Si}（i=1，2，3）是線性相關(guān)的，由下圖說明

將S3用S1與S2的線性組合表示為

可見，同一平面上任意三個(gè)矢量必定線性相關(guān)。

在三維空間里的三個(gè)矢量，只要他們不共面，則必線性獨(dú)立；若三維空間中有任意四個(gè)矢量，則矢量系必線性相關(guān)。可以得出結(jié)論：

當(dāng)矢量系中矢量的數(shù)目超過設(shè)計(jì)空間的維數(shù)時(shí)，矢量系必線性相關(guān)非零矢量構(gòu)成的正交矢量系必線性獨(dú)立。正交矢量系中矢量的數(shù)目不能超過矢量系所在的空間的維數(shù)三、關(guān)于二次收斂性問題

對(duì)于二元二次正定函數(shù)F（x），取一組共軛矢量S1與S2，其中矢量之一通過等值曲線中心。

二元二次正定目標(biāo)函數(shù)的等值線為一組同心的橢圓，其中心是函數(shù)的極小點(diǎn)。按共軛方向的性質(zhì)：任意做兩條平行線，與橢圓組中的兩橢圓切于

點(diǎn)，該兩點(diǎn)必通過橢圓的中心；或者說，過橢圓中心做任意直線與任意兩個(gè)橢圓相交，通過交點(diǎn)作橢圓切線必互相平行對(duì)以上結(jié)論的證明：

為簡化，設(shè)目標(biāo)函數(shù)為二次齊次函數(shù)，等值線中心在坐標(biāo)原點(diǎn)。展開

函數(shù)值分別為d1，d2的兩條等值線Ⅰ，Ⅱ，方程為：等值線任意點(diǎn)切線斜率為，可對(duì)上式求導(dǎo)而得，則切線斜率為過點(diǎn)橢圓切線斜率分別記為K1，k2，則有：當(dāng)所引的兩條直線平行，且切于等值線（橢圓)于點(diǎn),,則該兩條切線斜率相等，k1=k2，即④分別將切點(diǎn)與坐標(biāo)原點(diǎn)相連接，兩直線ox1，ox2的斜率分別記為如果有，說明兩點(diǎn)連線必通過坐標(biāo)原點(diǎn)o（橢圓中心）將式④寫成或?qū)⑸鲜秸归_整理后得由于函數(shù)F（x1，x2）是二次齊次函數(shù)，圖形為橢圓，所以，則必有。

由此證明得出，點(diǎn)，連線必定通過橢圓中心點(diǎn)o。

若在切于橢圓的直線上取方向S1，連接兩個(gè)切點(diǎn)，為方向S2，則S1，S2為共軛方向。如果從某任意初始點(diǎn)出發(fā)，依次沿方向S1，S2做兩次一維搜索，即可達(dá)到橢圓中心——此函數(shù)F（x）的極小點(diǎn)。

對(duì)于一般的二元二次正定函數(shù)，按其共軛方向進(jìn)行兩次搜索也必定達(dá)到函數(shù)的極小點(diǎn)。此情況目標(biāo)函數(shù)等值線仍是橢圓，但其中心不在坐標(biāo)原點(diǎn)。

二次收斂性是指一種算法，如果對(duì)于二次正定函數(shù)，從理論上只要進(jìn)行有限次一維搜索，就可以達(dá)到理論極小點(diǎn)，把這種算法稱為具有二階收斂性（二次收斂性）或有限步收斂法。

對(duì)于一般的n元二次正定函數(shù)F（x），依次按共軛矢量系（S1，S2……Sn）中各矢量方向進(jìn)行n維一次搜索，就可達(dá)等值線（橢圓）中心——理論極小值點(diǎn)。例題2：設(shè)二維目標(biāo)函數(shù)，給定方向S1=e1，初始點(diǎn)。求與S1相共軛的S2，并求函數(shù)的極小點(diǎn)。解：⑴第一個(gè)搜索方向。⑵函數(shù)的海塞矩陣對(duì)稱正定?？芍瘮?shù)F（x）為二次正定函數(shù)，如果按共軛方向S1，S2，進(jìn)行兩次一維搜索就達(dá)到目標(biāo)函數(shù)的極小點(diǎn)x*。⑶從點(diǎn)沿S1方向求極小點(diǎn)，即沿S1方向則⑷任取初始點(diǎn)，沿S1方向一維搜索求得該方向極小點(diǎn)[按⑶的做法]⑸求與S1相共軛的方向S2核驗(yàn)計(jì)算矢量S1與S2為對(duì)A矩陣共軛⑹從點(diǎn)出發(fā)，沿S2方向作一維搜索，

得極小點(diǎn)如右圖所示。一維優(yōu)化方法初始搜索區(qū)間的確定一維搜索的最優(yōu)化方法

1、格點(diǎn)法

2、黃金分割法

3、二次插值法

教學(xué)要求：

1、掌握初始搜索區(qū)間的確定方法

2、掌握黃金分割法

3、掌握二次插值法一維搜索方法概述

在優(yōu)化設(shè)計(jì)的迭代運(yùn)算中，在搜索方向s(k)上尋求最優(yōu)步長

(k)的方法稱一維搜索法。實(shí)際上一維搜索法就是一元函數(shù)極小化的數(shù)值迭代算法，其求解過程稱為一維搜索。一維搜索法是非線性優(yōu)化方法的基本算法，多元函數(shù)的迭代算法都可以歸結(jié)為在一系列逐步產(chǎn)生的下降方向上的一維搜索。例如：下圖所示的二維優(yōu)化的例子。二維優(yōu)化問題的一維搜索方向s(k)是由具體的優(yōu)化方法決定的，迭代公式

x(k+1)=x(k)+

(k)s(k)

因此，二維優(yōu)化問題minF(x1,x2)就可以表示為一維優(yōu)化問題minf()x2x1o

(k)S(k)S(k)x(k+1)x(k)x*F(x(k))F(x(k+1))二維優(yōu)化問題中的一維搜索3.1初始搜索區(qū)間的確定

在一維搜索時(shí)，需要確定一個(gè)搜索區(qū)間[a,b]，此區(qū)間必須包含函數(shù)的極小點(diǎn)x*，因此搜索區(qū)間必須是單峰區(qū)間，即該區(qū)間內(nèi)的函數(shù)值呈現(xiàn)“高-低-高”的趨勢(shì)。如圖所示，通過將搜索區(qū)間[a,b]逐漸縮小，直至足夠小，就可以得到近似最優(yōu)點(diǎn)。

在一維搜索時(shí)，需要確定一個(gè)搜索區(qū)間[a,b]，此區(qū)間必須包含函數(shù)的極小點(diǎn)x*，因此搜索區(qū)間必須是單峰區(qū)間，即該區(qū)間內(nèi)的函數(shù)值呈現(xiàn)“高-低-高”的趨勢(shì)。如圖所示，通過將搜索區(qū)間[a,b]逐漸縮小，直至足夠小，就可以得到近似最優(yōu)點(diǎn)。f(x)f(x)xxaax*x*bb確定初始搜索區(qū)間的進(jìn)退法一、試探搜索極小點(diǎn)位置

設(shè)函數(shù)為y=f(x),給定初始點(diǎn)為x1

，選定的初始步長為h0。

由初始點(diǎn)x1沿x軸正向取x2點(diǎn)，x2=x1+h0，計(jì)算x1、x2的函數(shù)值y1、y2，比較y1、y2的大小，則極小點(diǎn)的位置有如圖所示兩種情況

1、若y2<y1，則極小點(diǎn)位于x1點(diǎn)右方，應(yīng)繼續(xù)前進(jìn)搜索。

2、若y2>y1，則極小點(diǎn)位于x1點(diǎn)左方，應(yīng)反向后退搜索。確定初始搜索區(qū)間的進(jìn)退法x1x1x2x2x3x3h02h0h02h0前進(jìn)搜索后退搜索注意：x1x2互換后再取x3二、前進(jìn)搜索

令h

h0，并使步長加倍h2h，取得前進(jìn)方向的x3點(diǎn)，x3

x2+h=x2+2h0，其函數(shù)值y3與y2比較有如下情況：

1、若y2<y3，則有y1>

y2<y3，此時(shí)函數(shù)f(x)在[x1,x3]必有極小點(diǎn)，故令a

x1，b

x3，從而構(gòu)成搜索區(qū)間[a,b]

2、若y2>y3，則繼續(xù)前進(jìn)搜索，各點(diǎn)變換如下：

x1

x2，y1

y2

x2

x3，y2

y3

然后步長加倍，取新點(diǎn)x3，重復(fù)上述比較y2與y3的大小，直至出現(xiàn)y1>

y2<y3時(shí)，令a

x1，b

x3，從而構(gòu)成搜索區(qū)間[a,b]三、后退搜索

令h-h0，并將x1與

x2對(duì)調(diào)，使步長加倍h2h，取得x3點(diǎn)，x3

x2+h，其函數(shù)值y3與y2比較有如下情況：

1、若y2<y3，則有y1>

y2<y3，此時(shí)函數(shù)f(x)在[x3,x1]必有極小點(diǎn)，故令a

x3，b

x1，從而構(gòu)成搜索區(qū)間[a,b]

2、若y2>y3，則繼續(xù)后退搜索，各點(diǎn)變換如下：

x1

x2，y1

y2

x2

x3，y2

y3

然后步長加倍，取新點(diǎn)x3，重復(fù)上述比較y2與y3的大小，直至出現(xiàn)y1>

y2<y3時(shí)，令a

x3，b

x1，從而構(gòu)成搜索區(qū)間[a,b]四、進(jìn)退法確定搜索區(qū)間的流程圖例題3.1：試用進(jìn)退法確定函數(shù)

的一維優(yōu)化搜索區(qū)間[a，b]，設(shè)初始點(diǎn)x1=0，初始步長h0=1。解：計(jì)算過程如下:h←h0=1x2←x1+h=1y1=f(x1)=9,y2=f(x2)=4

由于用y2＜y1，作前進(jìn)搜索：h←2h=2x3←x2+h=3y3=f(x3)=0

比較y2，y3有y2＞y3，再做前進(jìn)搜索x1←x2=1,y1←y2=4x2←x3=3,y2←y3=0h←2h=4x3←x2+h=7,y3=F(x3)=16在比較y2，y3有y2＜y3，則取a←x1=1，b←x3=7搜索區(qū)間a，b為[1，7]搜索過程見下圖3.2一維搜索的最優(yōu)化方法

在確定了搜索區(qū)間以后，一維優(yōu)化的任務(wù)是采用某種方法將此區(qū)間逐步縮小，在滿足收斂精度或迭代精度的情況下，使其達(dá)到包含極小點(diǎn)的一個(gè)很小的鄰域，以取得一個(gè)近似的最優(yōu)點(diǎn)。

一維優(yōu)化的方法有如下幾種：

1、格點(diǎn)法

2、黃金分割法3、二次插值法3.2.1格點(diǎn)法一、格點(diǎn)法的原理

設(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。比較其大小，取最小者ym=min{yk,k=1,2,…,n}，則在區(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)法

新區(qū)間y1ym-1ymym+1ynx1axm-1xmxm+1xnb格點(diǎn)法的區(qū)間縮短格點(diǎn)法流程圖+--++-例題3.2：用格點(diǎn)法求一維目標(biāo)函數(shù)的最優(yōu)解。給定搜索區(qū)間[a，b]為[1，2.2]，迭代精度ε=0.2，內(nèi)分點(diǎn)數(shù)n=4。解：計(jì)算區(qū)間端點(diǎn)的函數(shù)值f(a)=2f(b)=2.96由上式確定四個(gè)內(nèi)分點(diǎn)的位置，并計(jì)算其函數(shù)值，計(jì)算結(jié)果見下頁表。其中最小的函數(shù)值為：對(duì)應(yīng)的點(diǎn)區(qū)間縮短次數(shù)xkykxmabb-a第一次1.241.481.721.961.27041.00161.19361.8461.481.241.720.48第二次1.3361.4321.5281.6241.1075841.0184961.0031361.0615041.5281.4321.6240.192新區(qū)間的端點(diǎn)為：新區(qū)間的長度為：，不滿足精度要求。再做第二次區(qū)間縮短后，得到區(qū)間端點(diǎn)為：新區(qū)間長度，滿足迭代精度。最優(yōu)解為：

3.2.2黃金分割法

黃金分割法適用于[a,b]區(qū)間上的任何單峰函數(shù)求極小值問題。對(duì)函數(shù)除要求單峰外不作其它要求，甚至可以不連續(xù)。因此，這種方法的適應(yīng)面相當(dāng)廣。

一、黃金分割法的原理

在搜索區(qū)間[a,b]內(nèi)適當(dāng)插入兩點(diǎn)x1,x2，x1<x2,且在區(qū)間內(nèi)對(duì)稱位置，計(jì)算其函數(shù)值。

y1=f(x1)y2=f(x2) 1)若y1<y2則極小點(diǎn)必在區(qū)間[a,x2]內(nèi)，令b=x2，新區(qū)間為[a，x2] 2)若y1≥<y2則極小點(diǎn)必在區(qū)間[x1,b]內(nèi)，令a=x1，新區(qū)間為[x1，b]

經(jīng)過函數(shù)值比較，區(qū)間縮短一次。新區(qū)間只保留x1，x2中的一個(gè)。黃金分割法內(nèi)分點(diǎn)選區(qū)的原則之一是要對(duì)稱的、并采取每次區(qū)間縮短率都是相等的。

設(shè)原區(qū)間長度為l如圖3.8所示，保留區(qū)間長度為

l，區(qū)間縮短率為

。進(jìn)行第二次縮短時(shí)，新點(diǎn)為x3,設(shè)y1>f(x3)則新區(qū)間為[a,x1]為保持相同的區(qū)間縮短率，應(yīng)有（1-）/=

故：1-

=

2

2+

-1=0

由此可得：

=0.618

黃金分割法可使相鄰兩次搜索區(qū)間都具有相同的縮短率0.618。 x1=a+0.382(b-a) x2=a+0.618(b-a)二、黃金分割法的搜索過程

1、給出初始搜索區(qū)間[a,b]及收斂精度

。

2、按坐標(biāo)點(diǎn)計(jì)算公式計(jì)算，并計(jì)算相應(yīng)的函數(shù)值

3、縮短搜索區(qū)間

4、檢查是否滿足收斂條件

5、若滿足收斂條件，則取最后兩點(diǎn)的平均值作為極小點(diǎn)的近似解。三、黃金分割法流程圖+-+-例題3.3試用黃金分割法求目標(biāo)函數(shù)的最優(yōu)解。給定初始區(qū)間[1，7]，收斂精度ε=0.4。解：第一次區(qū)間縮短計(jì)算過程：計(jì)算兩內(nèi)點(diǎn)及對(duì)應(yīng)函數(shù)值：X1=a+0.382(b-a)=3.292y1=f(x1)=0.085264X2=a+0.618(b-a)=4.708y2=f(x2)=2.917264作數(shù)值比較，可見y1<y2,再做置換：用終止準(zhǔn)則判斷為第二次區(qū)間縮短做準(zhǔn)備，做置換：x2←x1=3.292，y2←y1=0.085264各次縮短區(qū)間的計(jì)算數(shù)據(jù)見下頁表。第六次區(qū)間縮短的端點(diǎn)滿足精度要求，終止計(jì)算。取最優(yōu)解為區(qū)間縮短次數(shù)abx1x2y1y2原區(qū)間123456112.4164562.4164562.4164562.7509172.75091774.7084.7083.8326303.2923.2923.0853053.2922.4164563.2922.9574342.7509172.9574342.8786514.7083.2923.8326303.2922.9574343.0853052.9574340.0852640.34052400852640.0018120.0620440.0018120.0147252.9172640.0852640.6932730.0852640.0018120.0072770.001812黃金分割法例題計(jì)算數(shù)據(jù)3.3.3二次插值法一、插值法概念

假定我們給定的問題是在某一確定區(qū)間內(nèi)尋求函數(shù)的極小點(diǎn)的位置，但是沒有函數(shù)表達(dá)式，只有若干試驗(yàn)點(diǎn)處的函數(shù)值。我們可以根據(jù)這些函數(shù)值，構(gòu)成一個(gè)與原目標(biāo)函數(shù)相接近的低次插值多項(xiàng)式，用該多項(xiàng)式的最優(yōu)解作為原函數(shù)最優(yōu)解的近似解，這種方法是用低次插值多項(xiàng)式逐步逼近原目標(biāo)函數(shù)的極小點(diǎn)的近似求解方法，稱為插值方法或函數(shù)逼近法。二、插值法與試探法的異同點(diǎn)

相同點(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ù)值近似分布的極小點(diǎn)確定的。

試探法僅僅利用了試驗(yàn)點(diǎn)函數(shù)值進(jìn)行大小的比較，而插值法還要利用函數(shù)值本身或其導(dǎo)數(shù)信息。所以，當(dāng)函數(shù)具有較好的解析性質(zhì)時(shí)，插值方法比試探方法效果更好。三、二次插值法的概念利用原目標(biāo)函數(shù)上的三個(gè)插值點(diǎn)，構(gòu)成一個(gè)二次插值多項(xiàng)式，用該多項(xiàng)式的最優(yōu)解作為原函數(shù)最優(yōu)解的近似解，逐步逼近原目標(biāo)函數(shù)的極小點(diǎn)，稱為二次插值方法或拋物線法。四、二次插值函數(shù)的構(gòu)成

設(shè)一維目標(biāo)函數(shù)的搜索區(qū)間為[a,b]，取三點(diǎn)x1、x2、x3，其中x1、x3取區(qū)間的端點(diǎn)，即

x1

a，

x3

b

而x2為區(qū)間內(nèi)的一個(gè)點(diǎn)，開始可以取區(qū)間的中點(diǎn)，即

x2=0.5(x1+x3)

計(jì)算函數(shù)值f

1=f(x1)、f

2=

f(x2)、f

3=f(x3)

過函數(shù)曲線上的三點(diǎn)P1(x1,f

1)、P2(x2,f2)、P3(x3,f

3)作二次插值多項(xiàng)式

p(x)=Ax2+Bx+C

它應(yīng)滿足條件

p(x1)=Ax12+Bx1+C1=f

1

p(x2)=Ax22+Bx2+C=f

2

p(x3)=Ax32+Bx3+C=f

3

解方程組，得待定系數(shù)A、B、C分別為

于是函數(shù)p(x)就是一個(gè)確定的二次多項(xiàng)式，稱二次插值函數(shù)如圖所示，虛線部分即為二次插值函數(shù)

令插值函數(shù)p(x)的一階導(dǎo)數(shù)為0，即

p′(x)=2ax+b=0

得p(x)極小點(diǎn)為xp*=

B/2A

代入A、B得

令得注意：若c2=0，則

即

說明三個(gè)插值點(diǎn)位于同一條直線上，因此說明區(qū)間已經(jīng)很小，插值點(diǎn)非常接近，故可將x2、f2輸出作為最優(yōu)解。五、區(qū)間的縮短為求得滿足收斂精度要求的最優(yōu)點(diǎn)，往往需要多次進(jìn)行插值計(jì)算，搜索區(qū)間不斷縮短，使xp*不斷逼近原函數(shù)的極小點(diǎn)x*。

第一次區(qū)間縮短的方法是，計(jì)算xp*點(diǎn)的函數(shù)值fp*，比較fp*與f2，取其中較小者所對(duì)應(yīng)的點(diǎn)作為新的x2，以此點(diǎn)的左右兩鄰點(diǎn)作為新的x1和x3，得到縮短后的新區(qū)間[x1，x3]，如圖所示。新區(qū)間x1=ax2x3=bx*xP*x1x2x3以后，根據(jù)fp*相對(duì)于x2的位置，并比較fp*與f2，區(qū)間的縮短可以分為以下四種情況。x1x2x3xP*f2fP*x1x1x1x2x2x2xP*xP*xP*x3x3x3f2f2f2fP*fP*fP*bacd入口xp*>x2?f2>fP*?f2<fP*?x1

xp*f1

fP*x3

x2f3

f2x2

xp*f2

fP*x1

x2f1

f2x2

xp*f2

fP*x3

xp*f3

fP*出口YYYNNNabcd區(qū)間縮短流程圖六、終止準(zhǔn)則

當(dāng)滿足給定精度時(shí)，計(jì)算終止，并令

x*

xP*(k),f*

f(x*)七、二次插值算法流程圖+----+++例題3.4

試用二次插值法求函數(shù)的最優(yōu)解，初始區(qū)間為[1，7]，精度ε=0.01解：(1)初始插值節(jié)點(diǎn)x1=a=1,f1=f(x1)=4x2=0.5(a+b)=4,f2=f(x2)=1x3=b=7,f3=f(x3)=16(2)計(jì)算差值函數(shù)的極小點(diǎn)與極小值(3)縮短區(qū)間因有，故有x1=1,f1=4x3←x2=4,f3=1x2←=3,f2=0(4)重復(fù)步驟(2)c1=-1,c2=1

(5)檢查終止條件獲得最優(yōu)解例題3.5

用二次差值法求非二次函數(shù)的最優(yōu)解。初始區(qū)間端點(diǎn)為a=-0.5,b=2.5精度要求ε=0.005解：(1)初始差值結(jié)點(diǎn)x1=a=-0.5,f1=f(x1)=-0.851279x2=0.5(a+b)=1,f2=f(x2)=-2.610944x3=b=2.5,f3=f(x3)=15.615452(2)計(jì)算與

c1=5.488910,c2=4.441347(3)縮短區(qū)間因有，故取x1=-0.5,f1=-0.851279x2=0.382067,f2=-20927209x3=1,f3=-2.610944(4)對(duì)新區(qū)間重復(fù)步驟二c1=-1.17311,c2=1.910196(5)檢查終止條件未滿足終止條件，返回步驟（3）計(jì)算次數(shù)12345X1X2X3F1F2F3C1C2X*pF*p-0.51.02.5-0.851279-2.61094415.6154525.4889104.4413470.382067-2.927209-0.50.3820671.0-0.851279-2.927209-2.610944-1.173111.9101960.557065-3.0404500.1749980.3820670.5570651.0-2.927209-3.040450-2.6109440.5118112.6164330.593226-3.0465340.0361610.5570650.5932261.0-3.040450-3.046534-2.6109440.9696822.7974490.605217-3.0471450.0119910.5932260.6052171.0-3.046534-3.047145-2.6109441.0708402.8415480.608188-3.0471880.002971計(jì)算結(jié)果表經(jīng)五次差值計(jì)算后，得得最優(yōu)解//搜索區(qū)間的確定voidfind_ab(doublex0,doubleh0,double*a,double*b){ doublex1,y1,x2,y2,x3,y3,h; h=h0; x1=x0;y1=f(x1); x2=x1+h;y2=f(x2); if(y2>y1){ h=-h0; x3=x1;x1=x2;x2=x3;y3=y1;y1=y2;y2=y3; } for(;;){ h=2*h; x3=x2+h; y3=f(x3); if(y2<y3)break; x1=x2;y1=y2; x2=x3;y2=y3; } if(h<0){ *a=x3;*b=x1; }else{ *a=x1;*b=x3; }}一維優(yōu)化方法的比較格點(diǎn)法的結(jié)構(gòu)及程序很簡單,但效率偏低:黃金分割法的結(jié)構(gòu)簡單，使用可靠，但效率也不高，格點(diǎn)法和黃金分割法適于低維優(yōu)化問題中的一維搜索。二次插值法在同樣搜索次數(shù)下，其計(jì)算精度更高，但程序略復(fù)雜，可靠性差些，對(duì)高維數(shù)的優(yōu)化問題更適宜，經(jīng)過某些技術(shù)處理，方法的可靠度可大為提高。無約束優(yōu)化方法坐標(biāo)輪換法鮑威爾法梯度法牛頓法DFP變尺度法BFGS變尺度法無約束優(yōu)化方法的評(píng)價(jià)準(zhǔn)則及選用無約束優(yōu)化方法是優(yōu)化技術(shù)中基本的也是非常重要的內(nèi)容。無約束優(yōu)化問題的數(shù)學(xué)模型

求上述問題最優(yōu)解（x*,F*）的方法，稱為無約束優(yōu)化方法無約束優(yōu)化方法，不僅可以直接求無約束優(yōu)化設(shè)計(jì)問題的最優(yōu)解，而且通過對(duì)無約束優(yōu)化方法的研究給約束優(yōu)化方法建立明確的概念、提供良好的基礎(chǔ)·某些優(yōu)化設(shè)計(jì)方法就是先把約束優(yōu)化設(shè)計(jì)問題轉(zhuǎn)化為無約束問題后，再直接用無約束優(yōu)化方法求解。

無約束優(yōu)化理論研究開展得較早，構(gòu)成的優(yōu)化方法巳很多，也比較成熟，新的方法仍在陸續(xù)出現(xiàn)。本章的內(nèi)容與目的是討論幾個(gè)常用無約束優(yōu)化方法的基本思想、方法構(gòu)成、迭代步驟以及終止準(zhǔn)則等方面問題。

在n維無約束優(yōu)化方法的算法中，用函數(shù)的一階、二價(jià)導(dǎo)數(shù)進(jìn)行求解的算法，稱為解析法;無約束優(yōu)化方法總體分成兩大類型:解析法或稱間接法、直接搜索法或簡稱直接法；對(duì)于n維優(yōu)化問題，如果只利用函數(shù)值求最優(yōu)值的解法，稱為直接搜索法；解析法的收斂速率較高，直接法的可靠性較高。本章介紹的坐標(biāo)輪換法和鮑威爾法屬于直接法；梯度法、共軛梯度法、牛頓法和變尺度法屬于解析法無約束優(yōu)化方法算法的基本過程是:

從選定的某初始點(diǎn)x(k)出發(fā)，沿著以一定規(guī)律產(chǎn)生的搜索方向S(k),取適當(dāng)?shù)牟介La(k),逐次搜尋函數(shù)值下降的新迭代點(diǎn)x(k+1),使之逐步逼近最優(yōu)點(diǎn)x*?？梢园殉跏键c(diǎn)x(k)

、搜索方向S(k)

、迭代步長a(k)

稱為優(yōu)化方法算法的三要素。其中以搜索方向S(k)更為突出和重要，它從根本上決定著一個(gè)算法的成敗、收斂速率的快慢等。所以，一個(gè)算法的搜索方向成為該優(yōu)化方法的基本標(biāo)志，分析、確定搜索方向S(k)是研究優(yōu)化方法的最根本的任務(wù)之一。坐標(biāo)輪換法

坐標(biāo)輪換法屬于直接法，既可以用于無約束優(yōu)化問題的求解，又可以經(jīng)過適當(dāng)處理用于約束優(yōu)化問題求解。坐標(biāo)輪換法是每次搜索只允許一個(gè)變量變化，其余變量保持不變，即沿坐標(biāo)方向輪流進(jìn)行搜索的尋優(yōu)方法。它把多變量的優(yōu)化問題輪流地轉(zhuǎn)化成單變量（其余變量視為常量）的優(yōu)化問題，因此又稱這種方法為變量輪換法。此種方法只需目標(biāo)函數(shù)的數(shù)值信息而不需要目標(biāo)函數(shù)的導(dǎo)數(shù)。一、坐標(biāo)輪換法的迭代過程

如圖，以二次函數(shù)為例。

任取一初始點(diǎn)x(0)作為第一輪的始點(diǎn)x0(1),先沿第一坐標(biāo)軸的方向e1作一維搜索，用一維優(yōu)化方法確定最優(yōu)步長

1(1)

，得第一輪的第一個(gè)迭代點(diǎn)

x1(1)

=x0(1)

+

1(1)

e1，然后以

x1(1)為新起點(diǎn)，沿第二坐標(biāo)軸的方向e2作一維搜索，確定步長

2(1)

，得第一輪的第二個(gè)迭代點(diǎn)

x2(1)

=x1(1)

+

1(1)

e2

第二輪迭代，需要

x0(2)

x2(1)

x1(2)

=

x0(2)

+

1(2)

e1x2(2)

=x1(2)

+

2(2)

e2

依次類推，不斷迭代，目標(biāo)函數(shù)值不斷下降，最后逼近該目標(biāo)函數(shù)的最優(yōu)點(diǎn)。

二、終止準(zhǔn)則可以采用點(diǎn)距準(zhǔn)則

注意：若采用點(diǎn)距準(zhǔn)則或函數(shù)值準(zhǔn)則，其中采用的點(diǎn)應(yīng)該是一輪迭代的始點(diǎn)和終點(diǎn)，而不是某搜索方向的前后迭代點(diǎn)。坐標(biāo)輪換法的計(jì)算步驟⑴任選初始點(diǎn)作為第一輪的起點(diǎn)，置n個(gè)坐標(biāo)軸方向矢量為單位坐標(biāo)矢量：⑵按照下面迭代公式進(jìn)行迭代計(jì)算k為迭代輪數(shù)的序號(hào)，取k=1，2，……；i為該輪中一維搜索的序號(hào)，取i=1，2，……n步長α一般通過一維優(yōu)化方法求出其最優(yōu)步長。⑶按下式判斷是否中止迭代如滿足，迭代中止，并輸出最優(yōu)解最優(yōu)解否則，令k←k+1返回步驟（2）例題4.1

用坐標(biāo)輪換法求目標(biāo)函數(shù)

的無約束最優(yōu)解。給定初始點(diǎn)，精度要求ε=0.1解：做第一輪迭代計(jì)算沿e1方向進(jìn)行一維搜索式中，為第一輪的起始點(diǎn)，取按最優(yōu)步長原則確定最優(yōu)步長α1，即極小化此問題可由某種一維優(yōu)化方法求出α1。這里，我們暫且用微分學(xué)求導(dǎo)解出，令其一階導(dǎo)數(shù)為零以為新起點(diǎn)，沿e2方向一維搜索以最優(yōu)步長原則確定α2，即為極小化對(duì)于第一輪按終止條件檢驗(yàn)繼續(xù)進(jìn)行第2輪迭代計(jì)算，各輪計(jì)算結(jié)果見課本表4.1。計(jì)算5輪后，有故近似優(yōu)化解為坐標(biāo)輪換法的流程圖--++小結(jié)

坐標(biāo)輪換法程序簡單，易于掌握。但是計(jì)算效率比較低，尤其是當(dāng)優(yōu)化問題的維數(shù)較高時(shí)更為嚴(yán)重。一般把此種方法應(yīng)用于維數(shù)小于10的低維優(yōu)化問題。

對(duì)于目標(biāo)函數(shù)存在“脊線”的情況，在脊線的尖點(diǎn)處沒有一個(gè)坐標(biāo)方向可以使函數(shù)值下降，只有在銳角所包含的范圍搜索才可以達(dá)到函數(shù)值下降的目的，故坐標(biāo)輪換法對(duì)此類函數(shù)會(huì)失效。x2x1

脊線鮑威爾方法

鮑威爾方法是直接搜索法中一個(gè)十分有效的算法。該算法是沿著逐步產(chǎn)生的共軛方向進(jìn)行搜索的，因此本質(zhì)上是一種共軛方向法。一、鮑威爾基本算法

如圖所示，以三維二次目標(biāo)函數(shù)的無約束優(yōu)化問題為例。鮑威爾基本算法的搜索過程

鮑威爾基本算法的步驟：

第一環(huán)基本方向組取單位坐標(biāo)矢量系e1、e2、

e3

、…、en，沿這些方向依次作一維搜索，然后將始末兩點(diǎn)相連作為新生方向， Sk=xnk-x0k

再沿新生方向作一維搜索，完成第一環(huán)的迭代。以后每環(huán)的基本方向組是將上環(huán)的第一個(gè)方向淘汰，上環(huán)的新生方向補(bǔ)入本環(huán)的最后而構(gòu)成。

S2kS3k……SnSk

n維目標(biāo)函數(shù)完成n環(huán)的迭代過程稱為一輪。從這一輪的終點(diǎn)出發(fā)沿新生方向搜索所得到的極小點(diǎn)，作為下一輪迭代的始點(diǎn)。這樣就形成了算法的循環(huán)。

鮑威爾基本算法的缺陷：

可能在某一環(huán)迭代中出現(xiàn)基本方向組為線性相關(guān)的矢量系的情況。如第k環(huán)中，產(chǎn)生新的方向：

Sk=xnk-x0k=

1(k)S1(k)+2(k)S2(k)

+???+n(k)Sn(k)

式中，S1(k)、S2(k)

、

???、Sn(k)為第k環(huán)基本方向組矢量，

1(k)

、

2(k)

、???、

n(k)為個(gè)方向的最優(yōu)步長。

若在第k環(huán)的優(yōu)化搜索過程中出現(xiàn)

1(k)=0，則方向Sk表示為S2(k)

、

S3(k)

、???、Sn(k)的線性組合，以后的各次搜索將在降維的空間進(jìn)行，無法得到n維空間的函數(shù)極小值，計(jì)算將失敗。

如圖所示為一個(gè)三維優(yōu)化問題的示例，設(shè)第一環(huán)中

1=0

，則新生方向與e2、e3共面，隨后的各環(huán)方向組中，各矢量必在該平面內(nèi)，使搜索局限于二維空間，不能得到最優(yōu)解。

鮑威爾基本算法的退化x1x2x3

1=0

2e2

3e3S1二、鮑威爾修正算法

在某環(huán)已經(jīng)取得的n+1各方向中，選取n個(gè)線性無關(guān)的并且共軛程度盡可能高的方向作為下一環(huán)的基本方向組

鮑威爾修正算法的搜索方向的構(gòu)造：在第k環(huán)的搜索中，x0k

為初始點(diǎn)，搜索方向?yàn)镾1(k)、S2(k)

、

???、Sn(k)，產(chǎn)生的新方向?yàn)镾k

，此方向的極小點(diǎn)為x(k)。點(diǎn)

xn+1(k)=2xn(k)-x0(k)

，為x0(k)對(duì)xn(k)的映射點(diǎn)。

計(jì)算x0(k)

、

x1(k)

、???、xn(k)

、x(k)、

x

n+1(k)

各點(diǎn)的函數(shù)值，記作：

F1=F(x0(k))

F2=F(xn(k))

F3=F(xn+1(k))=F(xm(k))-F(xm-1(k))

是第k環(huán)方向組中，依次沿各方向搜索函數(shù)值下降最大值，即Sm(k)方向函數(shù)下降最大。(F3)(F2)(F1)影射點(diǎn)函數(shù)下降量△鮑威爾算法的方向淘汰

為了構(gòu)造第k+1環(huán)基本方向組，采用如下判別式：

按照以下兩種情況處理：

1、上式中至少一個(gè)不等式成立，則第k+1環(huán)的基本方向仍用老方向組S1(k)、S2(k)

、

???、Sn(k)。k+1環(huán)的初始點(diǎn)取

x0(k+1)=xn(k)F2<F3x0(k+1)=xn+1(k)F2F3

2、兩式均不成立，則淘汰函數(shù)值下降最大的方向，并用第k環(huán)的新生方向補(bǔ)入k+1環(huán)基本方向組的最后，即k+1環(huán)的方向組為

S1(k)、S2(k)

、???、Sm-1(k)、Sm+1(k)

???、Sn(k)

、Sn+1(k)

。k+1環(huán)的初始點(diǎn)取

x0(k+1)=x(k)

x(K)是第k環(huán)沿Sn+1(K)方向搜索的極小點(diǎn)。鮑威爾算法的終止條件：

||x(K)-x0(k)||三修正算法的迭代步驟及流程圖Powell算法的步驟如下：⑴任選初始迭代點(diǎn)，選定迭代精度ε，取初始基本方向組為單位坐標(biāo)矢量系其中，i=1，2……n（下同）。然后令k=1（環(huán)數(shù)）開始下面的迭代⑵沿諸方向依次進(jìn)行n次一微搜索，確定各步長使得到點(diǎn)陣i=1，2……n構(gòu)成新生方向沿方向進(jìn)行一維搜索求得優(yōu)化步長，得⑶判斷是否滿足迭代終止條件。如滿足則可結(jié)束迭代，最優(yōu)解為停止計(jì)算。否則，繼續(xù)進(jìn)行下步。⑷計(jì)算各迭代點(diǎn)的函數(shù)值，并找出相鄰點(diǎn)函數(shù)值差最大者（1≤m≤n）及與之相對(duì)應(yīng)的兩個(gè)點(diǎn)和，并以表示兩點(diǎn)的連線方向。⑸確定映射點(diǎn)并計(jì)算函數(shù)值檢驗(yàn)鮑威爾條件若至少其中之一成立轉(zhuǎn)下步，否則轉(zhuǎn)步驟⑺⑹置k+1環(huán)的基本方向組和起始點(diǎn)為（即取老方向組）當(dāng)F2＜F3當(dāng)F2≥F3令k←k+1，返回步驟⑵⑺置k+1環(huán)的方向組和起始點(diǎn)為令k←k+1，返回步驟⑵例題4.2試用鮑威爾修正算法求目標(biāo)函數(shù)的最優(yōu)解。已知初始點(diǎn)，迭代精度ε=0.001解：第一環(huán)迭代計(jì)算沿第一坐標(biāo)方向e1進(jìn)行一維搜索α1=2以為起點(diǎn)，改沿第二坐標(biāo)軸方向e2進(jìn)行一維搜索α2=0.5構(gòu)成新方向沿S1方向進(jìn)行以為搜索得極小點(diǎn)與極小值計(jì)算點(diǎn)距需進(jìn)行第二環(huán)迭代計(jì)算第二環(huán)迭代計(jì)算首先確定上環(huán)中的最大函數(shù)下降量及其相應(yīng)方向映射點(diǎn)及其函數(shù)值檢查鮑威爾條件于是可知鮑威爾條件兩式均不成立。第二環(huán)取基本方向組和起始點(diǎn)為沿e2方向作一維搜索得以為起點(diǎn)沿S1方向一維搜索得構(gòu)成新生方向沿S2方向一維搜索得檢查迭代終止條件需再作第三環(huán)迭代計(jì)算。根據(jù)具體情況來分析，S1，S2實(shí)際上為共軛方向，見下圖。本題又是二次函數(shù)，有共軛方向的二次收斂性，上面結(jié)果就是問題的最優(yōu)解?？梢灶A(yù)料，如果做第三環(huán)迭代，則一定各一維搜索的步長為零，必有故得最優(yōu)解梯度法

優(yōu)化設(shè)計(jì)是追求目標(biāo)函數(shù)值最小，因此，自然可以設(shè)想從某點(diǎn)出發(fā)，其搜索方向取該點(diǎn)的負(fù)梯度方向，使函數(shù)值在該點(diǎn)附近下降最快。這種方法也稱為最速下降法。一、基本原理

梯度法的迭代公式為：

x(k+1)=x(k)-

(k)g(k)

其中g(shù)(k)是函數(shù)F(x)在迭代點(diǎn)x(k)處的梯度

f(x(k))

，

(k)一般采用一維搜索的最優(yōu)步長，即

f(x(k+1))=f(x(k)-

(k)g(k))=minf(x(k)-

(k)g(k))=min()

據(jù)一元函數(shù)極值條件和多元復(fù)合函數(shù)求導(dǎo)公式，得

’()=-(f(x(k)-

(k)g(k)))Tg(k)

=0即(

f(x(k+1)))Tg(k)

=0或(g(k+1))Tg(k)=0

此式表明，相鄰的兩個(gè)迭代點(diǎn)的梯度是彼此正交的。也即在梯度的迭代過程中，相鄰的搜索方向相互垂直。梯度法向極小點(diǎn)的逼近路徑是鋸齒形路線，越接近極小點(diǎn)，鋸齒越細(xì)，前進(jìn)速度越慢。

這是因?yàn)樘荻仁呛瘮?shù)的局部性質(zhì)，

從局部上看，在該點(diǎn)

附近函數(shù)的下降最快，

但從總體上看則走了

許多彎路，因此函數(shù)

值的下降并不快。二、迭代終止條件

采用梯度準(zhǔn)則：

||g(k)||

三、迭代步驟

（1）任選初始迭代點(diǎn)x(0)，選收斂精度

。

（2）確定x(k)點(diǎn)的梯度（開始k=0)

（3）判斷是否滿足終止條件||g(k)||

？若滿足輸出最優(yōu)解，結(jié)束計(jì)算。否則轉(zhuǎn)下步。

（4）從x(k)點(diǎn)出發(fā)，沿-g(k)方向作一維搜索求最優(yōu)步長

(k)。得下一迭代點(diǎn)x(k+1)=x(k)-

(k)g(k),令k=k+1返回步驟(2)。四、梯度法流程圖入口給定：x(0)，

k=0||g(k)||

？x*=x(k)f*=f(x(k))出口x(k)=

x(0)計(jì)算：g(k)k=k+1沿g(k)方向一維搜索，求最優(yōu)步長

(k)。x(k+1)=

x(k)-

(k)g(k)/||g(k)||NY例題4.3用梯度法求目標(biāo)函數(shù)的最優(yōu)解。已知初始點(diǎn)迭代精度ε=0.005解：函數(shù)的梯度第一次迭代：以為起點(diǎn)沿一方向作一維搜索得第一個(gè)迭代點(diǎn)繼續(xù)第二次迭代到第五次迭代結(jié)束時(shí)，有故迭代可終止，最優(yōu)解為迭代數(shù)據(jù)表見課本表4.2共軛梯度法

共軛梯度法是共軛方向法的一種，因?yàn)樵摲椒ㄖ忻恳粋€(gè)共軛向量都是依賴于迭代點(diǎn)處的負(fù)梯度而構(gòu)造出來的，所以稱作共軛梯度法。一、共軛梯度法的搜索方向

共軛梯度法的搜索方向采用梯度法基礎(chǔ)上的共軛方向，如圖所示，目標(biāo)函數(shù)F(x)在迭代點(diǎn)xk+1處的負(fù)梯度為-f(xk+1)，該方向與前

一搜索方向Sk互為正交，在此

基礎(chǔ)上構(gòu)造一種具有較高收斂

速度的算法，該算法的搜索方

向要滿足以下兩個(gè)條件：

（1）以xk+1點(diǎn)出發(fā)的搜索方

向Sk+1是-f(xk+1)與Sk的線性

組合。即xkx*xk+1-f(xk+1)Sk+1Sk

Sk+1=-f(xk+1)+

kSk

（2）以與為基底的子空間中，矢量與相共軛，即滿足

[Sk+1]T

G

Sk=0二、

k的確定

確定方法自學(xué)，不作要求。記住三、共軛梯度法的算法

（1）選初始點(diǎn)x0和收斂精度

。

（2）令k=0，計(jì)算S0=-

f(x0)

。

（3）沿Sk方向進(jìn)行一維搜索求

(k)，得

x(k+1)=x(k)+

(k)S(k)

（4）計(jì)算

f(xk+1)

，若||

f(xk+1)||

，則終止迭代，取x*=xk+1；否則進(jìn)行下一步。

（5）檢查搜索次數(shù)，若k=n，則令x0=xk+1，轉(zhuǎn)（2），否則，進(jìn)行下一步。（6）構(gòu)造新的共軛方向

Sk+1=-f(xk+1)+

kSk

令k=k+1，轉(zhuǎn)（3）四、共軛梯度法流程圖入口k=0，計(jì)算：-f(x0)

||

f(xk+1)

||

？出口求

(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+1NYSk+1=-f(xk+1)+

kSkK=K+1五、共軛梯度法的特點(diǎn)

共軛梯度法屬于解析法，其算法需求一階導(dǎo)數(shù)，所用公式及算法簡單，所需存儲(chǔ)量少。該方法以正定二次函數(shù)的共軛方向理論為基礎(chǔ)，對(duì)二次型函數(shù)可以經(jīng)過有限步達(dá)到極小點(diǎn)，所以具有二次收斂性。但是對(duì)于非二次型函數(shù)，以及在實(shí)際計(jì)算中由于計(jì)算機(jī)舍入誤差的影響，雖然經(jīng)過n次迭代，仍不能達(dá)到極小點(diǎn)，則通常以重置負(fù)梯度方向開始，搜索直至達(dá)到預(yù)定精度，其收斂速度也是較快的。六、例題牛頓法

牛頓法是求無約束最優(yōu)解的一種古典解析算法。牛頓法可以分為原始牛頓法和阻尼牛頓法兩種。

實(shí)際中應(yīng)用較多的是阻尼牛頓法。原始牛頓法一、原始牛頓法的基本思想

在第k次迭代的迭代點(diǎn)x(k)鄰域內(nèi)，用一個(gè)二次函數(shù)去近似代替原目標(biāo)函數(shù)F(x)，然后求出該二次函數(shù)的極小點(diǎn)作為對(duì)原目標(biāo)函數(shù)求優(yōu)的下一個(gè)迭代點(diǎn)，依次類推，通過多次重復(fù)迭代，使迭代點(diǎn)逐步逼近原目標(biāo)函數(shù)的極小點(diǎn)。

如圖所示。F(x)

1(x)

0(x)x0x1x2x*二、原始牛頓法的迭代公式

設(shè)目標(biāo)函數(shù)F(x)具有連續(xù)的一、二階導(dǎo)數(shù)，在x(k)點(diǎn)鄰域內(nèi)取F(x)的二次泰勒多項(xiàng)式作近似式，即

取逼近函數(shù)

(x)為

設(shè)x(k+1)為

(x)極小點(diǎn)，根據(jù)極值的必要條件，應(yīng)有

(x(k+1))=0，即

(x)=gk+Hkx=0

又

x=x(k+1)

-x(k)

得x(k+1)

=x(k)

-Hk-1gk

即牛頓法迭代公式，方向-Hk-1gk稱為牛頓方向三、原始牛頓法的特點(diǎn)

若用原始牛頓法求某二次目標(biāo)函數(shù)的最優(yōu)解，則構(gòu)造的逼近函數(shù)與原目標(biāo)函數(shù)是完全相同的二次式，其等值線完全重合，故從任一點(diǎn)出發(fā)，一定可以一次達(dá)到目標(biāo)函數(shù)的極小點(diǎn)。

牛頓法是具有二次收斂性的算法。

其優(yōu)點(diǎn)是：對(duì)于二次正定函數(shù)，迭代一次即可以得到最優(yōu)解，對(duì)于非二次函數(shù)，若函數(shù)二次性較強(qiáng)或迭代點(diǎn)已經(jīng)進(jìn)入最優(yōu)點(diǎn)的較小鄰域，則收斂速度也很快。

原始牛頓法的缺點(diǎn)是：由于迭代點(diǎn)的位置是按照極值條件確定的，并未沿函數(shù)值下降方向搜索，因此，對(duì)于非二次函數(shù)，有時(shí)會(huì)使函數(shù)值上升，即f(xk+1)>f(xk)，而使計(jì)算失敗。阻尼牛頓法對(duì)原始牛頓法的改進(jìn)為解決原始牛頓法的不足，加入搜索步長

(k)

因此，迭代公式變?yōu)椋?/p>

x(k+1)

=x(k)

-

(k)Hk-1gk

這就是阻尼牛頓法的迭代公式，最優(yōu)步長

(k)也稱為阻尼因子，是沿牛頓方向一維搜索得到的最優(yōu)步長。牛頓法算法步驟⑴任選初始點(diǎn)，給定精度ε，置k←0⑵計(jì)算點(diǎn)的梯度矢量及其模⑶檢驗(yàn)迭代終止條件如滿足，則輸出最優(yōu)解否則，轉(zhuǎn)下步⑷計(jì)算點(diǎn)處的海塞矩陣i，j=1，2……n并求其逆矩陣⑸確定牛頓方向并沿牛頓方向作一維搜索，求出在方向上的最優(yōu)步長⑹計(jì)算第k+1個(gè)迭代點(diǎn)置k←k+1，返回步驟⑵牛頓法的算法流程圖+-例題4.5

用牛頓法求函數(shù)的最優(yōu)解。初始點(diǎn)，解：函數(shù)的梯度和海賽矩陣及其逆在點(diǎn)處沿方向移位搜索求得最優(yōu)步長故新迭代點(diǎn)為該點(diǎn)的梯度迭代即可結(jié)束由于目標(biāo)函數(shù)是二次正定函數(shù)，故迭代一次即達(dá)到最優(yōu)點(diǎn)三、阻尼牛頓法的特點(diǎn)

優(yōu)點(diǎn)：由于阻尼牛頓法每次迭代都在牛頓方向進(jìn)行一維搜索，避免了迭代后函數(shù)值上升的現(xiàn)象，從而保持了牛頓法的二次收斂性，而對(duì)初始點(diǎn)的選擇沒有苛刻的要求。

缺點(diǎn)：

1、對(duì)目標(biāo)函數(shù)要求苛刻，要求函數(shù)具有連續(xù)的一、二階導(dǎo)數(shù)；為保證函數(shù)的穩(wěn)定下降，海賽矩陣必須正定；為求逆陣要求海賽矩陣非奇異。

2、計(jì)算復(fù)雜且計(jì)算量大，存儲(chǔ)量大DFP變尺度法

變尺度法也稱擬牛頓法，它是基于牛頓法的思想而又作了重大改進(jìn)的一類方法。我們所介紹的變尺度法是由Davidon于1959年提出又經(jīng)Fletcher和Powell加以發(fā)展和完善的一種變尺度法，故稱為DFP變尺度法。一、變尺度法的基本思想

變尺度法的基本思想與牛頓法和梯度法有密切聯(lián)系。觀察梯度法和牛頓法的迭代公式

x(k+1)=x(k)-

(k)g(k)

和

x(k+1)=x(k)-

(k)Hk-1g(k)

分析比較這兩種方法可知：梯度法的搜索方向?yàn)?/p>

-g(k)

，只需計(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í)收斂速度極慢。

牛頓法的搜索方向?yàn)?Hk-1g(k)

，不僅需要計(jì)算一階偏導(dǎo)數(shù)，而且要計(jì)算二階偏導(dǎo)數(shù)及其逆陣，