運(yùn)籌學(xué)與最優(yōu)化方法第2章課件

第二

章無約束非線性規(guī)劃2.1解的定義f(X)局部最優(yōu)解整體最優(yōu)解例題見P11-122.2一維問題有解的條件設(shè)有一維無約束非線性規(guī)劃(2.2.1)則由數(shù)學(xué)分析的知識(shí)我們有

(1)若函數(shù)f(x)可微，則它在點(diǎn)x*取得局部最優(yōu)解(極值)的必要條件是(2)若函數(shù)f(x)在點(diǎn)x*處有二階連續(xù)導(dǎo)數(shù)，則它在點(diǎn)x*取得局部最優(yōu)解(極值)的充分條件是利用上述結(jié)論我們?cè)跀?shù)學(xué)分析中求局部最優(yōu)解(極值)的方法已很熟悉，但問題是在實(shí)際工作要找“駐點(diǎn)”的精確值往往是行不通的。因此在這里要單間介紹數(shù)值近似法的主要思想。2.3一維問題求解的方法基本思想：確定一個(gè)包含最優(yōu)值的已知區(qū)間，在保證不失去最優(yōu)值的條件下逐步縮小區(qū)間，當(dāng)把區(qū)間縮得足夠小時(shí)，即可用該區(qū)間內(nèi)的任何點(diǎn)做為近似最優(yōu)點(diǎn)。黃金分割法（0.618法）該方法是以不變的區(qū)間縮短率(黃金分割數(shù)(√5-1)/2=0.618)

縮小區(qū)間長度。其特點(diǎn)是效率低，但適用范圍廣（不需對(duì)函數(shù)有連續(xù)等附加條件）且編程方便。因此有0.618法計(jì)算步驟如下:切線法（一維牛頓法）設(shè)函數(shù)f(x)在(a,b)內(nèi)有二階連續(xù)導(dǎo)數(shù)求解思路是：在初始探索點(diǎn)xk

處用泰勒展式作

f(x)的二次近似函數(shù)g(x)，再用g(x)的最小點(diǎn)作新的探索點(diǎn)。即所以,當(dāng)|xk+1-xk|小于給定誤差δ時(shí)，xk是最優(yōu)解的近似值。abx1x2xkf(x)abx1x2xkf′

(x)f′(x)的切線法式方程示意圖牛頓法示意圖故也可解釋為用牛頓求根公式法求f(x)的駐點(diǎn)x*因此有牛頓法算法框圖如下:

其特點(diǎn)是收斂快效率高，但要求條件下高（需對(duì)函數(shù)有二階連續(xù)可微的附加條件）。初始x1,ε1,ε2>0k=1︱f′(xk)

︱<ε1?停；輸出解xk

yNf″(xk)>0?N輸出求解失敗Yxk

+1=xk-f′(xk)／f″(xk)|xk

+1-xk

|<ε2

YNk=k+1例求minф(λ)=arctantdt

解：ф′(λ)=arctan

λ,ф″(λ)=1／(1+λ2)

迭代公式：λk

+1=λk-

(1+λ2)arctan

λk

取λ1=1，計(jì)算結(jié)果：

k

λk

ф′(λk)1／ф″(λk)110.785422-0.5708-0.51871.325830.1169-0.11641.01374-0.001095-0.001095λ4≈λ*=0

取λ1=2，計(jì)算結(jié)果如下：

k

λk

ф′(λk)1／ф″(λk)121.107152-3.5357-1.295213.50313.95不收斂。

k

λk

ф′(λk)1／ф″(λk)121.107152-3.5357-1.295213.50313.95不收斂。插值法：

用ф(λ)在2或3個(gè)點(diǎn)的函數(shù)值或?qū)?shù)值，構(gòu)造2次或3次多項(xiàng)式作為ф(λ)的近似值，以這多項(xiàng)式的極小點(diǎn)為新的迭代點(diǎn)。

3點(diǎn)2次，2點(diǎn)2次，4點(diǎn)3次，3點(diǎn)3次，2點(diǎn)3次等

