1、第 三 章,無約束非線性最優(yōu)化方法,基本模型: 用符號(hào)(fs)表示非線性規(guī)劃,1）方向?qū)?shù) 設(shè)M0位數(shù)量場u=u(M)中的一點(diǎn),從點(diǎn)M0出發(fā)引一 條射線l,在l上點(diǎn)M0的附近取一動(dòng)點(diǎn)M, 記 如果 時(shí)，下列表達(dá)式的極限存在 則稱之為M0處沿著l方向的方向?qū)?shù). 記為 當(dāng) 時(shí), 表示函數(shù)u沿l是增加方向, 當(dāng) 時(shí), 表示函數(shù)u沿l是減小方向。,1.方向?qū)?shù)與梯度,2） 直角坐標(biāo)系中方向?qū)?shù)的計(jì)算公式 定理1. 若函數(shù)u=u(x,y,z)在點(diǎn)M0(x0,y0,z0)處可微; 為l的方向余弦, 則函數(shù)u在點(diǎn)M0處 沿l方向?qū)?shù)必然存在，且有下面公式計(jì)算 其中 是在M0附近的偏導(dǎo)數(shù). 例題1 求函數(shù)

2、在點(diǎn)M(1,0,1)處沿著 方向的方向?qū)?shù) 解:,3)梯度：根據(jù)方向?qū)?shù)公式 可以知道 是其變化率最快的方向, 稱為 梯度, 記為Grad u. 如果用 表示l線 上的單位矢量, 則方向?qū)?shù)可以寫成 梯度的性質(zhì)： 1) 方向?qū)?shù)等于梯度在該方向的投影.即 2) 數(shù)量場u=u(M)中任一點(diǎn)M處的梯度, 垂直于過該點(diǎn) 的等值面, 且指向u(M)增大的一方. 例3 設(shè) 為點(diǎn)M(x,y,z)的矢徑 的模, 試證,2. 海瑟矩陣,海瑟矩陣是對(duì)稱形式：,3 非線性規(guī)劃問題的展開形式,多元函數(shù)泰勒公式的矩陣形式： 其中,線性函數(shù)：f (X) = CTX + B = ci xi + B 二次函數(shù)：f (X)

3、= (1/2) XTQX + CTX + B,f (x) = f (x*)+ f T(x)(x-x*) + (1/2)(x-x*)T 2f (x*)(x-x*) + ox-x*2,4 凸集、凸函數(shù)和凸規(guī)劃,1）凸函數(shù) 定義: 設(shè)集合 S Rn 為凸集，函數(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ù)。 若進(jìn)一步有上面不等式以嚴(yán)格不等式成立，則稱 f(x) 為凸集 S 上的嚴(yán)格凸函數(shù)。 性質(zhì): 當(dāng)- f(x) 為凸函數(shù)（嚴(yán)格凸函數(shù)）時(shí)，則稱 f(x

4、) 為凹函數(shù)（嚴(yán)格凹函數(shù)）。,嚴(yán)格凸函數(shù),凸函數(shù),嚴(yán)格凹函數(shù),2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),定理： f(x) 為凸集 S 上的凸函數(shù) S 上任意有限點(diǎn)的凸組合的函數(shù)值不大于各點(diǎn)函數(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ù),凸函數(shù)與凹函數(shù)(續(xù)),凸函數(shù)的判定: 如果函數(shù)f (X)的Hesse矩陣處 處半正定，則f (X)為凸函數(shù)， 若f (X)正定，則f (X) 為嚴(yán)格凸

5、函數(shù)。 注: 該命題的逆命題不成立 例題 檢驗(yàn)函數(shù) 的凸性。,無約束問題的最優(yōu)性條件,1. 必要條件：若X*是函數(shù)f(X)的局部最大點(diǎn)，則在該點(diǎn)必有f(X*)=0以及Hesse矩陣2f(X*)半正定 定義: 對(duì)于可微函數(shù)f(X), 稱使其梯度為零向量的點(diǎn)為平穩(wěn)點(diǎn)（駐點(diǎn)）。 2. 若X*是駐點(diǎn)，則其為極值點(diǎn)的充分條件: 1) 若H(X*)半正定，X*為局部極小點(diǎn)； 若H(X*)正定，X*為孤立局部極小點(diǎn)； 2)若H(X*)半負(fù)定，X*為局部極大點(diǎn)； 若H(X*)負(fù)定，X*為孤立局部極大點(diǎn)； 3)若H(X*)不定，X*為鞍點(diǎn)；(閱讀課本的例題),6 最優(yōu)化問題的數(shù)值解 VS 解析解,1. 解析解與

