應(yīng)用數(shù)學我的光盤課件ctex ch

1、最優(yōu)化方法及其程序設(shè)計2010 年 3 月 22 日目錄第一章1.11.21.31.41.51.61138152226最優(yōu)化問題的數(shù)學模型 . . . . . . . . . . . . . . . . . . . . . .向量和矩陣范數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . .函數(shù)的可微性與展開 . . . . . . . . . . . . . . . . . . . . . . .凸集與凸函數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . .無約束問題的最優(yōu)性條件.

2、. . . . . . . . . . . . . . . . . . .無約束優(yōu)化問題的算法框架 . . . . . . . . . . . . . . . . . . .ii第一章1.1最優(yōu)化問題的數(shù)學模型通俗地說，所謂最優(yōu)化問題，就是求一個多元函數(shù)在某個給定集合上的極值. 幾乎所有類型的最優(yōu)化問題都可以用下面的數(shù)學模型來描述:min (),(1.1)s.t. ,這里， 是某個給定的集合(稱為可行集或可行域)，() 是定義在集合 上的實值函數(shù). 此外，在模型 (1.1) 中， 通常稱為決策變量, s.t. 是subject to (受限于) 的縮寫.1第一章回目錄1.1最優(yōu)化問題的數(shù)學模型

3、人們通常按照可行集的性質(zhì)對最優(yōu)化問題 (1.1)進行一個大致的分類:線性規(guī)劃和非線性規(guī)劃. 可行集是有限中的一個子集;組合優(yōu)化或網(wǎng)絡(luò)規(guī)劃. 可行集中的元素是有限的;動態(tài)規(guī)劃. 可行集是一個依賴時間的決策序列;最優(yōu)控制. 可行集是無窮中的續(xù)子集.本書主要考慮在工程設(shè)計中有著重要應(yīng)用的非線性規(guī)劃，其數(shù)學模型為min (),s.t. () = 0, = 1, , ,() 0, = 1, , ,(1.2)(1.3)(1.4)其中，(), () ( = 1, , ) 及() ( = 1, , ) 都是定義在R 上 2 第一章回目錄1.2向量和矩陣范數(shù)連續(xù)可微的多值函數(shù), 且至少有一個是非線性的.記 =

4、: () = 0, = : () 0.(1.5)若指標集 = , 稱之為無約束優(yōu)化問題，否則稱為約束優(yōu)化問題.特別地, 把 = 且 = 的優(yōu)化問題稱為等式約束優(yōu)化問題; 而把 = 且 = 的優(yōu)化問題稱為不等式約束優(yōu)化問題. () 稱為目標函數(shù),(), () ( = 1, , ; = 1, , ) 稱為約束函數(shù). 此外，通常把目標函數(shù)為二次函數(shù)而約束函數(shù)都是線性函數(shù)的優(yōu)化問題稱為二次規(guī)劃；而目標函數(shù)和約束函數(shù)都是線性函數(shù)的優(yōu)化問題稱為線性規(guī)劃.1.2向量和矩陣范數(shù)在算法的收斂性分析中，需要用到向量和矩陣范數(shù)的概念及其有關(guān)理論.設(shè)R 表示實 維向量空間，R 表示實 階矩陣全體所組成的線性空間. 在

5、這兩個空間中，分別定義向量和矩陣的范數(shù). 3 第一章回目錄1.2向量和矩陣范數(shù)向量 R 的范數(shù) 是一個非負數(shù)，它必須滿足以下條件：（1） 0， = 0 = 0;（2） = |, R;（3） + + .向量 = (1, , ) 的-范數(shù)定義為()1|=.(1.6)=1常用的向量范數(shù)有1-范數(shù)：1=| |;=1()1222-范數(shù)：=| |;2=1-范數(shù)： =max |.1矩陣 R 的范數(shù)是一個非負實數(shù)，它除了滿足跟向量范數(shù)相似的三條性質(zhì)之外，還必須具備乘法性質(zhì)： 4 第一章回目錄1.2向量和矩陣范數(shù), R.（4） ,如果一矩陣范數(shù) 相對于某向量范數(shù) 滿足下面的不等式（5） , R,則稱矩陣范數(shù) 和

