【正文】 x?Rn () 其中 f(x)具有一階連續(xù)偏導(dǎo)數(shù)。這是無約束最優(yōu)化中最簡單的方法。條件數(shù)越大 ,收斂越慢 . 最速下降法存在鋸齒現(xiàn)象 x(2)x(1)x 容易證明 ,用最速下降法極小化目標(biāo)函數(shù)時(shí) ,相鄰兩個(gè)搜索方向是正交的 .令 ( ) ( ) T ( )( 1 ) ( )( 1 ) ( 1 ) ( ) ( )( ) = ( ) 0( ) ( ) 0( ) ( )k k kkk T kk k k kf x d df x f xd f x d f x? ? ????? ? ? ?? ? ? ? ?? ? ? ? ? ? ?與 正 交( ) ( )( ) ( )( ) ( ) ()kkkkf x dd f x? ? ???? ?? 牛頓法 迭代格式 ( ) ( ) ( )( ) 2 ( ) ( )2 ( ) ( )( ) ( )( ) ( ) (( ( ) (( ) ( ) He ssi a nk k T kk T k kkkf x xf x f x x xx x f x x xf x f x x??? ? ?? ? ?? = )+1 ) )2其 中 是 在 點(diǎn) 處 的 矩 陣 .()()( ) , . ( ), ( ) T a y l or ,nkkf x x R x f xf x x?設(shè) 是 二 次 可 微 函 數(shù) 又 設(shè) 是 的 極 小 點(diǎn) 的一 個(gè) 估 計(jì) 將 在 點(diǎn) 展 開 取 二 階 近 似 :2 ( )( 1 ) ( ) 2 ( ) 1 ( )()( ) ( ) 10 2 2???? ? ?kk k k kfxx x f x f x 設(shè) 可 逆 , 則 得 牛 頓 法 的 迭 代 公 式 = ( . . )即 ( ) 2 ( ) ( )( ) ( ) ( 1 0 2 1? ? ? ?k k kf x f x x x ) = 0 ( . . )( 0 )( ) ( )( 1 ) ( ) 2 ( ) 1 ( )N e w ton )1 , , 0 , 1 。 ,( ) ( ) , : 1 , 2kkk k k kSte p x kSte p f x xx x f x f x k k????????? ? ? ? ? ?算 法 ( 法給 定 初 始 點(diǎn) 允 許 誤 差 置若 停 止 得 解 否 則 令 轉(zhuǎn) 牛頓法 ?? (x)=0 為求 ? (x)的駐點(diǎn) ,令 注意 :牛頓法的迭代格式也可以從最速下降方向的角度來理解 . m i n ( ). 1 (10 .2 .3 )??TTf x ds t d Ad下求 A度量下的最速下降方向 ,為此 ,考慮 牛頓法 TAd d Ad?下面介紹一下 A度量及其意義下的最速下降方向 .設(shè) A為對稱正定矩陣 ,向量 d的 A范數(shù)定義為 由 A, A1對稱正定 ,故存在對稱平方根 A1/2 , A1/2,使得 1 1 1 112 2 2 2, A A A A A A???? －于是 1 1 1 12 2 2 211221122()( ) ( ) ( ( ) )T T TTTTd Ad d A A d A d A df x d f x A A dA f x A d????? ? ??? 牛頓法 12 , ( 10 .2 .3 )?y A d令 則 可 寫 成12m in ( ( ) ). 1 ( 10 .2. 4)???TTA f x ys t y y去掉絕對值符號 ,有 1122 ( ( ) ) ( )TA f x y A f x??? ? ? ?1 1 12 2 2 ( ( ) ) ( ) ( )TA f x y A f x y A f x? ? ?? ? ? ? ?根據(jù) Schwartz不等式 ,得到 牛頓法 即 1 1 12 2 2 ( ) ( )Tf x A A d A f x??? ? ? ?12( ) ( ) Tf x d A f x?? ? ? ? ?為得到在點(diǎn) x處下降最快的方向 ,按下式選取 d 111 2() ( )( ( ) ( ) )??????? TA f xdf x A f x這時(shí)上式等號成立 ,由此確定的方向即 度量 A意義下的最速下降方向 牛頓法 若取 2 () kkA G f x? ? ?, ( ) .k kkG Gfx?的 最 速 下 降 方 向 其 步 長 為則牛頓法的搜索方向?qū)嶋H上是關(guān)于向量橢球范數(shù) 牛頓法 牛頓法 例 用牛頓法求解下列問題 4212( 1 ) m in ( 1 )( 0 , 1 )xxx????取 初 點(diǎn)3 221 120 4( 1 ) 12( 1 )( ) , ( ) 22 0x xf x f xx?? ??? ?? ? ? ??? ??????第 1次迭代 ( 1 ) 2 ( 1 ) 4 12 0 ( ) , ( ) 2 0 2f x f x? ? ? ?? ? ? ?? ? ? ?? ? ? ? ( 2 ) ( 1 ) 2 ( 1 ) 1 ( 1 )1( ) ( )0 12 0 4 1 / 3 1 0 2 2 0x x f x f x??? ? ? ?? ? ? ? ? ? ? ?? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?( 3 ) ( 2 ) 2 ( 2 ) 1 ( 2 )1( ) ( )1 / 3 48/ 9 0 32 / 27 5 / 9 0 0 2 0 0x x f x f x??? ? ? ??? ? ? ? ? ? ? ?? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?第 2次迭代 ( 2 ) 2 ( 2 ) 32 / 27 48/9 0 ( ) , ( ) 0 0 2f x f x?? ? ? ?? ? ? ?? ? ? ?? ? ? ? 牛頓法 ( 4 ) ( 3 ) 2 ( 3 ) 1 ( 4 )1( ) ( )5 / 9 64/ 27 0 256 / 729 19 / 27 0 0 2 0 0x x f x f x??? ? ? ??? ? ? ? ? ? ? ?? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?第 3次迭代 ( 3 ) 2 ( 2 ) 256 / 729 64/27 0 ( ) , ( ) 0 0 2f x f x?? ? ? ?? ? ? ?? ? ? ?? ? ? ?繼續(xù)下去 ,第 4次迭代 ,… 得到點(diǎn)列收斂于 (1,0),此為 最優(yōu)解 . 牛頓法 ? ?2 ( ) 1 ( 1 )1 2 1 2( 1 )2 ( ) 112 ( ) , . ( ) 0 ,( ) ,( ) , (10 .2 .) ( ) ( ) (( 2 )1??? ? ??? ? ? ? ???? ? ? ? ? ?nkkf x x E x f xf x x xk k k kx X x x x x xf x kf x f x f x x x設(shè) 是 二 次 可 微 函 數(shù) 滿 足且 存 在 , 又 設(shè) 初 始 點(diǎn) 充 分 接 近 使 得 存在 0, 滿 足 1, 且 對 每 一 個(gè)成 立定:(1理)2) .??kxxx則 牛 頓 法 產(chǎn) 生 的 序 列 收 斂 于 局部收斂性 牛頓法 證明 :根據(jù) ()，牛頓算法映射定義為 21( ) ( ) ( )A x x f x f x?? ? ? ? (a){ } , ( ) x x x x???定 義 解 集 合 令 函 數(shù) =下證 ?(x) 是關(guān)于解集合 ?和算法 A的下降函數(shù) . 21212 1 2A ( ) 0 ,( ) ( )( ) ( ) [ ( ) ( ) ]( ) [ ( ) ( ) ( ) ( ) ] ( b)fxy x x f x f x xx x f x f x xf f x x f x f x x x?????? ? ? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ? ? ?根 據(jù) 算 法 的 定 義 及 的 假 設(shè) 有, , ( ) .x X x x y A x? ? ?令 且 又 令 牛頓法 于是可得 2 1 212( ) ( ) ( ) ( ) ( ) ( c )y x f x x f x f x x xk k x x x x?? ? ? ? ? ? ? ? ?? ? ? ?()()( ) , , { } .A{}kkc y X x XXXxx??由 可 知 故 迭 代 產(chǎn) 生 的 序 列 根 據(jù)定 義 知 是 緊 集 , 故 迭 代 產(chǎn) 生 的 序 列 含 于 緊 集 . 此 外 ,算 法 映 射 在 緊 集 上 是 閉 的 .綜 上 , 迭 代 產(chǎn) 生 的 序 列 必 收 斂 于從而 ?(x) 是關(guān)于解集合 ?和算法 A的下降函數(shù) 牛頓法 2202( ) ( ) , *( * ) 0 , H e ss e ( * )* , H e ss e ( ) ( )L ips c hit z , L 0 , , ,( ) ( ) ,k 10 2 2 { }*.?? ? ???? ? ?? ? ??nnkf C R xf x f xx x G x f xx y RG x G y L x yxx局 部 收 斂 定 理 設(shè) 函 數(shù) 它 在的 梯 度 矩 陣 正 定 . 若 初 始點(diǎn) 充 分 靠 近 并 且 矩 陣 滿 足條 件 即 存 在 使 得 有 則 對 , 迭 代 格 式 ( . . ) 有 意 義 , 且 迭 代 點(diǎn) 序 列以 二 階 的 收 斂 速 度 收 斂 到定 理 牛頓法 當(dāng)牛頓法收斂時(shí) ,有下列關(guān)系 2( 1 ) ( ) kkx x c x x? ? ? ?c , 2是 某 個(gè) 常 數(shù) 因 此 算 法 至 少 是 階 收 斂 的 .特別的 ,對于二次凸函數(shù) ,用牛頓法求解 ,經(jīng)一次迭代即達(dá)到極小點(diǎn) .設(shè)有二次凸函數(shù) 其中 A是對稱正定矩陣 1()2TTf x x A x b x c? ? ? 牛頓法 先用極值條件求解 .令 ( ) 0f x A x b? ? ? ?得最優(yōu)解 1x A b???下用牛頓法解 ,任取一初始點(diǎn) x(1) ( 2 ) ( 1 ) 1 ( 1 ) ( 1 ) 1 ( 1 ) 1( ) ( )x x A f x x A A x b A b? ? ?? ? ? ? ? ? ? ?( 2 ), . .xx ?顯 然 即 一 次 迭 代 即 達(dá) 極 小 點(diǎn)定義 :若一個(gè)算法用于求解嚴(yán)格二次凸函數(shù)極小值問題時(shí) 從任意初始點(diǎn)出發(fā) ,算法在有限次迭代后可到達(dá)函數(shù)的極 小值點(diǎn) ,稱此算法具有二次終止性 . 于是牛頓法具有二次終止性 牛頓法 注意 ,當(dāng)初始點(diǎn)遠(yuǎn)離極小點(diǎn)時(shí) ,牛頓法可能不收斂 ?阻尼牛頓法 基本思想 :增加了沿牛頓方向的一維搜索 . 迭代公式為 ( 1 ) ( ) ( ) k k kkx x d?? ?=( ) 2 ( ) 1 ( )( ) ( ),k k kd f x f x ??? ? ? ?k其 中 為 牛 頓 方 向 , 是 由一 維 搜 索 所 得 的 步 長 即 滿 足( ) ( ) ( ) ( )( ( ) k k k kkf x d f x d????? ) = m i n 牛頓法 算法 (阻尼牛頓法 ) ( 0 )( ) 2 ( ) 1( ) ( )( ) 2 ( ) 1 ( )( ) ( )( ) ( ) ( ) ( )1 , , 0 , 1 。 , ( )