6、數(shù)值解 注意獲得解析解的困難性。 2、收斂性概念： 考慮(fs)設(shè)迭代算法產(chǎn)生點(diǎn)列x(k) S. 1) 算法的理想收斂：設(shè)x*S是(fs)的最優(yōu)解，如果x*x(k)，或者雖然 x(k) x*， 但是k，滿足 則稱算法收斂到最優(yōu)解 x*。,概念: 1) 局部最優(yōu): 2) 全局最優(yōu): 3) 嚴(yán)格全局最優(yōu) 以及 4) 全局收斂： 對(duì)任意初始點(diǎn)x(1), 算法均收斂。 5) 局部收斂： 當(dāng)x(1) 充分接近解x*時(shí)，算法才收斂。,2. 實(shí)用收斂性： 定義解集 S* = x | x 具有某種性質(zhì) 例：S*=x|x-g.opt S*=x|x-l.opt S*=x| f(x)=0 S*=x|f(x) (為給

7、定實(shí)數(shù),稱為閾值 當(dāng)下列情況之一成立時(shí)，稱算法收斂： 1x(k) S*; 2k，X(k)任意極限點(diǎn)S*,8. 收斂速度,設(shè)算法產(chǎn)生點(diǎn)列x(k), 收斂到解x*, 且x(k)x*， k， 1.線性收斂： 當(dāng)k充分大時(shí)成立 2.超線性收斂： 3.二階(次)收斂： 0，當(dāng)k充分大時(shí)有,定理：設(shè)算法點(diǎn)列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ù)）,4.

