非線性無約束規(guī)劃

非線性無約束規(guī)劃第1頁，共45頁，2023年，2月20日，星期四1）方向?qū)?shù)設(shè)M0位數(shù)量場u=u(M)中的一點,從點M0出發(fā)引一條射線l,在l上點M0的附近取一動點M,記如果時，下列表達(dá)式的極限存在則稱之為M0處沿著l方向的方向?qū)?shù).記為當(dāng)時,表示函數(shù)u沿l是增加方向,當(dāng)時,表示函數(shù)u沿l是減小方向。1.方向?qū)?shù)與梯度第2頁，共45頁，2023年，2月20日，星期四2）直角坐標(biāo)系中方向?qū)?shù)的計算公式定理1.若函數(shù)u=u(x,y,z)在點M0(x0,y0,z0)處可微;

為l的方向余弦,則函數(shù)u在點M0處沿l方向?qū)?shù)必然存在，且有下面公式計算其中是在M0附近的偏導(dǎo)數(shù).例題1

求函數(shù)在點M(1,0,1)處沿著方向的方向?qū)?shù)解:

第3頁，共45頁，2023年，2月20日，星期四3)梯度：根據(jù)方向?qū)?shù)公式可以知道是其變化率最快的方向,稱為梯度,記為Gradu.如果用表示l線上的單位矢量,則方向?qū)?shù)可以寫成梯度的性質(zhì)：1)方向?qū)?shù)等于梯度在該方向的投影.即2)數(shù)量場u=u(M)中任一點M處的梯度,垂直于過該點的等值面,且指向u(M)增大的一方.例3

設(shè)為點M(x,y,z)的矢徑的模,試證第4頁，共45頁，2023年，2月20日，星期四2.海瑟矩陣海瑟矩陣是對稱形式：第5頁，共45頁，2023年，2月20日，星期四3非線性規(guī)劃問題的展開形式

多元函數(shù)泰勒公式的矩陣形式：其中線性函數(shù)：f(X)=CTX+B=cixi

+B二次函數(shù)：f(X)=(1/2)XTQX+CTX+Bf(x)=f(x*)+fT(x)(x-x*)+(1/2)(x-x*)T

2f(x*)(x-x*)+o‖x-x*‖2第6頁，共45頁，2023年，2月20日，星期四4凸集、凸函數(shù)和凸規(guī)劃1）凸函數(shù)

定義:

設(shè)集合SRn為凸集，函數(shù)f:SR

若x(1),x(2)S,(0,1)，均有

f(x(1)＋(1-)x(2))≤f(x(1))+(1-)f(x(2))，則稱f(x)為凸集S上的凸函數(shù)。若進一步有上面不等式以嚴(yán)格不等式成立，則稱f(x)為凸集S上的嚴(yán)格凸函數(shù)。性質(zhì):當(dāng)-f(x)為凸函數(shù)（嚴(yán)格凸函數(shù)）時，則稱f(x)為凹函數(shù)（嚴(yán)格凹函數(shù)）。嚴(yán)格凸函數(shù)凸函數(shù)嚴(yán)格凹函數(shù)第7頁，共45頁，2023年，2月20日，星期四2.2凸集、凸函數(shù)和凸規(guī)劃(續(xù))定理：f(x)為凸集S上的凸函數(shù)S上任意有限點的凸組合的函數(shù)值不大于各點函數(shù)值的凸組合。思考：設(shè)f1,f2是凸函數(shù)，設(shè)1,2>0,1f1+2f2,1f1-2f2是否凸函數(shù)？f(x)=max{f1(x),f2(x)},g(x)=min{f1(x),f2(x)}是否凸函數(shù)？

凸規(guī)劃=凸可行集+凸目標(biāo)函數(shù)第8頁，共45頁，2023年，2月20日，星期四凸函數(shù)與凹函數(shù)(續(xù))凸函數(shù)的判定:

如果函數(shù)f(X)的Hesse矩陣處處半正定，則f(X)為凸函數(shù)，若f(X)正定，則f(X)為嚴(yán)格凸函數(shù)。注:

該命題的逆命題不成立例題檢驗函數(shù)的凸性。第9頁，共45頁，2023年，2月20日，星期四無約束問題的最優(yōu)性條件1.必要條件：若X*是函數(shù)f(X)的局部最大點，則在該點必有f(X*)=0以及Hesse矩陣2f(X*)半正定定義:

對于可微函數(shù)f(X),稱使其梯度為零向量的點為平穩(wěn)點（駐點）。2.若X*是駐點，則其為極值點的充分條件:1)若H(X*)半正定，X*為局部極小點；若H(X*)正定，X*為孤立局部極小點；2)若H(X*)半負(fù)定，X*為局部極大點；若H(X*)負(fù)定，X*為孤立局部極大點；3)若H(X*)不定，X*為鞍點；(閱讀課本的例題)第10頁，共45頁，2023年，2月20日，星期四6最優(yōu)化問題的數(shù)值解VS解析解1.解析解與數(shù)值解注意獲得解析解的困難性。2、收斂性概念：考慮(fs)設(shè)迭代算法產(chǎn)生點列{x(k)}S.1)算法的理想收斂：設(shè)x*∈S是(fs)的最優(yōu)解，如果x*∈{x(k)}，或者雖然

x(k)

≠x*，但是k，滿足則稱算法收斂到最優(yōu)解x*。

第11頁，共45頁，2023年，2月20日，星期四

概念:

1)

局部最優(yōu):2)全局最優(yōu):3)嚴(yán)格全局最優(yōu)

以及

4)

全局收斂：對任意初始點x(1),算法均收斂。

5)局部收斂：當(dāng)x(1)

充分接近解x*時，算法才收斂。第12頁，共45頁，2023年，2月20日，星期四2.實用收斂性：

定義解集

S*={x|x具有某種性質(zhì)}

例：S*={x|x---g.opt}

S*={x|x---l.opt}

S*={x|f(x)=0}

S*={x|f′(x)≤β

}(β為給定實數(shù),稱為閾值

當(dāng)下列情況之一成立時，稱算法收斂：

1°x(k)∈S*;2°k，{X(k)}任意極限點∈S*第13頁，共45頁，2023年，2月20日，星期四8.收斂速度

設(shè)算法產(chǎn)生點列{x(k)},收斂到解x*,且x(k)≠x*，k，1.線性收斂：當(dāng)k充分大時成立2.超線性收斂：3.二階(次)收斂：

﹥0，當(dāng)k充分大時有第14頁，共45頁，2023年，2月20日，星期四定理：設(shè)算法點列{x(k)}超線性收斂于x*,且x(k)≠x*，k，那么證明只需注意|||x(k+1)–x*||-||x(k)–x*|||≤||x(k+1)–x(k)||≤||x(k+1)–x*||+||x(k)–x*||

，除以||x(k)–x*||并令k→∞，利用超線性收斂定義可得結(jié)果。8、收斂速度（續(xù)）第15頁，共45頁，2023年，2月20日，星期四4.1常用的搜索算法結(jié)構(gòu)考慮（fs）

常用一種線性搜索的方式構(gòu)造{xk}序列來求解迭代中從一點出發(fā)沿下降可行方向找一個新的、更優(yōu)的點。△下降方向：設(shè)∈S，d∈Rn,d≠0,若存在，使，稱d為

在點的下降方向。minf(x)

s.t.

x∈S第16頁，共45頁，2023年，2月20日，星期四4常用的搜索算法結(jié)構(gòu)△可行方向：設(shè)∈S，d∈Rn,d≠0,若存在使，稱d為該點的可行方向。

同時滿足上述兩個性質(zhì)的方向稱下降可行方向。第17頁，共45頁，2023年，2月20日，星期四迭代算法的停止標(biāo)準(zhǔn)1）2）3）對于無約束問題可以用第18頁，共45頁，2023年，2月20日，星期四10常用的搜索算法結(jié)構(gòu)線性搜索求，新點使x(k+1)∈S初始x(1)∈S,k=1對x(k)點選擇下降可行方向d(k)是否滿足停機條件？停k=k+1yesno第19頁，共45頁，2023年，2月20日，星期四11一維搜索一元函數(shù)求極小及線性搜索均為一維搜索。常用于求：

minf(x(k)+

d(k))=φ()s.t.

∈S

S有3種情況（-∞，+∞）或（0，+∞）或[a,b]一、縮小區(qū)間的精確一維搜索：考慮問題(P)minφ()

s.t.∈[α,β]

為此先介紹不確定區(qū)間及單峰函數(shù)的概念△不確定區(qū)間：[α,β]含φ(α)的最小點，但不知其位置第20頁，共45頁，2023年，2月20日，星期四單峰的概念一、縮小區(qū)間的精確一維搜索（續(xù)）若對任意λ1,λ2,α≤1<2

≤β滿足：

1o若

2

≤

*，則φ(

1)>φ(

2);

2o若

1

≥λ*，則φ(

1)<φ(

2).則稱φ(

)在[α,β]

上強單峰。

若只有當(dāng)φ(1)≠φ(*)，φ(2)≠φ(*)時，上述1o,2o式才成立，則稱φ(

)在[α,β]

上單峰。

α

*

12

β強單峰

α

*

β單峰第21頁，共45頁，2023年，2月20日，星期四設(shè)f(X)是目標(biāo)函數(shù)，如果是在給定Xk和方向矢量Pk下，通過f(x)=f(xk+akPk)

的極小化而產(chǎn)生則稱為最優(yōu)步長。根據(jù)單變量的駐點條件:以及復(fù)合函數(shù)的求導(dǎo)法則可得：1.精確一維搜索（假定求目標(biāo)函數(shù)極小值）第22頁，共45頁，2023年，2月20日，星期四2一維搜索一、縮小區(qū)間的精確一維搜索（續(xù)）

定理：設(shè)Ф：R→R

在[α，β]上單峰，α≤x1

＜x2≤β

。那么

1°若Ф(x1)≥Ф(x2)，則去除[，x2

]；如左下圖

2°若Ф(x1)＜Ф(x2)，則去除[x2，β]；如右下圖

α

x1

x2

β

αx1

x2β第23頁，共45頁，2023年，2月20日，星期四12一維搜索2、黃金分割法（0.618法）選二點x1<x2,比較f(x1)

與f(x2),可去掉[a,x1]或者[x2,b]

考慮下面分割條件：

1°對稱：x1

-a=b-x2……①

（使“壞”的情況去掉，區(qū)間長度不小于“好”的情況）

2°保持縮減比λ=(保留的區(qū)間長度／原區(qū)間長度)不變。（使每次保留下來的節(jié)點，在下一次的比較中成為一個相應(yīng)比例位置的節(jié)點)。如圖所示,推導(dǎo)縮減比λ第24頁，共45頁，2023年，2月20日，星期四黃金分割法的步驟:1)