6、向量范數(shù) 是相容的. 進一步，若存在 =0 使成立= max R,= max ,(1.7)=0=1則稱矩陣范數(shù) 是由向量范數(shù) 誘導(dǎo)出來的算子范數(shù)，簡稱算子范數(shù)，有時也稱為從屬于向量范數(shù) 的矩陣范數(shù). 此時向量范數(shù)和算子范數(shù)通常采用相同的符號 .不難驗證，從屬于向量范數(shù), 1, 2 的矩陣范數(shù)分別為 =max|,1 =11 = 1max|, =1 5 第一章回目錄1.2向量和矩陣范數(shù)2 = max | ( ),它們分別稱作行和范數(shù)、列和范數(shù)和譜范數(shù).本書在各種迭代算法的收斂性時，通常采用譜范數(shù)和按下述方式定義的F-范數(shù):()1/2 2=tr( ) =(1.8)=1 =1現(xiàn)在()=1來 R，則向量

7、序列和矩陣序列的收斂性.知道， 若()()= lim = 1, , .lim= ,類似地，若()=1 ，則()()lim= lim= , = 1, , .為了利用范數(shù)來描述上述極限，必須建立向量范數(shù)的等價定理以及矩陣范數(shù)的等價定理. 6 第一章回目錄1.2向量和矩陣范數(shù)1.1 (1) 設(shè) 和 是定義在 上的兩個向量范數(shù)，則存定理在兩個正數(shù) 1, 2，對所有 R 均成立1 2.(2) 設(shè) 和 是定義在 R 上的兩個矩陣范數(shù)，則存在兩個正數(shù) 1, 2，對所有 R 均成立1 2.下面，斂性.利用范數(shù)的概念來等價地定義向量序列和矩陣序列的收定理 1.2 (1) 設(shè) () 為 維向列序列， 為定義在 R

8、 上的向量范數(shù)，則()()= lim = 0;lim(2) 設(shè)() 為 矩陣序列， 為定義在R 上的向量范數(shù)， 7 第一章回目錄1.3函數(shù)的可微性與展開則()() = 0.= limlim1.3函數(shù)的可微性與展開本節(jié)主要介紹后文經(jīng)常需要用到 元函數(shù)的一階和二階導(dǎo)數(shù)以及泰勒展開式.函數(shù) (), 其中自變量 = (1, , )定義 1.1 設(shè)有 R. 稱向量() () () ()() =, ,(1.9) 8 12第一章回目錄1.3函數(shù)的可微性與展開為 ()在 處的一階導(dǎo)數(shù)或梯度.稱矩陣2 ()2 ()2 () 212 ()1 ()1222 ()2221.2 ()2.2 () () =(1.10)2

9、.2 () 212為 ()在 處的二階導(dǎo)數(shù)或 Hesse矩陣. 若梯度 () 的每個分量函數(shù)在 都連續(xù), 則稱 在 一階連續(xù)可微；若Hesse 陣2() 的各個分量函數(shù)都連續(xù)，則稱 在 二階連續(xù)可微.若 在開集 的每一點都連續(xù)可微，則稱 在 上一階連續(xù)可微；若 在開集 的每一點都都二階連續(xù)可微，則稱 在 連續(xù)可微. 9 上二階第一章回目錄1.3函數(shù)的可微性與展開由上述定義不難發(fā)現(xiàn)，若 在 二階連續(xù)可微，則2 ()2 (), = 1, 2, , ,=, 即Hesse 陣2() 是對稱陣.例 1.1 設(shè)二次函數(shù)1 () = +,2是對稱陣. 那么，不難計算它在 的梯度及Hesse其中 R, 為 R