8、1 常用的搜索算法結(jié)構(gòu),考慮（fs） 常用一種線性搜索的方式構(gòu)造xk序列來求解 迭代中從一點(diǎn)出發(fā)沿下降可行方向找一個(gè)新的、更優(yōu)的點(diǎn)。 下降方向 ： 設(shè) S，d Rn,d0,若存在 ，使 ，稱d 為 在 點(diǎn)的下降方向。,4 常用的搜索算法結(jié)構(gòu),可行方向： 設(shè) S，dRn, d0, 若存在 使 ， 稱d 為該點(diǎn)的可行方向。 同時(shí)滿足上述兩個(gè)性質(zhì)的方向稱 下降可行方向。,迭代算法的停止標(biāo)準(zhǔn),1） 2） 3） 對(duì)于無約束問題可以用,10 常用的搜索算法結(jié)構(gòu),線性搜索求 ， 新點(diǎn) 使x(k+1)S,yes,no,11 一維搜索,一元函數(shù)求極小及線性搜索均為一維搜索。常用于求： min f(x(k)+ d

9、(k)=( ) s.t. S S有3種情況（-，+）或（0， + ）或a,b 一、縮小區(qū)間的精確一維搜索：考慮問題(P) min ( ) s.t. , 為此先介紹不確定區(qū)間及單峰函數(shù)的概念 不確定區(qū)間：, 含()的最小點(diǎn)， 但不知其位置,單峰的概念,一、縮小區(qū)間的精確一維搜索（續(xù)） 若對(duì)任意1 ,2, 1 ( 2); 2 若 1 * ，則( 1) ( 2). 則稱( )在, 上強(qiáng)單峰。 若只有當(dāng)( 1) ( * )， ( 2) ( * )時(shí)，上述1, 2 式才成立，則稱( )在, 上單峰。,設(shè)f(X)是目標(biāo)函數(shù)，如果 是在給定Xk和方向 矢量Pk下，通過f(x)=f(xk+akPk) 的極小化

10、而產(chǎn)生 則稱 為最優(yōu)步長。 根據(jù)單變量的駐點(diǎn)條件: 以及復(fù)合函數(shù)的求導(dǎo)法則可得：,1. 精確一維搜索（假定求目標(biāo)函數(shù)極小值）,2 一維搜索,一、縮小區(qū)間的精確一維搜索（續(xù)） 定理： 設(shè)：RR 在， 上單峰，x1 x2 。 那么 1若(x1) (x2)，則去除 ， x2 ；如左下圖 2若(x1)(x2)， 則 去除x2，；如右下圖,12 一維搜索,2、黃金分割法（0.618 法） 選二點(diǎn)x1x2 ,比較f(x1) 與f(x2), 可去掉a, x1或者x2 ,b 考慮下面分割條件： 1對(duì)稱： x1 - a = b -x2 （使“壞”的情況去掉，區(qū)間長度不小于“好”的情況） 2保持縮減比 =(保留的

11、區(qū)間長度原區(qū)間長度) 不變。 （使每次保留下來的節(jié)點(diǎn)， 在下一次的比較中成為一個(gè)相應(yīng)比例位置的節(jié)點(diǎn) )。如圖所示, 推導(dǎo)縮減比 ,黃金分割法的步驟: 1) 確定初始區(qū)間為a,b, 初始區(qū)間的長度L=b-a, 容差 0, k=1 2) 計(jì)算初始分割點(diǎn)，x1=a+0.382L, f1=f(x1); x2=a+0.618L, f2=f(x2) 3) 消去大端值，計(jì)算新的分割點(diǎn)： 若f1f2, 置 a=x1, x1=x2, b=b, f1=f2, x2=a+b-x1, f2=f(x2) 若f1lg /log 0.618 例題 用黃金分割法求解 min f(x)=x2-6x+10,牛頓-拉夫遜法(牛頓切

12、線法) 為了找到導(dǎo)數(shù)函數(shù)對(duì)應(yīng)的駐點(diǎn)，采用根近似 假設(shè)xk是當(dāng)前駐點(diǎn)的近似解，則該點(diǎn)的f(x)函數(shù)線性近似可以表示為 f(x)f(xk)+f”(xk)(x-xk) 令此式為零，得出下一個(gè)近似點(diǎn)為 xk+1=xk-f(xk)/f”(xk) 收斂檢查： 例題: 用牛頓切線法求解 min f(x)=2x2+16/x,2、二次插值法： 用設(shè)f(x)是區(qū)間a,b上的連續(xù)單峰函數(shù)，x1, x2, x3 是該區(qū)間上三個(gè)相鄰點(diǎn)，它們的函數(shù)值分別為f1, f2, f3, 且滿足兩邊大中間小的條件， f1 f2 f3, 求系數(shù) ao, a1, a2, 使得二次函數(shù) q(x)=a0+a1(x-x1)+a2(x-x1)

13、(x-x2) 在這三點(diǎn)上與f(x)的函數(shù)值相等, 可得到所有的系數(shù)。 由dq/dx=0 可得 例題 用二次插值法求解min f(x)=2x2+16/x， 在區(qū)間1, 1.5內(nèi)的最小值。,3-3 多維梯度法,( f ) min f(x) s.t. f : RnR ( f 連續(xù)可微) 取極值的必要條件： 若x*l.opt. f(x*)=0 (駐點(diǎn) ) 說明： f (x) f(x*)+ Tf(x*)(x-x*), x. 故 f (x*) f(x )， x. (由于Tf(x*) =0 ) 1. 最速下降法 方向：在迭代點(diǎn) x(k) 取方向 d(k)= f(x(k) ) 步長: 精確一維搜索,最速下降法

