運(yùn)籌學(xué)與最優(yōu)化方法-第5章無約束最優(yōu)化課件

第五章無約束最優(yōu)化方法2020/12/21第五章無約束最優(yōu)化（f）minf(x)f:Rn→R

5.1最優(yōu)性條件

設(shè)f連續(xù)可微必要條件：若x*－l.opt.則▽f(x*)=0(駐點(diǎn))。當(dāng)f凸時(shí)，x*－l.opt.←→▽f(x*)=0

注意：f(x)≥f(x*)+▽Tf(x*)(x-x*),x.

故f(x*)≤f(x)，x.（由于▽Tf(x*)=0）5.2最速下降法在迭代點(diǎn)x(k)取方向d(k)=－▽f(x(k)

)精確一維搜索

最速下降法：梯度方向函數(shù)值變化最快的方向2020/12/22第五章無約束最優(yōu)化5.2最速下降法（續(xù)）x(1),ε>0,k=1||▽f(x(k)

)

||<ε?Yesstop.x(k)–解

Nod(k)=－▽f(x(k)

)解minf(x(k)+λd(k))s.t.λ>0得x(k+1)=x(k)+λkd(k)k=k+12020/12/23第五章無約束最優(yōu)化5.2最速下降法（續(xù)）特點(diǎn)：全局收斂，線性收斂，易產(chǎn)生扭擺現(xiàn)象而造成早停。（當(dāng)x(k)距最優(yōu)點(diǎn)較遠(yuǎn)時(shí)，速度快，而接近最優(yōu)點(diǎn)時(shí)，速度下降）原因：f(x)=f(x(k))+▽Tf(x(k))(x-x(k))+o||x-x(k)||

當(dāng)x(k)接近l.opt.時(shí)▽f(x(k)

)→0，于是高階項(xiàng)o||x-x(k)||的影響可能超過▽Tf(x(k))(x-x(k))。5.3Newton法及其修正一、Newton法：

設(shè)f(x)二階可微，取f(x)在x(k)點(diǎn)附近的二階Taylor近似函數(shù)：

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

求駐點(diǎn)：

▽qk(x)=▽f(x(k))+▽2f(x(k))(x-x(k))=02020/12/24第五章無約束最優(yōu)化Newton法：（續(xù)）

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

x(k+1)=x(k)-[▽2f(x(k))]-1▽f(x(k))——Newton迭代公式實(shí)用中常用▽2f(x(k))S=-▽f(x(k))解得s(k)x(k+1)=x(k)+s(k)x(1),ε>0,k=1▽2f(x(k))S=-▽f(x(k))

得s(k),x(k+1)=x(k)+s(k)||s(k)||<ε?STOP.x(k+1)—l.optYesNok=k+1實(shí)用中，判斷若▽2f(x(k))

非正定時(shí)進(jìn)行相應(yīng)處理2020/12/25第五章無約束最優(yōu)化Newton法：（續(xù)）特點(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ì)算量大2020/12/26第五章無約束最優(yōu)化5.3Newton法及其修正二、Newton法的改進(jìn)：(1)為減小工作量，取m（正整數(shù)），使每m次迭代使用同一個(gè)Hesse陣，迭代公式變?yōu)椋?/p>

x(km+j+1)=x(km+j)-[▽2f(x(km))]-1▽f(x(km+j))j=0,1,2,…,m-1,k=0,1,2,…

特點(diǎn)：收斂速度隨m的增大而下降

m=1時(shí)即Newton法，m→∞即線性收斂。(2)帶線性搜索的Newton法：在Newton迭代中，取d(k)=-[▽2f(x(k))]-1▽f(x(k)),

加入線性搜索：minf(x(k)+λkd(k))

求得λk,x(k+1)=x(k)+λkd(k)

特點(diǎn)：可改善局部收斂性，當(dāng)d(k)為函數(shù)上升方向時(shí)，可向負(fù)方向搜索，但可能出現(xiàn)±d(k)均非下降方向的情況。2020/12/27第五章無約束最優(yōu)化5.3Newton法及其修正二、Newton法的改進(jìn)：（續(xù)）(3)Goldstein-Price方法(G-P法)：取d(k)=-[▽2f(x(k))]-1▽f(x(k))，▽2f(x(k))正定-▽f(x(k))，否則采用下列精確一維搜索：求λk，使其中δ