確定初始區(qū)間為[a,b],初始區(qū)間的長度L=b-a,容差>0,k=12)計算初始分割點，x1=a+0.382L,f1=f(x1);x2=a+0.618L,f2=f(x2)3)消去大端值，計算新的分割點：若f1>f2,置a=x1,x1=x2,b=b,f1=f2,x2=a+b-x1,f2=f(x2)

若f1<=f2,置b=x2,x2=x1,a=a,f2=f1,x1=a+b-x2,f1=f(x1)4)收斂檢查；如果(b-a)/L<=,則按照下面方式輸出結(jié)果：若f1<f2,置x*=x1,f*=f1,a=a,b=x2;計算終止。否則，置x*=x2,f*=f2;,a=x1,b=b計算終止。否則，置k=k+1,返回3).通過上面分析可以估計給定容差的迭代次數(shù)N>lg

/log0.618例題用黃金分割法求解

minf(x)=x2-6x+10第25頁，共45頁，2023年，2月20日，星期四牛頓-拉夫遜法(牛頓切線法)

為了找到導(dǎo)數(shù)函數(shù)對應(yīng)的駐點，采用根近似假設(shè)xk是當(dāng)前駐點的近似解，則該點的f’(x)函數(shù)線性近似可以表示為

f’(x)f’(xk)+f”(xk)(x-xk)令此式為零，得出下一個近似點為

xk+1=xk-f’(xk)/f”(xk)收斂檢查：例題:

用牛頓切線法求解

minf(x)=2x2+16/x第26頁，共45頁，2023年，2月20日，星期四2、二次插值法：

用設(shè)f(x)是區(qū)間[a,b]上的連續(xù)單峰函數(shù)，x1,x2,x3

是該區(qū)間上三個相鄰點，它們的函數(shù)值分別為f1,f2,f3,且滿足兩邊大中間小的條件，f1>f2<f3,求系數(shù)

ao,a1,a2,使得二次函數(shù)

q(x)=a0+a1(x-x1)+a2(x-x1)(x-x2)

在這三點上與f(x)的函數(shù)值相等,可得到所有的系數(shù)。由dq/dx=0可得例題用二次插值法求解minf(x)=2x2+16/x，在區(qū)間[1,1.5]內(nèi)的最小值。第27頁，共45頁，2023年，2月20日，星期四3-3多維梯度法(f)

minf(x)

s.t.f:Rn→R(

f連續(xù)可微)

取極值的必要條件：若x*－l.opt.←→▽f(x*)=0(駐點)

說明：

f(x)

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

故

f(x*)

≤f(x)，

x.(由于▽Tf(x*)=0

)1.最速下降法

方向：在迭代點x(k)

取方向d(k)=－▽f(x(k))

步長:精確一維搜索第28頁，共45頁，2023年，2月20日，星期四最速下降法（續(xù)）特點：