14、（續(xù)） 特點(diǎn)： 1) 全局收斂, 線性收斂; 2) 缺點(diǎn): 易產(chǎn)生扭擺現(xiàn)象而造成早停 (當(dāng)x(k)距最優(yōu)點(diǎn)較遠(yuǎn)時(shí),速度快, 而接近最優(yōu)點(diǎn)時(shí),速度下降) 原因 1： 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) 。 原因 2：,最速下降法的流程,例題3-9 用最速下降法求解:,3 Newton法及其修正 一、 Newton法： 設(shè)f(x)二階可微，取f(x)在x(k)點(diǎn)附近的二階Taylor近似函數(shù)： qk(x)=f(x(k)+Tf(x(

15、k)(x-x(k) + (x-x(k)T2f(x(k)(x-x(k) 求駐點(diǎn)： qk(x)=f(x(k)+2f(x(k)(x-x(k)=0 當(dāng)2f(x(k)正定時(shí)，令上述方程解為x(k+1), 有極小點(diǎn)： Newton迭代公式: x(k+1)=x(k)-2f(x(k) -1f(x(k) 停止條件: |f(x(k)|,Newton法的計(jì)算流程,例題 3-11 用Newton法計(jì)算,Pk+1=-2f(x(k) -1f(x(k),特點(diǎn)： 1) 二階收斂，局部收斂。 （當(dāng)x(k)充分接近x*時(shí), 局部函數(shù)可用正定二次函數(shù)很好地近似，故收斂很快） 2) 當(dāng)f(x)為正定二次函數(shù)時(shí)，從任意初始點(diǎn)可一步迭代

16、達(dá)到最優(yōu)解 說明: 設(shè)f(x)= xTQx+PTx+r , Qnn對(duì)稱正定, P Rn, r R. x(1), f(x(1)=Q x(1) +P 2f(x(1)=Q 迭代： x(2) = x(1) - Q 1(Qx(1) +P) = - Q 1 P (駐點(diǎn)即opt.) 主要缺點(diǎn)： (1)局部收斂 (2)用到二階Hesse陣，且要求正定 (3)需計(jì)算Hesse陣逆或解n階線性方程組，計(jì)算量大,Newton法：（續(xù)）,6、 Newton法的改進(jìn)（續(xù)）-自己閱讀和體會(huì) (1)為減小工作量，取m（正整數(shù)），使每m次迭代使用同一個(gè)Hesse陣，迭代公式變?yōu)椋?x(km+j+1)=x(km+j)-2f(x

17、(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) , 加入線性搜索：min f(x(k)+k d(k) 求得k , x(k+1)=x(k)+kd(k) 特點(diǎn)：可改善局部收斂性，當(dāng)d(k)為函數(shù)上升方向時(shí)，可向負(fù)方向搜索，但可能出現(xiàn) d(k)均非下降方向的情況。,二、算法流程圖,6 共軛梯度法,共軛的概念: 對(duì)于方向pi, pj相對(duì)于nn對(duì)稱正定矩陣Q共軛，則 基本公式: 停止

18、條件:,共軛梯度法算法特點(diǎn),1、全局收斂（下降算法）；線性收斂； 2、每步迭代只需存儲(chǔ)若干向量(適用于大規(guī)模問題)； 3、有二次終結(jié)性（對(duì)于正定二次函數(shù)，至多n次迭代 可達(dá)opt.） 例題 3-10 用共軛梯度法求解,目標(biāo)函數(shù) (f)min f(x), f: R n R 1、基本思想： 用對(duì)稱正定矩陣H(k)近似2f(x(k)的逆 , 而H(k)的產(chǎn)生從給定H(1)開始逐步修整得到。 2、算法框圖：,5 變尺度法,5、變尺度法的主要特點(diǎn)： 只需用到函數(shù)一階梯度 (Newton法用到二階Hesse陣） 下降算法，故全局收斂； 不需求矩陣逆；（計(jì)算量?。?一般可達(dá)到超線性收斂；（速度快） 有二次終

19、結(jié)性。 二 DFP (Davidon(1959),Fletcher and Powell (1963) ) 法: 1、DFP法：以下省去各量上標(biāo)，x, s, y, H 表示第k 步的量， 等表示第k+1步的量。,二、1、DFP法： （續(xù)） Ex. 用DFP法求解 min f(X)= 10 x12+x22 解：取初始點(diǎn)x(1)=(110,1)T, H(1)=I (單位矩陣) 得到如下結(jié)果： （計(jì)算過程見下頁）,2、BFGS法 BFGS ( Broyden(1970), Fletcher (1970), Goldfarb (1970), Schanno(1970) ) 法 主要公式：,BFGS法有變尺度法的全部優(yōu)點(diǎn)，并且在一定條件下可以證明在BFGS法中使用前文中介紹的不精確一維搜索有全局收斂性。,3.4. 多維直接算法