Lecture6算法和算法復(fù)雜性一維搜索.ppt

《Lecture6算法和算法復(fù)雜性一維搜索.ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《Lecture6算法和算法復(fù)雜性一維搜索.ppt（33頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、最優(yōu)化方法 Optimization 第十一講 第八章 算法和算法復(fù)雜性 第九章 一 維 搜 索 主要內(nèi)容 算法概念 算法收斂準(zhǔn)則 全局收斂 , 局部收斂 , 收斂速度 算法二次終止性 算法復(fù)雜性 內(nèi)點(diǎn)法 : 路徑跟蹤法 算法概念 一下降迭代算法 迭代： ( ) ( 1 ) () () 1 * l im * 0 * kk k k k x A x k k x x xx x 從 一 點(diǎn) 出 發(fā) ， 按 照 某 種 規(guī) 則 ， 求 出 后 繼 點(diǎn) ， 用 代 替 ， 重 復(fù) 以 上 過(guò) 程 ， 得 到 一 個(gè) 解

2、的 序 列 ， 若 該 序 列 有 極 限 點(diǎn) ， 即 則 稱(chēng) 它 收 斂 于 。 下降 ： 在每次迭代中，后繼點(diǎn)處的函數(shù)值要有所減少。 下降迭代算法的步驟 ： 。，置選定某一初始點(diǎn) 0.1 )0( kx 。確定搜索方向 )(.2 kd 。迭代點(diǎn) ，以產(chǎn)生下一個(gè)求步長(zhǎng)出發(fā)，沿方向從 )1( )()(.3 k k kk x dx 。，返回止迭代；否則，令 小點(diǎn)，若是，則停是否為極小點(diǎn)或近似極檢查 21: .4 )1( kk x k 選取搜索方向 是最關(guān)鍵的一步，各種算法的區(qū)別， 主要在于確定搜索方向的方法不同。 k確 定 步 長(zhǎng) 的 主 要 方

3、法 令它等于某一常數(shù)。.1 2. k 可 接 受 點(diǎn) 算 法 ， 即 只 要 能 使 目 標(biāo) 函 數(shù) 值 下 降 ， 可 任 意 選 取 步 長(zhǎng) 。 ( ) ( ) ( ) ( ) ( ) ( ) 3. () ( ) m i n ( ) . kk k k k k k x x d fx f x d f x d 基 于 沿 搜 索 方 向 使 目 標(biāo) 函 數(shù) 值 下 降 最 多 ， 即 沿 射 線(xiàn) 求 目 標(biāo) 函 數(shù) 的 極 小 由 于 這 項(xiàng) 工 作 是 求 以 為 變 量 的 一 元 函 數(shù) 的 極 小 點(diǎn) ， 故 常 稱(chēng) 這 一 過(guò) 程 為 （ 最 優(yōu) ） 一 維 搜 索 ，

4、這 樣 確 定 的 步 長(zhǎng) 為 最 佳 步 長(zhǎng) 。 定理： ( 1 ) ( ) ( ) ( 1 ) ( ) ( 1 ) () ( ) m in ( ) ( ) 0 k k k k k k k k k k k T k f x x f x d f x d x x d f x d 設(shè) 目 標(biāo) 函 數(shù) 具 有 一 階 偏 導(dǎo) 數(shù) ， 由 下 列 規(guī) 則 產(chǎn) 生 ： 則 有 。 證明： 0)( )()( 0)( )( )()( )( )( )( kTk k k kTk k k k k kk kk ddxf ddxf dxf 而 的駐點(diǎn)。為是最優(yōu)步長(zhǎng)，則若

5、 記 二算法映射 定義： ,2 :2 nX X XE AX 給 定 集 合 記 其 冪 集 （ 即 所 有 子 集 構(gòu) 成 的 集 合 ） 為 ， 稱(chēng) 集 值 映 射 為 一 個(gè) 算 法 映 射 (algorithm mapping). 例： ( 0 ) ( 1 ) ( ) m i n | , 0 , | ( ) | () n n kk L P c x Ax b x X x x L P A x y y L P y x x X x A x 考 慮 標(biāo) 準(zhǔn) 形 式 的 線(xiàn) 性 規(guī) 劃 令 為 的 基 本 可 行 解 ， 若 定 義 算 法 映 射 為 的 基 本 可

6、 行 解 , 并 且 和 的 基 矩 陣 是 相 鄰 的 ， 那 么 對(duì) 于 任 意 一 個(gè) 基 本 可 行 解 ， 迭 代 格 式 就 生 成 一 個(gè) 相 鄰 的 基 本 可 行 解 序 列 。 例： 2m in . . 1 . x s t x 考 慮 下 列 非 線(xiàn) 性 規(guī) 劃 ： 1 1 , ( 1 ) 1 ; 2 () 1 ( 1 ) , 1 1. 2 xx Ax xx 定 義 算 法 映 射 ： 3 5 3 9 3 3 5 7 2 5 3 , 2 , , , , 3 , , , , , 3 , , , , 2 4 2 8 3 2 3 6 2 4 A

7、 利 用 算 法 可 以 產(chǎn) 生 不 同 的 點(diǎn) 列 ： x y 1 y=(x+1)/2 A(x(1,k)) A(x(2,k)) 解集合 把滿(mǎn)足某些條件的點(diǎn)集定義為 解集合 當(dāng)?shù)c(diǎn)屬 于該集合時(shí)，停止迭代 常用的解集合 ： | ( ) 0 | | , ( ) , x f x x x KK T x x S f x b b 為 點(diǎn) 其 中 是 某 個(gè) 可 接 受 的 目 標(biāo) 函 數(shù) 值 。 算法收斂問(wèn)題 定義： ( 1 ) () :2 X k AX Y X x Y A x AY 設(shè) 為 解 集 合