以3點(diǎn)2次為例：取λ1，λ

2，λ3，求出ф(λ1)，ф(λ2)，ф(λ3)割線法（一維擬牛頓法）

牛頓特點(diǎn)是收斂快效率高，但每步要計(jì)算二階導(dǎo)數(shù)，在函數(shù)復(fù)雜時(shí)，求導(dǎo)數(shù)是很難的?？捎貌钌探茖?dǎo)數(shù)，則牛頓切線法公式變換為它的幾何意義是用兩點(diǎn)xk-1，

xk的割線代替f′(x)在點(diǎn)xk的切線。它不需計(jì)算二階導(dǎo)數(shù)，但它收斂速度也慢于切線法。

二次插值多項(xiàng)式：g(x)=α

x2+βx+γ

αx12+βx1+γ=g(x1)

αx22+βx2+γ=g(x2)

αx32+βx3+γ=g(x3)

解得插值法設(shè)

[a,b]是f(x)的單谷區(qū)間

，x*為f(x)在[a,b]中的極小點(diǎn)，在[a,b]中任取x2，令x1=a,x3=b,

用如下二次插值多項(xiàng)式插值2.4多維問題有解的條件設(shè)有多維無約束非線性規(guī)劃(2.4.1)2.5多維問題求解的方法算法概述問題1、如何選擇初始點(diǎn)？2、如何產(chǎn)生新點(diǎn)xk+1，即如何確定搜索方向和步長？3、選擇什么迭代終止準(zhǔn)則好？算法的收斂速度

問題對(duì)于某一確定的下降算法，其優(yōu)劣如何評(píng)價(jià)？人們通常采用收斂速度來評(píng)價(jià)。下面給出度量收斂速度的幾個(gè)概念。復(fù)習(xí)梯度的性質(zhì)：⑴函數(shù)在某點(diǎn)的梯度方向?yàn)楹瘮?shù)過該點(diǎn)的等值線的法線方向；⑵函數(shù)值沿梯度方向增加最快，沿負(fù)梯度方向下降最快；⑶梯度描述的只是函數(shù)某點(diǎn)鄰域內(nèi)的局部信息。參見P27圖2-16。梯度法（最速下降法）

對(duì)于迭代式，當(dāng)取搜索方向?yàn)樨?fù)梯度方向時(shí)構(gòu)成的尋優(yōu)算法，稱為求解無約束優(yōu)化問題的梯度法。迭代步驟梯度法的特點(diǎn)梯度法尋優(yōu)效率受目標(biāo)函數(shù)性態(tài)影響較大。若目標(biāo)函數(shù)等值線為圓，則一輪搜索就可找到極致點(diǎn)；若當(dāng)目標(biāo)函數(shù)等值線為扁橢圓時(shí)，收斂速度則顯著下降。梯度法中相鄰兩輪搜索方向相互垂直。Newton法設(shè)f(x)二階可微，取f(x)在x(k)點(diǎn)附近的二階Taylor近似函數(shù)：

gk(x)=f(x(k))+▽Tf(x(k))(x-x(k))+1／2(x-x(k))T▽2f(x(k))(x-x(k))

求駐點(diǎn)：

▽gk(x)=▽f(x(k))+▽2f(x(k))(x-x(k))=0當(dāng)▽2f(x(k))正定時(shí)，有極小點(diǎn)：

x(k+1)=x(k)-[▽2f(x(k))]-1▽f(x(k))——Newton迭代公式

二維Newton法的幾何意義:在x(0)點(diǎn)附近,把曲面z=f(x),用它在該點(diǎn)的密切拋物面z=g0(x)近似代替,然后再用g0(x)的最小點(diǎn)x(1)作為新的起點(diǎn),用同樣的方法去找x(k),直到||▽2f(x(k))||<ε,用g0(x)的最小點(diǎn)x(k)作為曲面z=f(x)的局部最小點(diǎn)x*,即x*≈x(k)。令稱為牛頓方向再引入步長t，可得稱之為阻尼牛頓法公式。x(0),ε>0,k=1▽2f(x(k)),s(k)=-[▽2f(x(k))]2▽f(x(k))||▽2f(x(k))||<ε?STOP.x(k+1)—l.optYesNok=k+1實(shí)用中，判斷若▽2f(x(k))

