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

1、非線性無(wú)約束規(guī)劃第1頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四1）方向?qū)?shù)設(shè)M0位數(shù)量場(chǎng)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頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四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ì)算其中 是在

2、M0附近的偏導(dǎo)數(shù).例題1 求函數(shù) 在點(diǎn)M(1,0,1)處沿著 方向的方向?qū)?shù)解: 第3頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四3)梯度：根據(jù)方向?qū)?shù)公式可以知道 是其變化率最快的方向, 稱為梯度, 記為Grad u. 如果用 表示l線上的單位矢量, 則方向?qū)?shù)可以寫成梯度的性質(zhì)：1) 方向?qū)?shù)等于梯度在該方向的投影.即2) 數(shù)量場(chǎng)u=u(M)中任一點(diǎn)M處的梯度, 垂直于過(guò)該點(diǎn)的等值面, 且指向u(M)增大的一方.例3 設(shè) 為點(diǎn)M(x,y,z)的矢徑 的模, 試證第4頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四2. 海瑟矩陣 海瑟矩陣是對(duì)稱形式：第5頁(yè)，共45頁(yè)，20

3、22年，5月20日，3點(diǎn)42分，星期四3 非線性規(guī)劃問(wèn)題的展開形式 多元函數(shù)泰勒公式的矩陣形式：其中線性函數(shù)：f (X) = CTX + B = ci xi + B二次函數(shù)：f (X) = (1/2) XTQX + CTX + Bf (x) = f (x*)+ f T(x)(x-x*) + (1/2)(x-x*)T 2f (x*)(x-x*) + ox-x*2第6頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四4 凸集、凸函數(shù)和凸規(guī)劃1）凸函數(shù) 定義: 設(shè)集合 S Rn 為凸集，函數(shù) f :SR 若 x(1), x(2) S, ( 0 , 1 ) ，均有 f( x(1)(1- ) x(

4、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) 為凹函數(shù)（嚴(yán)格凹函數(shù)）。嚴(yán)格凸函數(shù)凸函數(shù)嚴(yán)格凹函數(shù)第7頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四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)= m

5、ax f1(x) , f2 (x) , g(x)= min f1(x) , f2 (x) 是否凸函數(shù)？ 凸規(guī)劃=凸可行集+凸目標(biāo)函數(shù)第8頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四凸函數(shù)與凹函數(shù)(續(xù))凸函數(shù)的判定: 如果函數(shù)f (X)的Hesse矩陣處處半正定，則f (X)為凸函數(shù)，若f (X)正定，則f (X) 為嚴(yán)格凸函數(shù)。注: 該命題的逆命題不成立例題 檢驗(yàn)函數(shù)的凸性。第9頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四無(wú)約束問(wèn)題的最優(yōu)性條件1. 必要條件：若X*是函數(shù)f(X)的局部最大點(diǎn)，則在該點(diǎn)必有f(X*)=0以及Hesse矩陣2f(X*)半正定 定義: 對(duì)于可

6、微函數(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)；(閱讀課本的例題)第10頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四6 最優(yōu)化問(wèn)題的數(shù)值解 VS 解析解1. 解析解與數(shù)值解 注意獲得解析解的困難性。2、收斂性概念： 考慮(fs)設(shè)迭代算法產(chǎn)生點(diǎn)列x(k) S.1) 算法的理想收斂：設(shè)x*S是(fs)的最優(yōu)解，如果x*x(k)，或