8、， 為 算 法 映 射 。 給 定 一 個(gè) 集 合 ， 若 對(duì) 于 任 意 的 初 始 點(diǎn) ， 算 法 映 射 所 產(chǎn) 生 的 序 列 中 任 一 收 斂 子 序 列 的 極 限 都 屬 于 ， 則 稱(chēng) 算 法 映 射 在 上 收 斂 。 ( ) . ( ) . Y g lob a l c o n v e rg e n c e Y loc a l c o n v e rg e n c e 若 集 合 是 任 意 選 取 的 （ 該 集 合 不 必 限 定 在 解 集 合 的 很 小 領(lǐng) 域 內(nèi) ） ， 則 相 應(yīng) 的 收 斂 性 稱(chēng) 為 若 集 合 只 能 取 接 近 的 點(diǎn) 集 ， 則

9、相 應(yīng) 的 收 斂 性 稱(chēng) 為 全 局 收 斂 性 局 部 收 斂 性 實(shí)用收斂準(zhǔn)則 ( 1 ) ( ) ( 1 ) ( ) () 1 . . kk kk k xx xx x 或 者 ( ) ( 1 ) ( ) ( 1 ) () ( ) ( )2 . ( ) ( ) . () kk kk k f x f xf x f x fx 或 者 ()3 . ( ) ( ) .kfx 無(wú) 約 束 最 優(yōu) 化 中 收斂速率 定義： () ( 1 ) _____ () () * * l i m * k k p k k k p 設(shè) 序 列 收 斂

10、于 ， 定 義 滿(mǎn) 足 的 非 負(fù) 數(shù) 的 上 確 界 為 序 列 的 收 斂 級(jí) 。 p p若 序 列 的 收 斂 級(jí) 為 ， 則 序 列 是 級(jí)稱(chēng) 收 斂 的 。 11p 序 列 是 以 收 斂 比 線(xiàn) 性若 且 ， 則 稱(chēng) 收 斂 的 。 1 , 1 0pp 若 或 者 且 ， 則 序 列 是 超 線(xiàn)稱(chēng) 性 收 斂 的 。 收斂級(jí) p越大，序列收斂得越快；當(dāng)收斂級(jí) p 相同時(shí)，收斂比 越小， 序列收斂得越快。 例： 01kaa 11 l i m 0 l i m 1 , l i m ( 1 ) () 0 k k kk k k r kk k a aa ar aa a

11、a 又 且 當(dāng) 時(shí) ， 以 收 斂 比 線(xiàn) 性 收 斂 于 。 例： 2 0 | | 1kaa 1 1 1 1 2 2 2 2 2 2 22 2 l im 0 l im l im 1 , l im ( 2 ) k k k k k kk k k r k k k a a a a r aaa a 又 且 當(dāng) 時(shí) ， 是 2 級(jí) 收 斂 的 。 例： 1 k k 1 1 1 ( 1 ) 1 l i m 0 1 11 l i m l i m 0 111 1 1 l i m l i m ( 1 ) 1 1 1 k k k