非正定時(shí)進(jìn)行相應(yīng)處理牛頓法的迭代算法x(k+1)=x(k)+s(k)

Newton法優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：二階收斂。當(dāng)x(k)充分接近x*時(shí),局部函數(shù)可用正定二次函數(shù)很好地近似，故收斂很快。二次終結(jié)性：當(dāng)f(x)為正定二次函數(shù)時(shí)，從任意初始點(diǎn)可一步迭代達(dá)到最優(yōu)解。設(shè)f(x)=1／2xTQx+PTx+r,Qn×n對(duì)稱正定，P∈

Rn,r∈R.x(1),▽f(x(1))=Qx(1)+P▽2f(x(1))=Q

迭代：x(2)=x(1)-Q–1(Qx(1)+P)=-Q–1P(駐點(diǎn)即opt.)主要缺點(diǎn)：(1)局部收斂

(2)用到二階Hesse陣，且要求正定

(3)需計(jì)算Hesse陣逆或解n階線性方程組，計(jì)算量大共軛方向法(共軛梯度法)1、共軛方向的(代數(shù))定義：

對(duì)一般n元非線性函數(shù)f(x),可在其某個(gè)局部極小點(diǎn)X*鄰近的一點(diǎn)x(k),將f(x)用它的密切拋物面g(x)近似代替,再用g(x)的一組共軛方向進(jìn)行搜索即可。但一般不能在n步內(nèi)達(dá)到所需計(jì)算精度。共軛梯度法：在構(gòu)造共軛方向時(shí)，加入負(fù)梯度方向和一維搜索條件，即得共軛梯度法。設(shè)有問題任給初始點(diǎn)x(0)，取負(fù)梯度方向s(0)

=▽f(x(k))

為第一個(gè)方向，令x=x(0)+t

s(0)=x(0)-t

▽f(x(k))

作一維搜索

求得t,記為t0,從而得新的初始點(diǎn)x(1)=x(0)+t

s(0)=x(0)-t

▽f(x(k))，第二個(gè)方向取為s(1)=-▽f(x(1))+λ10

s(0)其中λ10代定，要求s(1)與s(0)是關(guān)于H共軛，即

(s(1))THs(0)=0解之得以x(1)為初始點(diǎn)重復(fù)以上步驟即可構(gòu)造出一組關(guān)于H的共軛方向s(i),i=0,1,…,n-1.計(jì)算λ10時(shí)要用Hesse矩陣H，計(jì)算復(fù)雜，面且不便于推廣到一般非線性函數(shù)f(x),故用簡化公式（在f(x)o為n元二次函數(shù)時(shí)可證）于是有共軛梯度算法：x(0),ε>0s(0)=-▽f(x(1)),k=0k=k+1||▽f(x(k))||<ε?Stop.x(k)—解解minf(x(k)+t

d(k))

s.t.t>0令x(k+1)=x(k)+tk

s(k)

K<n-1?x(0)=x(n)s(0)=-▽f(x(0)),k=0求λ

k+1,s(k+1)=-▽f(x(k+1))+λ

k+1s(k)yNNy重新開始得tk共軛梯度法算法優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：

1、公式簡單，存貯少，每步迭代只需存儲(chǔ)若干向量，對(duì)于正定二次函數(shù)，有二次終結(jié)性（至多n次迭代可達(dá)opt.）

2、收斂速度介于梯度法和牛頓法之間（適用于大規(guī)模問題）。缺點(diǎn)1、其收斂性強(qiáng)列依賴于精確的一維搜索。2、其理論背景至今尚未研究清楚。

擬牛頓法（變尺度法）1、基本思想：用對(duì)稱正定矩陣H(k