∈(0,1／2)1°f(x(k)+λk

d(k))≤f(x(k))+δ

▽f(x(k))

Td(k)λk2°f(x(k)+λkd(k))≥f(x(k))+(1-δ)▽f(x(k))

Td(k)λk特點(diǎn)：在一定條件下，G-P法全局收斂。但當(dāng)▽2f(x(k))非正定情況較多時(shí)，收斂速度降為接近線性。2020/12/28第五章無約束最優(yōu)化5.3Newton法及其修正二、Newton法的改進(jìn)：（續(xù)）(4)Levenberg-Marguardt法（L-M法）：主要思想：用[▽2f(x(k))+μI]

取代▽2f(x(k))進(jìn)行迭代，其中I為單位矩陣。μ>0使[▽2f(x(k))+μI]

正定，μ盡量小。特點(diǎn)：全局二階收斂。2020/12/29無約束最優(yōu)化----共軛梯度法一、共軛梯度法的方向：

設(shè)f(x)=(1/2)xTGx+bTx+cGn×n對(duì)稱正定，b∈Rn,從最速下降方向開始，構(gòu)造一組共軛方向：設(shè)初始點(diǎn)x(1),取d(1)=-▽f(x(1))……①(最速下降方向)設(shè)k≥1,已得到k個(gè)相互共軛的方向d(1),d(2),…,d(k),以及，由x(1)開始依次沿上述方向精確一維搜索得到點(diǎn)x(2),…，x(k),x(k+1).即有下式：

x(i+1)=x(i)+αid(i),i=1,2,…,k……②

精確一維搜索保證方向?qū)?shù)為0：▽fT(x(i+1))d(i)=0,i=1,2,…,k……③

在x(i+1)點(diǎn)構(gòu)造新方向d(k+1)為-▽f(x(k+1))與d(1),d(2),…,d(k)的組合：④2020/12/210共軛梯度法一、共軛梯度法的方向：（續(xù)）使d(k+1)與d(1),d(2),…,d(k)都共軛：

d(k+1)

TGd(j)=0,j=1,2,…,k……⑤Gram-Schmidt過程：i,

j=1,2,…,k記y(j)=▽f(x(j+1))-▽f(x(j))=G(x(j+1)-x(j))=αjGd(j)…….⑥

根據(jù)⑥式，有d(i)Ty(j)=αjd(i)TGd(j)=0,i≠j……⑦根據(jù)④，⑤，⑥有

d(k+1)

T

y(j)=αjd(k+1)TGd(j)=0,j=1,2,…,k……⑧⑧′這里的j應(yīng)為i2020/12/211共軛梯度法一、共軛梯度法的方向：（續(xù)）

j≤k,i<j有▽f(x(j+1))Td(i)=0……⑨由⑥式

由⑨式

▽f(x(j+1))T▽f(x(i))=0

i<j≤k……⑩(由④式

)根據(jù)⑧及⑥得：j=1,2,…,k-1-▽f(x(k+1))T[▽f(x(j+1))

-▽f(x(j))]+βj(k)d(j)Ty(j)=02020/12/212共軛梯度法一、共軛梯度法的方向：（續(xù)）上式中由⑩式有：-▽f(x(k+1))T

▽f(x(j+1))

=0由⑥式有：βj(k)d(j)Ty(j)=βj(k)αjd(j)TGd(j)于是βj(k)

=0故④式中只有βk(k)

≠0,記βk=βk(k)

可得到公式：

d(k+1)=-▽f(x(k+1))+βk

d(k)

當(dāng)j=k時(shí)，由⑧′,⑥式得：(11)注意：2020/12/213無約束最優(yōu)化2020/12/214二、算法流程圖x(1),ε>0d(1)=-▽f(x(1)),k=1k=k+1k=1||▽f(x(k))||<ε?Stop.x(k)—解解minf(x(k)+λd(k))s.t.λ>0得λk

x(k+1)=x(k)+λkd(k)

k=n?x(1)=x(n+1)d(1)=-▽f(x(1)),k=1求βkd(k+1)=-▽f(x(k+1))+βkd(k)yNyN重新開始2020/12/2155.4共軛梯度法三、算法特點(diǎn)：1、全局收斂（下降算法）；線性收斂；2、每步迭代只需存儲(chǔ)若干向量（適用于大規(guī)模問題）；3、有二次終結(jié)性（對(duì)于正定二次函數(shù)，至多n次迭代可達(dá)opt.）

