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

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

3、22年，5月20日，3點42分，星期四3 非線性規(guī)劃問題的展開形式 多元函數(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頁，共45頁，2022年，5月20日，3點42分，星期四4 凸集、凸函數(shù)和凸規(guī)劃1）凸函數(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ù)。 若進一步有上面不等式以嚴格不等式成立，則稱 f(x) 為凸集 S 上的嚴格凸函數(shù)。性質: 當- f(x) 為凸函數(shù)（嚴格凸函數(shù)）時，則稱 f(x) 為凹函數(shù)（嚴格凹函數(shù)）。嚴格凸函數(shù)凸函數(shù)嚴格凹函數(shù)第7頁，共45頁，2022年，5月20日，3點42分，星期四2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)) 定理： f(x) 為凸集 S 上的凸函數(shù) S 上任意有限點的凸組合的函數(shù)值不大于各點函數(shù)值的凸組合。思考：設f1, f2是凸函數(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ī)劃=凸可行集+凸目標函數(shù)第8頁，共45頁，2022年，5月20日，3點42分，星期四凸函數(shù)與凹函數(shù)(續(xù))凸函數(shù)的判定: 如果函數(shù)f (X)的Hesse矩陣處處半正定，則f (X)為凸函數(shù)，若f (X)正定，則f (X) 為嚴格凸函數(shù)。注: 該命題的逆命題不成立例題 檢驗函數(shù)的凸性。第9頁，共45頁，2022年，5月20日，3點42分，星期四無約束問題的最優(yōu)性條件1. 必要條件：若X*是函數(shù)f(X)的局部最大點，則在該點必有f(X*)=0以及Hesse矩陣2f(X*)半正定 定義: 對于可

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

7、者雖然 x(k) x*， 但是k，滿足 則稱算法收斂到最優(yōu)解 x*。 第11頁，共45頁，2022年，5月20日，3點42分，星期四 概念: 1) 局部最優(yōu): 2) 全局最優(yōu): 3) 嚴格全局最優(yōu) 以及 4) 全局收斂： 對任意初始點x(1), 算法均收斂。 5) 局部收斂： 當x(1) 充分接近解x*時，算法才收斂。第12頁，共45頁，2022年，5月20日，3點42分，星期四2. 實用收斂性： 定義解集 S* = x | x 具有某種性質 例：S*=x|x-g.opt S*=x|x-l.opt S*=x| f(x)=0 S*=x|f(x) (為給定實數(shù),稱為閾值 當下列情況之一成立時，稱算

8、法收斂： 1x(k) S*; 2k，X(k)任意極限點S*第13頁，共45頁，2022年，5月20日，3點42分，星期四8. 收斂速度 設算法產(chǎn)生點列x(k), 收斂到解x*, 且x(k)x*， k，1.線性收斂： 當k充分大時成立2.超線性收斂： 3.二階(次)收斂： 0，當k充分大時有第14頁，共45頁，2022年，5月20日，3點42分，星期四定理：設算法點列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，利用超線性收斂定義可得結果。8、收斂速度（續(xù)）第15頁，共45頁，2022年，5月20日，3點42分，星期四4.1 常用的搜索算法結構 考慮（fs） 常用一種線性搜索的方式構造xk序列來求解 迭代中從一點出發(fā)沿下降可行方向找一個新的、更優(yōu)的點。下降方向 ： 設 S，d Rn,d0,若存在 ，使 ，稱d 為 在 點的下降方向。min f(x) s.t. xS第16頁，共45頁，2022年，5月20日，3點42分，星期四4 常用的搜索算法結構可行方向： 設 S，dRn, d0, 若存在 使 ， 稱d 為該點的可行方向。同時滿足上述兩個性質的方向稱 下降可行方向。第17頁，共45頁，2

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

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

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

13、f1=f(x1); x2=a+0.618L, f2=f(x2)3) 消去大端值，計算新的分割點： 若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= , 則按照下面方式輸出結果： 若f1lg /log 0.618例題 用黃金分割法求解 min f(x)=x2-6x+10第25頁，共45頁，2022年，5月20日，3點42分，星期四牛頓-拉夫遜法(牛頓切線法) 為了找到導數(shù)函數(shù)對應的駐點，采用根近似

14、假設xk是當前駐點的近似解，則該點的f(x)函數(shù)線性近似可以表示為 f(x)f(xk)+f”(xk)(x-xk)令此式為零，得出下一個近似點為 xk+1=xk-f(xk)/f”(xk)收斂檢查：例題: 用牛頓切線法求解 min f(x)=2x2+16/x第26頁，共45頁，2022年，5月20日，3點42分，星期四2、二次插值法： 用設f(x)是區(qū)間a,b上的連續(xù)單峰函數(shù)，x1, x2, x3 是該區(qū)間上三個相鄰點，它們的函數(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頁，共45頁，2022年，5月20日，3點42分，星期四3 Newton法及其修正一、 Newton法： 設f(x)二階可微，取f(x)在x(k)點附近的二階Taylor近似函數(shù)： qk(x)=f(x(k)+Tf(x(k)(x-x(k) + (x-x(k)T2f(x(k)(x-x(k) 求駐點： qk(x)=f(x(k)+2f(x(k)(x-x(k)=0 當2f(x(k)正定時，令上述方程解為x(k+1), 有極小點： 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頁，共45頁，2022年，5月20日，3點42分，星期四6 共軛梯度法共軛的概念: 對于方向pi, pj相對于nn對稱正定矩陣Q共軛，則基本公式:停止條件:第36頁，共45頁，2022年，5月20日，3點42分，星期四共軛梯度法算法特點1、全局收斂（下降算法）；線性收斂；2、每步迭代只需存儲若干向量(適用于大規(guī)模問題)；3、

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