10、2() = + , () = .展開). 設(shè)函數(shù) : R R 連續(xù)可微，那么例1.2 (1 ( + ) = () +( + ) d0= () + ( + ) , (0, 1)= () + () + (). 10 第一章回目錄1.3函數(shù)的可微性與展開進一步, 若函數(shù) 是二次連續(xù)可微的, 則有121212 () + () + () + () + () + () +(1 ) ( + )d ( + )=0 2( + ), () + ( (0, 1)=22 )=及12( + ) = () + ( + ) d02= () + ( + ) , (0, 1)2= () + () + ().下面簡單介紹一下向量

11、值函數(shù)的可微性及中值定理. 設(shè)有向量值函數(shù) = (1, 2, , ) : R R. 若每個分量函數(shù) 都是(連續(xù)) 可微的，則稱 是 (連續(xù)) 可微的. 向量值函數(shù) 在 的導(dǎo)數(shù) R 11 第一章回目錄1.3函數(shù)的可微性與展開是指它在 的Jacobi 矩陣, 記為 () 或 (), 即1()1()1() 12 () () ()22212 () := () :=.().()() 12考慮到標量函數(shù)的梯度定義, 有時也把向量函數(shù)稱為 在 的梯度，記為的Jacobi 矩陣的轉(zhuǎn)置 () = ()= (1(), 2(), , ().不難發(fā)現(xiàn)，例 1.2 中關(guān)于多函數(shù)的一些結(jié)論可以推廣到向量值函數(shù)的情形. 例

12、如，若向量值函數(shù) : R R 是連續(xù)可微的，則對于任意 12 第一章回目錄1.3函數(shù)的可微性與展開的, R, 有1 ( + ) = () + ( + ) d.0對于向量值函數(shù) , 也可以定義Lipschitz 連續(xù)性的概念.R R, R, 稱 在 是定義 1.2 設(shè)向量值函數(shù) :Lipschitz 連續(xù)的，是指存在常數(shù) 0, 使得對任意的 R, 滿足 () () ,(1.11)其中, 稱為 Lipschitz 常數(shù). 若 (1.11) 式對任意的 , R 都成立, 則稱 在 R 內(nèi)是 Lipschitz 連續(xù)的.在迭代法的收斂性分析中, 有時需要用到向量值函數(shù)的“中值定理”, 現(xiàn)引述如下.定理

13、 1.3 設(shè)向量值函數(shù) : R R 連續(xù)可微, 那么 13 第一章回目錄1.3函數(shù)的可微性與展開對任意的 , R, 有(1) () () sup ( + ( ) .01對任意的 , , R, 有 () () ()( )(2)sup ( + ( ) () .01由上述定理的結(jié)論(2) 可推得下面的結(jié)論.推論 1.1 設(shè)向量值函數(shù) : R R 是連續(xù)可微的, 且其Jacobi 矩陣是 Lipschitz 連續(xù)的, 即存在常數(shù) 0 () () ,使得 , R.(1.12)則對任意的 , R, 有1 ( + ) () () 2 .(1.13)2 14 第一章回目錄1.4凸集與凸函數(shù)1.4凸集與凸函數(shù)本

14、節(jié)介紹凸集、錐和多面體的有關(guān)概念.定義 1.3 設(shè)集合 R. 稱集合 為凸集, 是指對任意的, 及任意的實數(shù) 0, 1, 都有 + (1 ) .由上述定義不難知道凸集的幾何意義. 即對非空集合 R,接其中任意兩點的線段仍屬于該集合，則稱該集合 為凸集.不難證明凸集的下列基本性質(zhì).若連引理 1.1 設(shè) , 1, 2 是凸集， 是一實數(shù), 那么(1) = | = , 是凸集.(2) 交集 1 2 是凸集.(3) 和集 1 + 2 = | = + , 1, 2 也是凸集. 15 第一章回目錄1.4凸集與凸函數(shù)例 1.3 維歐氏空間中的 個點的凸組合是一個凸集.即集合 R , 0, = = 1=1=1

15、是凸集.例 1.4 維歐氏空間中的超平面 = = 是一個凸集其,中 R, R0 是超平面的法向量. 此外, 下面的四個半空間+= | ,= | ,= | ,= | 0，有 , 則稱 為一個錐 (cone). 若 同時也是凸集, 則稱 為一個凸錐 (convex cone). 此外, 對于錐 , 若 0 , 則稱 是一個尖錐ed cone). 相應(yīng)地, 包含 0 的凸錐稱為尖凸錐.(po例 1.6 多面體 R| 0 是一個尖凸錐, 通常稱之為多面錐(polyhedral cone). 17 第一章回目錄1.4凸集與凸函數(shù)例 1.7 集合R:= R| 0, = 1, 2, , +是一個尖凸錐, 通

16、常稱之為非負錐 (nonnegative ornt). 相應(yīng)地, 凸錐R:= R| 0, = 1, 2, , nt).+稱為正錐(itive or有了凸集的概念之后，就可以定義凸集上的所謂凸函數(shù).定義 1.6 設(shè)函數(shù) : R R, 其中 為凸集.(1)稱 是 上的凸函數(shù), 是指對任意的 , 及任意的實數(shù) 0, 1, 都有 ( + (1 ) () + (1 ) ().(2) 稱 是 上的嚴格凸函數(shù), 是指對任意的 , , = 及任意的實數(shù) 0, 1, 都有 ( + (1 ) 0, 使對任意的12 ( + (1 ) +(1 ) () + (1 ) ().2凸函數(shù)具有下列基本性質(zhì).命題 1.1 設(shè)

17、, 1, 2 都是凸集 上的凸函數(shù),則有(1) 1() + 22() 也是 上的凸函數(shù).(2) 水平集(, ) = | , () 是凸集.1, 2 R+, R,凸集和凸函數(shù)在優(yōu)化理論中起著舉足輕重的作用, 但是利用凸函數(shù)的定義來判斷一個函數(shù)是否具有凸性并非一件容易的事情. 如果函數(shù)是一階或二階連續(xù)可微的, 則可利用函數(shù)的梯度或Hesse 陣來判別或驗證函數(shù)的凸性要相對容易一些. 下面給出幾個判別定理. 19 第一章回目錄凸集與凸函數(shù)1.41.4設(shè) 在凸集 R 上一階連續(xù)可微，則在 上為凸函數(shù)的充要條件是定理(1) () (*) + (*) ( *), *, .(1.14)在 上嚴格凸的充要條件

18、是，當 = 時，成立(2) () (*) + (*) ( *), *, .(1.15)在 上一致凸的充要條件是，存在常數(shù) 0，使對任意的(3)*, ，成立 () (*) + (*) ( *) + *2.(1.16)知道， 在一元函數(shù)中， 若 () 在區(qū)間 (, ) 上二階可微且 () 0 ( 0)，則 () 在 (, ) 內(nèi)凸（嚴格凸）.對于二階連續(xù)可微的多元函數(shù) : R R, 也可以由其二階導(dǎo)數(shù) (Hesse 陣) 給出凸性的一個近乎完整的表述. 20 第一章回目錄1.4凸集與凸函數(shù)定義 1.7設(shè) 函數(shù) 在凸集 上是二階連續(xù)可微的. 若對一切 , 有 2() 0，則稱 2 在點 處是定的.

19、若對一切0 = R, 有 2() 0，則稱 2 在點 處是正定的. 進一步，若存在常數(shù) 0, 使得對任意的 R, , 有 2() 2，則稱 2 在 上是一致正定的.有了上述定義，果推廣到多元函數(shù)上.可以把一元函數(shù)關(guān)于用二階導(dǎo)數(shù)表述凸性的結(jié)函數(shù) 在凸集 R 上二階連續(xù)可微,定理 1.5設(shè) 則定； 在 上是凸的充要條件是 2() 對一切 為(1)(2)定；(3)正定. 在 上是嚴格凸的充分條件是 2() 對一切 為正 在 上是一致凸的充要條件是 2() 對一切 為一致注意，2 正定是 嚴格凸的充分條件而非必要條件. 21 第一章回目錄1.5無約束問題的最優(yōu)性條件1.5無約束問題的最優(yōu)性條件本節(jié)無約

20、束優(yōu)化問題min ()(1.17)的最優(yōu)性條件, 它包含一階條件和二階條件.分為全局極小點和局部極小點.定義 1.8 若對于任意的 R, 都有 (*) (),首先給出極小點的定義, 它則稱 *為 的一個全局極小點. 若上述不等式嚴格成立且 = *, 則稱的一個嚴格全局極小點.*為 定義 1.9 若對于任意的 (*, ) = R| * 0 為某個常數(shù). 若上述不等式嚴格成立且 = *, 則稱 * 為 的一個嚴格局部極小點.由上述定義可知, 全局極小點一定是局部極小點, 反之不然. 一般來說, 求全局極小點是相當?shù)? 因此通常只求局部極小點 (在實際應(yīng)用中, 有時求局部極小點已滿足了問題的要求).

21、 故本書所的方法都是指局部極小點.的求極小點為了和敘述的方便, 通篇引入下列記號:2 = (),() = (),2 = ().() = (),定理1.6 (一階必要條件)設(shè) () 在開集 上一階連續(xù)可微.若* 證是 (1.17) 的一個局部極小點, 則必有 (*) = 0.取 = * (*) , 其中 0 為某個常數(shù). 則有 () = (*) + (*) ( *) + ( *)= (*) (*) (*) + ()= (*) (*)2 + (). 23 第一章回目錄1.5無約束問題的最優(yōu)性條件注意到() (*) 及 0,有().0 (*)2 上式兩邊令 0 得(*) = 0, 即(*) = 0.

22、 定理 1.7 (二階必要條件)設(shè) () 在開集 上二階連續(xù)可微. 若* 是(1.17) 的一個局部極小點, 則必有(*) = 0 且(*) 是定矩陣.證 設(shè)* 是一局部極小點, 那么由定理 1.6 可知(*) = 0. 下面只需證明(*) 的展開式得定性. 任取 = * + , 其中 0 且 R.由1*2 *20 () ( ) = ( ) + ( ),2即(22)*( ) + 0.2對上式令 0, 即得 (*) 0, 從而定理成立. 24 第一章回目錄1.5無約束問題的最優(yōu)性條件定理 1.8 (二階充分條件)設(shè) ()在開集 上二階連續(xù)可微. 若* 滿足條件 (*) = 0 及 (*) 是正定

23、矩陣, 則 * 是 (1.17) 的一個局部極小點.證 任取 = * + , 其中 0 且 R. 由公式得1* 2 * (+ ) = ( ) + ( ) + (+ ),2其中 (0, 1). 注意到(*) = 0, (*) 正定和 二階連續(xù)可微, 故存在 0, 使得(* + ) 在 (*), 從而定理成立.一般來說, 目標函數(shù)的穩(wěn)定點不一定是極小點. 但對于目標函數(shù)是凸函數(shù)的無約束優(yōu)化問題, 其穩(wěn)定點、局部極小點和全局極小點三者是等價的.1.9 設(shè) () 在 R 上是凸函數(shù)并且是一階連續(xù)可微的.定理則* R 是 (1.17) 的全局極小點的充要條件是 (*) = 0. 25 第一章回目錄1.6

24、無約束優(yōu)化問題的算法框架證 只需證明充分性, 必要性是顯然的. 設(shè)(*) = 0. 由凸函數(shù)的判別定理 1.4(1), () (*) + (*) ( *) = (*), R,這表明* 是全局極小點. 1.6無約束優(yōu)化問題的算法框架在數(shù)值優(yōu)化中, 一般采用迭代法求解無約束優(yōu)化問題min ()(1.18)的極小點. 迭代法的基本是: 給定一個初始點0, 按照某一迭代規(guī)則產(chǎn)生一個迭代序列. 使得若該序列是有限的, 則最后一個點就是問題(1.18) 的極小點; 否則, 若序列 是無窮點列時, 它有極限點且這個極限點即為問題 (1.18) 的極小點. 26 第一章回目錄1.6無約束優(yōu)化問題的算法框架設(shè) 為第 次迭代點,子, 則第 次迭代完成后 為第 次搜索方向, 為第 次步長因到新一輪(第 + 1 次) 的迭代點+1= + .(1.19)因此,可以寫出求解無約束優(yōu)化問題(1.18) 的一般算法框架如下.算法 1.1 ( 無約束問題的一般算法框架)步 0步 1步 2步 3步 4給定初始化參數(shù)及初始迭代點 0. 置 := 0.若 滿足某種終止準則, 停止迭代, 以 作為近似極小點.通過求解 處的某個子問題確定下降方向 .通過某種搜索方式確定步長因子 , 使得( +) 0, 使得對任意的 (0, 和 = 0, 有 ( + ) ().則稱