注：對(duì)不同的βk公式，對(duì)于正定二次函數(shù)是相等的，對(duì)非正定二次函數(shù)，有不同的效果，經(jīng)驗(yàn)上PRP效果較好。2020/12/216變尺度法一、變尺度法的基本思路：(f)minf(x),f:Rn→R1、基本思想：用對(duì)稱正定矩陣H(k)近似▽2f(x(k)),而H(k)的產(chǎn)生從給定H(1)開始逐步修整得到。2、算法框圖：x(1),H(1)對(duì)稱ε>0,k=1d(k)=-H(k)▽f(x(k))一維搜索得λkx(k+1)=x(k)+λkd(k)||x(k+1)-x(k)||<ε?修正H(k)產(chǎn)生H(k+1)Stop.x(k+1)----解k=k+1yN2020/12/217變尺度法一、變尺度法的基本思路：（續(xù)）3、擬Newton方程：記：s(k)=x(k+1)-x(k),y(k)=▽f(x(k+1))-▽f(x(k))

當(dāng)f為二次函數(shù)時(shí)：f(x)=1∕2xTBx+cTx+b

▽f=Bx+c

有y(k)=Bs(k)

或s(k)=B-1y(k)

稱Hy=S或y=BS為擬Newton方程。顯然當(dāng)H正定時(shí),B-1=H.4、”近似”：對(duì)于f(x)的二階Taylor展式，舍去高階項(xiàng)，有y(k)≈▽2f(x(k))s(k)

或s(k)≈(▽2f

(x(k)))-1y(k)用矩陣B(k)或H(K)分別取代▽2f(x(k))或者(▽2f

(x(k)))-1使擬Newton方程成立，可看作是對(duì)▽2f(x(k))或(▽2f

(x(k)))-1的一種近似。此種近似H或B不唯一。2020/12/218變尺度法一、變尺度法的基本思路：（續(xù)）5、變尺度法的主要特點(diǎn)：⑴只需用到函數(shù)的一階梯度；（Newton法用到二階Hesse陣）⑵下降算法，故全局收斂；⑶不需求矩陣逆；（計(jì)算量?。纫话憧蛇_(dá)到超線性收斂；（速度快）⑸有二次終結(jié)性。二、DFP(Davidon(1959),FletcherandPowell(1963))法和

BFGS(Broyden(1970),Fletcher(1970),Goldfarb(1970),Schanno(1970))法:1、DFP法：

以下省去各量上標(biāo)，x,s,y,H

表示第k

步的量，等表示第k+1步的量。2020/12/219變尺度法二、DFP法和BFGS法:1、DFP法：（續(xù)）2020/12/220二、1、DFP法：（續(xù)）Ex.用DFP法求解10x12+x22解：取初始點(diǎn)x(1)=(1∕10,1)T,H(1)=I(單位矩陣)得到如下結(jié)果：（計(jì)算過程見下頁）2020/12/221二、1、DFP法：（續(xù)）計(jì)算過程：2020/12/222二、1、DFP法：（續(xù)）2020/12/223二、1、DFP法：（續(xù)）定理：設(shè)H對(duì)稱正定，sTy>0那么DFP法產(chǎn)生的對(duì)稱正定。注：下列各情況下有sTy>0：

1of(x)為正定二次函數(shù)；2o精確一維搜索時(shí)；3o前章介紹的不精確一維搜索時(shí)?？梢宰C明：DFP法在精確一維搜索前提下，超線性收斂。2、BFGS法若把前面的推導(dǎo)，平行地用在y=Bs公式上，可得到2020/12/224二、2、BFGS法（續(xù)）用此公式求方向時(shí)，需用到矩陣求逆或解方程：

d=-B-1▽f(x)或Bd=-▽f(x)由于每次只有秩2的變換，這里的計(jì)算量仍可以降下來。為了得到H-公式，可對(duì)上面求逆（推導(dǎo)得）：BFGS法有變尺度法的全部優(yōu)點(diǎn)，并且在一定條件下可以證明在BFGS法中使用前文中介紹的不精確一維搜索有全局收斂性。