1)全局收斂,線性收斂;2)缺點:易產(chǎn)生扭擺現(xiàn)象而造成早停

(當(dāng)x(k)距最優(yōu)點較遠(yuǎn)時,速度快,而接近最優(yōu)點時,速度下降)原因1：

f(x)=f(x(k))+▽Tf(x(k))(x-x(k))+o||x-x(k)||

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

)→0，于是高階項

o||x-x(k)||的影響可能超過▽Tf(x(k))(x-x(k))

。原因2：第29頁，共45頁，2023年，2月20日，星期四最速下降法的流程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+1例題3-9用最速下降法求解:第30頁，共45頁，2023年，2月20日，星期四3Newton法及其修正一、Newton法：

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

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

求駐點：

▽qk(x)=▽f(x(k))+▽2f(x(k))(x-x(k))=0

當(dāng)▽2f(x(k))正定時，令上述方程解為x(k+1),有極小點：

Newton迭代公式:

x(k+1)=x(k)-[▽2f(x(k))]-1▽f(x(k))停止條件:||f(x(k))||<第31頁，共45頁，2023年，2月20日，星期四Newton法的計算流程x(1),ε>0,k=1

x(k+1)=x(k)+p(k)||f(x(k))||<?STOP.x(k+1)—l.optYesNok=k+1實用中，判斷若▽2f(x(k))

非正定時進行相應(yīng)處理例題3-11用Newton法計算Pk+1=-[▽2f(x(k))]-1▽f(x(k))第32頁，共45頁，2023年，2月20日，星期四特點：1)二階收斂，局部收斂。（當(dāng)x(k)充分接近x*時,局部函數(shù)可用正定二次函數(shù)很好地近似，故收斂很快）2)當(dāng)f(x)為正定二次函數(shù)時，從任意初始點可一步迭代達(dá)到最優(yōu)解說明:

設(shè)f(x)=xTQx+PTx+r,Qn×n對稱正定,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(駐點即opt.)主要缺點：

(1)局部收斂

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

(3)需計算Hesse陣逆或解n階線性方程組，計算量大Newton法：（續(xù)）第33頁，共45頁，2023年，2月20日，星期四6、Newton法的改進（續(xù)）--------自己閱讀和體會(1)為減小工作量，取m（正整數(shù)），使每m次迭代使用同一個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,…

特點：收斂速度隨m的增大而下降

m=1時即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)

特點：可改善局部收斂性，當(dāng)d(k)為函數(shù)上升方向時，可向負(fù)方向搜索，但可能出現(xiàn)±d(k)均非下降方向的情況。第34頁，共45頁，2023年，2月20日，星期四二、算法流程圖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得λkx(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重新開始第35頁，共45頁，2023年，2月20日，星期四6共軛梯度法共軛的概念:

對于方向pi,pj相對于nn對稱正定矩陣Q共軛，則基本公式:停止條件:第36頁，共45頁，2023年，2月20日，星期四共軛梯度法算法特點1、全局收斂（下降算法）；線性收斂；2、每步迭代只需存儲若干向量(適用于大規(guī)模問題)；3、有二次終結(jié)性（對于正定二次函數(shù)，至多n次迭代可達(dá)opt.）例題3-10

用共軛梯度法求解第37頁，共45頁，2023年，2月20日，星期四目標(biāo)函數(shù)(f)minf(x),f:Rn→R1、基本思想：

用對稱正定矩陣H(k)近似▽2f(x(k))的逆,而H(k)的產(chǎn)生從給定H(1)開始逐步修整得到。2、算法框圖：x(1),H(1)對稱ε>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+1yN5變尺度法第38頁，共45頁，2023年，2月20日，星期四5、變尺度法的主要特點：

⑴只需用到函數(shù)一階梯度

(Newton法用到二階Hesse陣）⑵下降算法，故全局收斂；⑶不需求矩陣逆；（計算量?。纫话憧蛇_(dá)到超線性收斂；（速度快）⑸有二次終結(jié)性。二DFP(Davidon(1959),FletcherandPowell(1963))法:

1、DFP法：以下省去各量上標(biāo)，x,s,y,H

表示第k

步的量，等表示第k+1步的量。第39頁，共45頁，2023年，2月20日，星期四二、1、DFP法：（續(xù)）Ex.用DFP法求解minf(X)=10x12+x22解：取初始點x(1)=(1∕10,1)T,H(1)=I(單位矩陣)得到如下結(jié)果：（計算過程見下頁）第40頁，共45頁，2023年，2月20日，星期四第41頁，共45頁，2023年，2月20日，星期四2、BFGS法

BFGS(Broyden(1970),Fletcher(1970),Goldfarb(1970),Schann