12、k k kk k k pk p kk k k k kk kk k kkk p kk k k 又 是 超 線(xiàn) 性 收 斂 的 。 用二次終止性作為判斷算法優(yōu)劣的原因 ： (1)正定二次函數(shù)具有某些較好的性質(zhì)，因此一個(gè)好的算法應(yīng) 能夠在有限步內(nèi)達(dá)到其極小點(diǎn)。 (2)對(duì)于一般的目標(biāo)函數(shù)，若在其極小點(diǎn)處 Hesse矩陣正定， 因此可以猜想，對(duì)正定二次函數(shù)好的算法，對(duì)于一般目標(biāo)函 數(shù)也應(yīng)具有較好的性質(zhì)。 2 ( ) * * * 1 * * * | | * |

13、| 2 T T f x f x f x x x x x f x x x o x x 若某個(gè)算法對(duì)任意的 正定二次函數(shù) ，從任意的初始點(diǎn)出發(fā)，都 能經(jīng) 有限步 迭代達(dá)到其極小點(diǎn)，則稱(chēng)該算法具有 二次終止性 。 算法的二次終止性 算法復(fù)雜性 描述算法的存儲(chǔ)要求和運(yùn)行時(shí)間要求，分為 算法的空間復(fù)雜性和算法的時(shí)間復(fù)雜性。 利用算法需要的 初等運(yùn)算次數(shù) 表示算法的 時(shí)間復(fù)雜性 。 算法復(fù)雜性 求解實(shí)例 I的算法的 基本計(jì)算總次數(shù) C(I)是實(shí)例輸入長(zhǎng)度 d(I)的一個(gè)函數(shù)，該函數(shù)被另一個(gè)函數(shù) g(x)控制，即存 在一個(gè)函數(shù) g(x)和一個(gè)常數(shù) a，使得 ( ( )

14、)C I a g d I 多項(xiàng)式時(shí)間算法與指數(shù)時(shí)間算法 輸入規(guī)模 (input size)：表示一個(gè) 實(shí)例 所 需要的字符串長(zhǎng)度。 一般的，使用 位二進(jìn)制就可以 表示任意整數(shù) r。 線(xiàn)性規(guī)劃的輸入規(guī)模為： 21 lo g r 2 2 2 1 22 1 1 1 2 1 l o g 1 l o g 1 l o g | | 1 l o g | | 1 l o g | | 2 l o g | | ( , , ) n j j m n m i j j i j i L m n c ab mn m n P P A b c

15、 為 中 所 有 非 零 數(shù) 的 乘 積 多項(xiàng)式時(shí)間算法與指數(shù)時(shí)間算法 ( ( ) )C I a g d I 假設(shè)問(wèn)題和解決該問(wèn)題的一個(gè)算法已經(jīng)給定，若給定該問(wèn)題 的一個(gè)實(shí)例 I，存在 多項(xiàng)式函數(shù) g(x)，使得 成立，則稱(chēng)該算法對(duì)實(shí)例 I是 多項(xiàng)式時(shí)間算法 . 若存在 g(x)為多項(xiàng)式函數(shù)且對(duì)該問(wèn)題任意一個(gè)實(shí)例 I ，都有 上式成立，則稱(chēng)該算法為解決該問(wèn)題的多項(xiàng)式時(shí)間算法。 當(dāng) g(x)為指數(shù)函數(shù)時(shí)，稱(chēng)相應(yīng)的算法為 指數(shù)時(shí)間算法 。 （ 1）隨著問(wèn)題輸入規(guī)模的增加，算法的計(jì)算量（即 算法復(fù)雜性）呈多項(xiàng)式增長(zhǎng) . （ 2）一個(gè)多項(xiàng)式時(shí)間算法利用