2020/12/225三、Broyden族

當(dāng)在秩2公式中，α、β

任意選取時(shí)可得到不同的公式，經(jīng)過理論推導(dǎo)，可得到下列結(jié)果：2020/12/226三、Broyden族（續(xù)）2020/12/227直接算法

minf(x)一、單純形法及可變多面體算法1、單純形法基本思路：設(shè)x(0),x(1),…,x(n)是Rn中n+1個(gè)點(diǎn)構(gòu)成的一個(gè)當(dāng)前的單純形。比較各點(diǎn)的函數(shù)值得到：x

max,x

min使

f(x

max)=max{f(x(0)),f(x(1)),…,f(x(n))}

f(x

min)=min{f(x(0)),f(x(1)),…,f(x(n))}

取單純形中除去x

max點(diǎn)外，其他各點(diǎn)的形心：去掉x

max，加入x(n+1)得到新的單純形。重復(fù)上述過程。2020/12/228一、1、單純形法基本思路：（續(xù)）幾點(diǎn)注意：⑴當(dāng)x(n+1)又是新單純形的最大值點(diǎn)時(shí)，取次大值點(diǎn)進(jìn)行反射；⑵若某一個(gè)點(diǎn)x′出現(xiàn)在連續(xù)m個(gè)單純形中的時(shí)候，取各點(diǎn)與x′連線的中點(diǎn)（n個(gè)）與x′點(diǎn)構(gòu)成新的單純形，繼續(xù)進(jìn)行。經(jīng)驗(yàn)上取m≥1.65n+0.05n2

例如：n=2時(shí)，可取m≥1.65×2+0.05×4=3.5可取m=4.123457891061112132020/12/229一、1、單純形法基本思路：（續(xù)）優(yōu)點(diǎn)：不需求導(dǎo)數(shù)，不需要一維搜索。缺點(diǎn)：無法加速，收斂慢，效果差。2、改進(jìn)單純形法：（可變多面體算法）

設(shè)第k步迭代得到n+1個(gè)點(diǎn)：x(0),x(1),…,x(n)，得到x

max,x

min及通過下列4步操作選新迭代點(diǎn)：1o反射：取反射系數(shù)α>0,(單純形法中α=1)

2o擴(kuò)展：給定擴(kuò)展系數(shù)γ>1,計(jì)算。（加速）2020/12/230一、

2、改進(jìn)單純形法：（續(xù)）

若f(y(1))<f(x

min),則若f(y(1))>f(y(2)),那么y(2)取代x

max;否則，y(1)取代x

max。若max{f(x(i))|x(i)≠x

max}≥f(y(1))≥f(x

min),y(1)取代x

max。3°收縮：若f(x

max)>f(y(1))>f(x(i)),x(i)≠x

max,計(jì)算,以y(3)取代x

max

。4°減半：若f(y(1))>f(x

max),重新取各點(diǎn)，使

x(i)=xmin+1∕2(x(i)-x

min)得到新單純形。經(jīng)驗(yàn)上：α=1,0.4≤β≤0.6,2.3≤γ≤3.0.有人建議:α=1,β=0.5，γ=2。算法停機(jī)準(zhǔn)則取：2020/12/231二、模式搜索法：Hooke&Jeeves19611、基本思想與主要過程：△利用兩類移動(dòng)（探測性移動(dòng)和模式性移動(dòng)）進(jìn)行一步迭代：

探測性移動(dòng)的目的：探求一個(gè)沿各坐標(biāo)方向的新點(diǎn)并得到一個(gè)“有前途”的方向；模式性移動(dòng)的目的：沿上述“有前途”方向加速移動(dòng)?！髦饕^程：第k步迭代，設(shè)已得到x(k)1°探測性移動(dòng)：給定步長αk，設(shè)通過模式性移動(dòng)得到y(tǒng)(0),

依次沿各坐標(biāo)方向e(i)=(0,…,1,0,…,0)T

i

移動(dòng)αk步長：i=0,1,…,n-1,=y(i)+e(i+1)

若f()<f(y(i)),則y(i+1)=2020/12/232二、1、基本思想與主要過程：（續(xù)）

否則取=y(i)+e(i+1)

若f()<f(y(i)),則y(i+1)=否則