7、者雖然 x(k) x*， 但是k，滿足 則稱算法收斂到最優(yōu)解 x*。 第11頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四 概念: 1) 局部最優(yōu): 2) 全局最優(yōu): 3) 嚴(yán)格全局最優(yōu) 以及 4) 全局收斂： 對(duì)任意初始點(diǎn)x(1), 算法均收斂。 5) 局部收斂： 當(dāng)x(1) 充分接近解x*時(shí)，算法才收斂。第12頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四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) (為給定實(shí)數(shù),稱為閾值 當(dāng)下列情況之一成立時(shí)，稱算

8、法收斂： 1x(k) S*; 2k，X(k)任意極限點(diǎn)S*第13頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四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í)有第14頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四定理：設(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*

9、 | 并令k，利用超線性收斂定義可得結(jié)果。8、收斂速度（續(xù)）第15頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四4.1 常用的搜索算法結(jié)構(gòu) 考慮（fs） 常用一種線性搜索的方式構(gòu)造xk序列來(lái)求解 迭代中從一點(diǎn)出發(fā)沿下降可行方向找一個(gè)新的、更優(yōu)的點(diǎn)。下降方向 ： 設(shè) S，d Rn,d0,若存在 ，使 ，稱d 為 在 點(diǎn)的下降方向。min f(x) s.t. xS第16頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四4 常用的搜索算法結(jié)構(gòu)可行方向： 設(shè) S，dRn, d0, 若存在 使 ， 稱d 為該點(diǎn)的可行方向。同時(shí)滿足上述兩個(gè)性質(zhì)的方向稱 下降可行方向。第17頁(yè)，共45頁(yè)，2

10、022年，5月20日，3點(diǎn)42分，星期四迭代算法的停止標(biāo)準(zhǔn)1）2）3） 對(duì)于無(wú)約束問(wèn)題可以用第18頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四10 常用的搜索算法結(jié)構(gòu)線性搜索求 ，新點(diǎn)使x(k+1)S初始x(1) S, k =1對(duì)x(k)點(diǎn)選擇下降可行方向d(k)是否滿足停機(jī)條件？停k=k+1yesno第19頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四11 一維搜索一元函數(shù)求極小及線性搜索均為一維搜索。常用于求： min f(x(k)+ d(k)=( ) s.t. S S有3種情況（-，+）或（0， + ）或a,b一、縮小區(qū)間的精確一維搜索：考慮問(wèn)題(P) min (

11、) s.t. , 為此先介紹不確定區(qū)間及單峰函數(shù)的概念 不確定區(qū)間：, 含()的最小點(diǎn)， 但不知其位置第20頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四單峰的概念一、縮小區(qū)間的精確一維搜索（續(xù)） 若對(duì)任意1 ,2, 1 ( 2); 2 若 1 * ，則( 1) ( 2).則稱( )在, 上強(qiáng)單峰。 若只有當(dāng)( 1) ( * )， ( 2) ( * )時(shí)，上述1, 2 式才成立，則稱( )在, 上單峰。 * 1 2 強(qiáng)單峰 * 單峰第21頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四 設(shè)f(X)是目標(biāo)函數(shù)，如果 是在給定Xk和方向矢量Pk下，通過(guò)f(x)=f(xk+akPk

12、) 的極小化而產(chǎn)生則稱 為最優(yōu)步長(zhǎng)。 根據(jù)單變量的駐點(diǎn)條件:以及復(fù)合函數(shù)的求導(dǎo)法則可得：1. 精確一維搜索（假定求目標(biāo)函數(shù)極小值）第22頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四2 一維搜索一、縮小區(qū)間的精確一維搜索（續(xù)） 定理： 設(shè)：RR 在， 上單峰，x1 x2 。 那么 1若(x1) (x2)，則去除 ， x2 ；如左下圖 2若(x1)(x2)， 則 去除x2，；如右下圖 x1 x2 x1 x2 第23頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四12 一維搜索2、黃金分割法（0.618 法） 選二點(diǎn)x10, k=12) 計(jì)算初始分割點(diǎn)，x1=a+0.382L,

13、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) 若f1=f2, 置b=x2, x2=x1, a=a, f2=f1, x1=a+b-x2, f1=f(x1)4) 收斂檢查；如果(b-a)/L= , 則按照下面方式輸出結(jié)果： 若f1lg /log 0.618例題 用黃金分割法求解 min f(x)=x2-6x+10第25頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四牛頓-拉夫遜法(牛頓切線法) 為了找到導(dǎo)數(shù)函數(shù)對(duì)應(yīng)的駐點(diǎn)，采用根近似

14、假設(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第26頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四2、二次插值法： 用設(shè)f(x)是區(qū)間a,b上的連續(xù)單峰函數(shù)，x1, x2, x3 是該區(qū)間上三個(gè)相鄰點(diǎn)，它們的函數(shù)值分別為f1, f2, f3, 且滿足兩邊大中間小的條件， f1 f20, k=1| f(x(k) ) |0得 x(k+1)=x(k)+kd(k)k=k+1例題3-9 用

15、最速下降法求解:第30頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四3 Newton法及其修正一、 Newton法： 設(shè)f(x)二階可微，取f(x)在x(k)點(diǎn)附近的二階Taylor近似函數(shù)： qk(x)=f(x(k)+Tf(x(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)|0, k=1 x(k+1)=x(k)+p(k)

16、|f(x(k)|0d(1)=- f(x(1),k=1k=k+1k=1| f(x(k)|0得 k x(k+1)=x(k)+k d(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頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四6 共軛梯度法共軛的概念: 對(duì)于方向pi, pj相對(duì)于nn對(duì)稱正定矩陣Q共軛，則基本公式:停止條件:第36頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四共軛梯度法算法特點(diǎn)1、全局收斂（下降算法）；線性收斂；2、每步迭代只需存儲(chǔ)若干向量(適用于大規(guī)模問(wèn)題)；3、

17、有二次終結(jié)性（對(duì)于正定二次函數(shù)，至多n次迭代 可達(dá)opt.）例題 3-10 用共軛梯度法求解第37頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四 目標(biāo)函數(shù) (f)min f(x), f: R n 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)+ k d(k)|x(k+1)-x(k)|0,(單純形法中 =1) 2 擴(kuò)展：給定擴(kuò)展系數(shù) 1,計(jì)算。（加速）第44頁(yè)，共45頁(yè)，2022年，5月20日，3點(diǎn)42分，星期四 若f(y(1) f(y(2), 那么y(