北郵最優(yōu)化理論與算法PPT課件：8_算法

1、最優(yōu)化理論與算法8， 算法第八章 算法 算法概念 算法收斂問題ch8 算法-概念 8.1.1 算法映射( )(1)( )a,k1k,kkkxxx,即從一點出發(fā), 按照某種規(guī)則 求出后繼點用代替重復以上過程 便產(chǎn)生點列迭代下降，即對某個函數(shù)，在每次迭代中后繼點處的函數(shù)值要有所減小。迭代下降算法考慮極小化問題 f(x) s.t. x s 這里f是目標函數(shù)，s是可行域。對于求解這一問題的解答程序或算法可以看作是一個迭代過程，這過程按照規(guī)定的一組指令和終止準則一起產(chǎn)生一個點序列。ch8 算法概念df 8.1.1 算法a是定義在空間x上的點到集映射,即對每一個點xx,給定一個子集a(x)x.111211

2、.,.,.,().kkkkkkxxxx xkxxxxxaax每一點指定到 的一個給出一個向量應用算法指令，我們就得到一個新的點這個過程可用一個來描述。此映射一般是一個的映射，它把定義域 中的。于是，給出一個初始點 ，算法映射生成一系列的點其中對每一通過這一映射構(gòu)造子集算法映射點到集，的迭代算法把 變成ch8 算法-概念2 min . . 11 nlp xstx 例 考慮如下1*1( )(1)/2*144, 2.5, 1.75, 1.375, 1.1875,. , xa xxaxx最優(yōu)解顯為 設點到點的算法映射為則容易驗證，應用映射 ，對任何初始點所得到的序列都收斂于最優(yōu)解例如，當算法生成序列1

3、,(1)/2,1( )(1)/2,1,1xxa xxax點到若定義算法映射為的映射 如定義算法 為集合 若 若ch8 算法概念如圖所示,應用算法a時,經(jīng)a作用得到一個閉區(qū)間,從此區(qū)間中任取一點作為后繼點,重復這個過程,得一由算法產(chǎn)生得點列,在一定條件下,它收斂于問題的解.如3,2,3/2,5/4, 3,3/2,9/8,33/32, etc.x*=1xk+1xkxk+1a(x)x*=1xk+1xkxk+1a(x)ch8 算法概念 8.1.2 解集合 min ( ) x sf x考慮為了求解上述問題，要求使用的算法具有這樣的性質(zhì)： 由算法產(chǎn)生的點列收斂于整體最優(yōu)解然而，在許多情形下，要滿足這一點很

4、難做到。事實上由于非凸性，問題的規(guī)模和其它一些困難，達到整體最優(yōu)幾乎不可能，因此當達到屬于預定集的某一點達到，則可以停止迭代，這個預定集就稱之為解集合常用的解集合有如下幾種類型ch8 算法概念1, *:*2 *: *( *),3 *: *( *),4 *: *( *)( ),50 * ( )0: *xxxxsf xbxxsf xlbxxsf xblblagrangeff xxxx 是一個可接受的目標值其中是允許限， 是最優(yōu)目 是問題的一個局部最優(yōu)解，標值的下界，一個典型的下界是 對偶問題的目標值其中是整體最小值， 是指定，的，值，是6 *: *kktxxsfj 點，是點ch8 算法概念 8.1

5、.3 下降函數(shù)1.21,( ), ( )( )2,( ),( ), ( )( )dfxya xyxxyaxaxxyxxxa 當且時 設為解集合為 上的一個算法是定義在 上的連續(xù)實函數(shù) 若滿足則稱 是關(guān)于解集合 和算法 的下降函且數(shù)當時,:min( ). .,( )( )nlpf xst xsf xf x一般地 當求解 時 通常取或作為下降函數(shù)ch8 算法概念 8.1.4 閉映射( )( )( )( )( ) 8.1.3:, (),z ,( )zxapqkkkkkaxdfxyrra xyxx xxya xyyyxaa x 設 和 分別是空間和中的非空閉集。為點到集映射，若蘊含則稱。如果映射 在集

6、合上每一點是映射 在處是閉的映射在集閉的，則合稱上是閉的ch8 算法概念3,1,242( )1(1),2xxxa xxx若2若2義義為為設是整體最優(yōu)解的集合，即=1?？紤]算法映射，定義為2 min . . 11 xstx 重新考慮例映射在下圖中說明ch8 算法概念此例表明算法在區(qū)間此例表明算法在區(qū)間(- ,2)上上收斂于集收斂于集 中點，而在中點，而在2， )上卻不收斂于上卻不收斂于 中點，中點，從而算法從而算法不是閉不是閉的顯然對任何初始點顯然對任何初始點x1 2, 由映射由映射a產(chǎn)生的任何序列都收斂于點產(chǎn)生的任何序列都收斂于點x*=2，對初始點對初始點x12, 由映射由映射a產(chǎn)生的任何序列

7、都收斂于點產(chǎn)生的任何序列都收斂于點x=1.ch8 算法概念評注：上面例子表明初始點x1選取的重要性：若x1 2則達到收斂于中的點，否則就不能實現(xiàn)。另注意注意到，在上例中都滿足如下條件：但對任何但對任何x1 2都不收斂于都不收斂于 x*=1 ,即算法不是閉的即算法不是閉的 1，給出一可行點xk 1,任何后繼點xk也是可行的,即xk+1 12，給出一個不在解集內(nèi)的可行點xk,任何后繼點xk+1滿足 f(xk+1)0, ,當kn()時有()( )(n)( )()(2.1), (2.2)(), 0 (2.3)knxxknkkxx特別的 必有 ()( )對于所有的包括不屬于 的由于 是下降函數(shù),故()(

8、)ch8算法-收斂定理( )( )()()( )( )k(2.2)(2.3) (2.4)(2.5) limkknnkkxxxxxxxxxx由和可得()( )()()()( ) n都成立.另一方面,由 是下降函數(shù)知()( )0 (2.5)由和得()( ) (2.6)ch8 算法-收斂定理(1)(1)(1)(). ,. ,. lim()( )(2.7),( )( ) (2.8)kkkkkkxxxkkxkkxxxxxx下證反證法假設考慮序列由于此序列含于緊集故存在收斂子序列設其極限為用上面的方法可證 由極限唯一性 ch8 算法-收斂定理( )(1)(1)( ),(),( ), ( )( ) (2.9

9、)(2.8).kkkkkkkkxxxx xa xaxaxxa xaxxxx再次 由上分析可知對于有 由于算法 在 的補集上是閉的因此在 處是閉的 于是有 由 是關(guān)于 和 的下降函數(shù)知必有此與矛盾故ch8 算法-收斂定理 8.2.2實用收斂準則正如在收斂定理中所指出，若我們達到解集中的一個點時，就終止算法。然而，在大多數(shù)情形下，收斂于中的點僅僅出現(xiàn)在極限意義上，因此我們必須依靠終止迭代過程的某些實際規(guī)則，下面給出一些常用的終止規(guī)則。這里0和正整數(shù)n是預先給定的。1) |xk+n xk| 如果應用映射如果應用映射a的的n次后移動的距離小于次后移動的距離小于 時，算法終止時，算法終止11 or 2),-kkkkkxxxxx ch8 算法-收斂定理11()-()()-3),()(),)40()kkkkkkf xf xf xf xf xf x 當函數(shù)值 或下降函數(shù)值 的下降量充分小時停止計算 即 或 在無約束最優(yōu)化中，當梯度充分接近于 時停止計） 算，即