16、另一個(gè)多項(xiàng)式時(shí)間算 法作為其 “ 子程序 ” ，構(gòu)造一個(gè)新的復(fù)合型算法， 則新算法仍是多項(xiàng)式時(shí)間算法。 多項(xiàng)式時(shí)間算法的優(yōu)點(diǎn) 1 22 m in 10 . . 2 10 10 , 2 , , 0 , 1 , 2 , , n ni i i i j i ij ji i x s t x x i n x i n 上例用單純形算法需要 2n-1次迭代 單純形算法的復(fù)雜性 精確線(xiàn)搜索 試探法 : 黃金分割法、 Fibonacci法、二分法 函數(shù)逼近法 : Newton法、割線(xiàn)法、拋物線(xiàn)法、 三次插值法 非精確線(xiàn)搜索

17、 Armijo步長(zhǎng)規(guī)則、 Goldstein步長(zhǎng)規(guī)則、 Wolfe步長(zhǎng)規(guī)則 一維搜索 ( ) ( ) 0( ) m i n ( ) kkL S f x d ( ) ( ) ( ) ( ) m i n ( E x ac t L i n e S ea rc h ). . k k k k k k k f x d f x d 如 果 求 得 的 ， 使 得 則 稱(chēng) 該 一 維 搜 索 為 精 確 一 維 搜 索 稱(chēng) 為 最 優(yōu) 步 長(zhǎng) ( ) ( ) ( ) ( I n ex ac t L i n e S ea rc h ). k k k k kf

18、x d f x 如 果 存 在 ， 使 得 則 稱(chēng) 該 一 維 搜 索 為 非 精 確 一 維 搜 索 精確、非精確線(xiàn)搜索 函數(shù)逼近法：牛頓法 基本思想： 在極小點(diǎn)附近用二階 Taylor多項(xiàng)式近似。 )(m in xf 2)()()()()( ))(( 2 1))(()()( kkkkk xxxfxxxfxfx 令 ( ) ( ) ( )( ) ( ) ( ) ( ) 0k k kx f x f x x x 又 令 )( )( )( )( )( )()1( )1( k k kk k xf xf xx xx ，則的駐點(diǎn)，記作得 定理： ( 1 ) () ( )

19、( ) 0 ( ) 0 k f x x f x f x x x xx 設(shè) 存 在 ， 滿(mǎn) 足 ， ， 初 點(diǎn) 充 分 接 近 ， 則 牛 頓 法 產(chǎn) 生 的 序 列 至 少 以 二 級(jí) 收 斂 速 度 收 連 續(xù) 三 階 導(dǎo) 斂 于 數(shù) 。 證明： )( )( )( xf xf xxA 射牛頓法可定義為算法影 ||)( xxx 定義函數(shù) x設(shè)解集合為 )(, )()1()( kkk xAxxx 設(shè) ( 1 ) ( 1 ) () ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) () ( ) 2 ( ) () ( ) | | ( ) 1 ( )

20、 ( ) ( ) ( ) | ( ) | 1 ( ) ( ) ( ) ( ) | ( ) | 11 ( ) | ( ) | | ( ) | 2 kk k k k k k k kk k k k k kk k x x x fx x x x f x f x x f x f x f x f x f x x x f x fx x x f x x fx 其 中 在 和 之 間 。 21 )( 21 )( |)(|,|)(| 0, ,0)()()( kxfkxf xxxkk xxxfxfxf k k 處，有的閉區(qū)間上的每一點(diǎn)和使得在包含 時(shí)，存在

21、接近當(dāng)連續(xù)，和 ( 1) ( ) 2 ( )2 1 ()2k k kkx x x x xk 是 二 級(jí) 收 斂 。 1 2 )1( 1 2 )1( xx k k xx ，使得充分接近取初點(diǎn) |||| ||||| )()1( )1()( xxxx xxxxxXx kk k 且有 。 上連續(xù)在為緊集，是下降函數(shù)，且 xx XxAX k )( )( 算法步驟 : ( 0 )1 . , 0 , 0 xk 給 定 初 始 點(diǎn) 允 許 誤 差 置 。 .3;,|)(|.2 )()( 否則轉(zhuǎn)則停止計(jì)算，得點(diǎn)若 kk xxf 。，返回置 計(jì)算點(diǎn) 21 , )( .3 )( )(

22、 )()1( )1( kk xf xf xx x k k kk k 缺點(diǎn)： 初 始 點(diǎn)選擇十分重要。如果初始點(diǎn)靠近極小點(diǎn)，則 可能很快收斂；如果初始點(diǎn)遠(yuǎn)離極小點(diǎn)，迭代產(chǎn)生的點(diǎn) 列可能不收斂于極小點(diǎn)。 例： .01.0),21(5m i n xxe x 2)0( x取初始點(diǎn) 解： 00 00 2.060 96.13 01 2.501 2.061 2.12 34 9.534 9.067 7.11 38 8.738 8.220 )()()( kkk xfxfxk 為近似解。6 0 9 6.1 x 0 ( ) m i n a

23、 r c t g * 0 . x f x t d t x 最 優(yōu) 解例： 用 Newton法求解： 2 1( ) , ( ) 1 f x arc tg x f x x 1 1 1 0.785 4 2 2 0.570 8 0.517 8 1.325 8 3 0.116 9 0.116 3 1.013 7 4 0.001 061 k k k k x f x f x 1 1 2 1 . 1 0 7 1 5 2 3 . 5 3 5 7 1 . 2 9 5 2 1 3 . 5 0 3 1 3 . 9 5 k k k k x f x f x 非精確搜索 ( ) ( ) (

24、 ) ( ) ( ) 0 0 1 , ( ) ( ) ( ) km kk k m k k m k T k m f x d f x f x d 設(shè) , ( , ) , ( 0 , 1 ) . 取 步 長(zhǎng) 其 中 是 滿(mǎn) 足 下 式 的 最 小 非 負(fù) 整 數(shù) : Armijo步長(zhǎng)規(guī)則 根據(jù)目標(biāo)函數(shù)的 Taylor展開(kāi)式， 滿(mǎn)足這種規(guī)則的步長(zhǎng)一定 存在。 非精確搜索 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 2 ( ) ( ) ( ) , ( ) ( ) ( 1 ) ( ) . 0 k k k k k T k k k

25、k k T k f x d f x f x d f x d f x f x d 1 設(shè) ( 0 , ) . 取 步 長(zhǎng) 滿(mǎn) 足 下 式 : 由 于 充 分 小 時(shí) , 第 二 式 必 不 成 立 , 故 該 規(guī) 則 在 保 證 目 標(biāo) 函 數(shù) 下 降 的 前 提 下 , 使 下 一 迭 代 點(diǎn) 盡 可 能 遠(yuǎn) 離 當(dāng) 前 迭 代 點(diǎn) . Goldstein步長(zhǎng)規(guī)則 ( ) ( )( ) 0 , 0. kk k f x d G o l d s t e i n 定 理 : 若 ( ) = 關(guān) 于 有 下 界 則 必 存 在 滿(mǎn) 足 步 長(zhǎng) 規(guī)

26、則 ( ) ( ) ( ) ( ) ( ) 1 1 1 ( ) ( ) ( ) 2 12 ( ) 0 , , ( ) ( ) . 0. 0, ( ) ( 1 ) ( ) k T k k k T k k k T k f x d f x f x d f x f x d 證 明 : 由 于 故 ( ) = 在 充 分 小 時(shí) , ( ) 在 () 的 上 方 由 于 () 關(guān) 于 有 下 界 故 () 和 () 在 的 正 半 軸 有 交 點(diǎn) . 類(lèi) 似 地 , ( ) = 和 () 在 的 正 半 軸 也

27、 有 交 點(diǎn) . 取 () 和 () 與 () 的 一 個(gè) 最 小 交 點(diǎn) 12 1 2 2 1 1 0) 2 . k G o ld ste in , . 因 . 則 存 在 (, 使 步 長(zhǎng) 規(guī) 則 成 立 非精確搜索 12 ( ) ( ) ( ) ( ) ( ) 1 ( ) ( ) ( ) ( ) ( ) ( ) 2 ( ) ( ) 0< 1 ( ) ( ) ( ) , ( ) ( ) ( ) . () 0 k k k k k T k k k T k k k T k kk k f x d f x f x d f x d d f x f x d f x d 設(shè) . 取 步 長(zhǎng) 滿(mǎn) 足 下 式 : 該 規(guī) 則 使 函 數(shù) 的 陡 度 在 點(diǎn) 比 在 = 點(diǎn) 有 所 減 緩 , 從 而 使 下 一 迭 代 點(diǎn) 盡 可 能 遠(yuǎn) 離 當(dāng) 前 迭 代 點(diǎn) . Wolfe步長(zhǎng)規(guī)則