【正文】 如果 ,??kg停 . Step5: 若 ,nk ? 令 轉(zhuǎn) step2. Step6: 計算 11111 , ????? ???? kkkkkTkkTkk dgdgggg ??Step7: 如果 ,0?kTk gd令 轉(zhuǎn) step2, 否則 轉(zhuǎn) step3. 0 :,kxx?（ ） （ ）0 :,kxx?（ ） （ ）作 業(yè) 用 FR共軛梯度法求解： ? ? 02212 5m i n 2 5f x x x x ??? ? ? ????（ ）多維約束最優(yōu)化方法 ? 懲罰函數(shù)法 SUMT:序列無約束極小化方法 (Sequential Unconstrained Minimization Technique) ? 乘子法 外點法（二次罰函數(shù)方法） 內(nèi)點法（內(nèi)點障礙罰函數(shù)法） 罰函數(shù)法 基本思想 設(shè)法將約束問題求解轉(zhuǎn)化為無約束問題求解． 具體說： 根據(jù)約束的特點，構(gòu)造某種懲罰函數(shù)， 然后把它加到目標函數(shù)中去，將約束問題的 求解化為一系列無約束問題的求解． 懲罰策略 ： 企圖違反約束的迭代點給予很大的 目標函數(shù)值． 迫使一系列無約束問題的極小點或 者無限地靠近可行域，或者一直保持在可行域 內(nèi)移動，直到收斂到極小點． 外罰函數(shù)法（外點法） 引例： 求解等式約束問題 : ? ? 222121 ,m in xxxxf ??02. 21 ??? xxts解 : 圖解法求出最優(yōu)解 ? ? .1,1* Tx ?構(gòu)造： ? ????????????22,2121222121 xxxxxxxxF但是 ? ?21 , xxF性態(tài)極壞， 無法用有效的無約束 優(yōu)化算法求解． 設(shè)想構(gòu)造： ? ? ? ?1 222 2 1 2。kk gdG ??方程組有時奇異或病態(tài)的， 無法確定 ,kd或 kd不是下降方向． (4) 收斂到鞍點或極大點的可能性并不?。? 阻尼牛頓法算法 Step1: 給出 ( 0 ) , 0 1 , : 0nx R k?? ? ? ? ?Step2: 計算 ? ?() ,kfx?如果 ? ?() ,kfx ???停． Step3: 否則計算 ,kGStep4: 沿 并且求解方程 ,kk gdG ??得出 .kdkd進行線搜索， 得出 .k?Step5: 令 ( 1 ) ( ) ,kk kkx x d?? ?? 轉(zhuǎn) Step2. 阻尼牛頓法收斂定理 定理 2: 設(shè) ? ?xf二階連續(xù)可微， 又設(shè)對任意的 ( 0 ) ,nxR?存在常數(shù) ,0?m 使得 ? ?xf在 ? ? ? ?? ?0xfxfxL ??上滿足： ? ? ? ?( 0 )22 ,Tnf x m R x L x? ? ? ?? ? ? ? ?則在精確線搜索條件下， 阻尼牛頓法產(chǎn)生的點列 ? ?()kx滿足： (1) 當 ? ?()kx是有限點列時， 其最后一個點為 ? ?xf的唯一極小點． (2) 當 ? ?()kx是無限點列時， 收斂到 ? ?xf的唯一極小點． 阻尼牛頓法收斂定理 定理 3: 設(shè) ? ?xf二階連續(xù)可微， 又設(shè)對任意的 ( 0 ) ,nxR?存在常數(shù) ,0?m 使得 ? ?xf在 ? ? ? ?? ?( 0 )L x f x f x??上滿足： ? ? ? ?( 0 )22 ,Tnf x m R x L x? ? ? ?? ? ? ? ?則在 Wolfe不精確線搜索條件下， 阻尼牛頓法 產(chǎn)生的點列 ? ?()kx滿足： ? ?()l im 0kk fx?? ??且 ? ?()kx收斂到 ? ?xf的唯一極小點． 例 2： 用阻尼牛頓法求解： ? ? ? ? ? ?(0 )241 1 2 2m i n 1 0 , 0 Tf x x x x x x? ? ? ? ?解： ??????????????????21102000 Gg顯然 0G不是正定的， 但： ???????? ???011210G于是， ???????? ???? ?020100 gGd沿方向 0d進行線搜索， ? ?( 0 ) 40 16 1 ,f x d??? ? ?得其極小點 .00 ??從而迭代不能繼續(xù)下去． 帶保護的牛頓法算法 給出 ( 0 ) 12, , , : 0nx R k????Step1: kG若 為奇異的，轉(zhuǎn) Step8，否則， Step2: 令 ,1 kkk gGd ???Step3: 若 ,1 kkkTk dgdg ??為奇異的，轉(zhuǎn) ，否則，則轉(zhuǎn) Step8，否則， Step4: 若 ,1 kkkTk dgdg ??則轉(zhuǎn) Step9，否則， Step5: 沿方向 kd進行線搜索， 求出 ,k?并令 ( 1 ) ( ) .kk kkx x d?? ??Step6: 若 ,21 ???kg 停； Step7: 令 ,1?? kk 轉(zhuǎn) Step1； Step8: 令 ,kk gd ?? 轉(zhuǎn) Step5； Step9: 令 ,kk dd ??轉(zhuǎn) Step5. 例 3： 用帶保護的牛頓法求解： ? ? ? ? ? ?( 0 )241 1 2 2m i n 1 0 , 0 Tf x x x x x x? ? ? ? ?解： ??????????????????21102000 Gg顯然 0G不是正定的， 但： ???????? ???011210G于是， ???????? ???? ?020100 gGd因為， ,000 ?dg T故令， ,2000 ???????????? gd沿 0d進行線搜索得： ,210 ??? ?( 1 ) ( 1 )0 ,01x f x?????????第二次迭代： ????????????????? ??2110,0111 Gg而： ???????? ???? ?121111 gGd使 ,0211 ??dg T 故令 ?????????????????? ???12121d沿 1d進行線搜索， 得出 ,1 ??于是 : ? ?( 2 ) ( 2 ) f x??? ? ??????此時 : ???????? ???0 72g共軛梯度法 問題 1: 如何建立有效的算法？ 從二次模型到一般模型 問題 2: 什么樣的算法有效呢？ 二次終止性 (經(jīng)過有限次迭代必達到極小點的性質(zhì)） 算法特點 （１）建立在二次模型上，具有二次終止性． （２）有效的算法，克服了最速下降法的慢 收斂性，又避免了牛頓法的計算量大和局部收 性的缺點． （３）算法簡單，易于編程，需存儲空間小等 優(yōu)點，是求解大規(guī)模問題的主要方法． 共軛方向及其性質(zhì) 定義 1: 設(shè) mddd , 21 ?是 nR 中任一組 非零向量， 如果： ? ?jiGdd jTi ?? ,0則稱 mddd , 21 ?是關(guān)于 G 共軛的． 注： 若 ,IG ? 則是正交的，因此共軛是 正交的推廣． 定理 1: 設(shè) G為 n 階正定陣， 非零向量組 mddd , 21 ?關(guān)于 G 共軛， 則必線性無關(guān)． 推論 1: 設(shè) G為 n階正定陣， 非零向量組 nddd , 21 ?關(guān)于 G共軛， 則向量構(gòu)成 nR的一組基． 推論 2: 設(shè) G為 n 階正定陣， 非零向量組 nddd , 21 ?關(guān)于 G 共軛， 若向量 v 與 nddd , 21 ?關(guān)于 G 共軛， 則 .0?v求 的極小點的方法 共軛方向法算法 ? ? ? ?( ) ( )0m i n ,kkk k kf x d f x d??? ?? ? ?Step1: 給出 ( 0 ) , 0 1 , : 0nx R k?? ? ? ? ?計算 ? ?( 0 )0g g x?和初始下降方向 .0dStep2: 如果 ,??kg 停止迭代． Step3: 計算 ( 1 ),kk x? ?使得 ( 1 ) ( ) .kk kkx x d?? ??Step4: 采用某種共軛方向法計算 1?kd使得： .,1,0,01 kjGdd jTk ????Step5: 令 ,1: ?? kk 轉(zhuǎn) Step2. 共軛方向法基本定理 定義 2: 設(shè) n 維向量組 kddd , 21 ?線性無關(guān)， ( 1 ) ,nxR?向量集合 ? ?( 1 ) 11kk i i iiH x d R???? ? ??為 (1)x 與 kddd , 21 ?生成的 k 維超平面． 引理 1: 設(shè) ? ?xf 是連續(xù)可微的嚴格凸函數(shù)， n 維向量組 kddd ?, 21線性無關(guān)， ( 1 ) ,nxR?則： ( 1 ) ( 1 )1kkiiix x d????? ?是 ? ?xf在 kH上 唯一極小點的充要條件是： kidg iTk ?,2,1,01 ???定理 2: 設(shè) G為 n 階正定陣， 向量組 kddd ?, 21關(guān)于 G共軛， 對正定二次函數(shù) ? ? ,21 cxbGxxxf TT ???由任意 開始， 依次進行 k 次精確線搜索： ( 1 ) ( ) , 1 , 2 , ,ii iix x d i k?? ? ? ?則： （１） kidgiTk ?,2,1,01 ???（２） ( 1)kx ? 是 ? ?xf在 kH上的極小點． 推論 : 當 nk ? 時， 為正定二次函數(shù)在 nR上的極小點． (1)x( 1)nx ?共軛梯度法 記： 11 ????? kkkk dgd ?左乘 ,1Gd Tk ?并使 1111???? ?kTkkTkk GddGdg?,01 ?? kTk dGd 得： （ HestenesStiefel公式） ?。? 00 gd ??—— 是一種特殊的共軛方向法 共軛梯度法基本性質(zhì) 定理 3: 對于正定二次函數(shù)， 采用精確線搜索 的共軛梯度法在 nm ? 步后終止， 且對 ni ??1 成立下列關(guān)系式： ,1,1,0,0 ??? ijGdd jTi ?,1,1,0,0 ??? ijgg jTi ?,iTiiTi gggd ??,1,1,00 ??? ijdg jTi ?（共軛性） （正交性） （下降條件） 系數(shù)的其他形式 （１） FR公式 111??? ?kTkkTkk gggg?（ 1964） （ 2） PRP公式 ? ?1111??????kTkkkTkk ggggg? （ 1969） FR共軛梯度法算法 ? ?( + 1 )+1 ,kkg f x??( 0 )00 ()d g f x? ? ? ??令Step1: 給出 ( 0 ) , 0 1 , : 0nx R k?? ? ? ? ?Step2: 如果 ,??kg停． Step5: 轉(zhuǎn) Step2. 計算 Step4: 11 ,k k k kd g d???? ? ?11Tkkk Tkkgggg???? ，Step3: 由精確線搜索求 ,k?計算 1 ,kk??令( 1 ) ( ) ,kk kkx x d?? ??并 令例 4： 用 FR共軛梯度法求解： ? ? ? ?2 2 ( 0 )1 2 1 2 131mi n 2 2 , 422 Tf x x x x x x x? ? ? ? ? ?解： 化成 ? ? cxbGxxxf TT ??? 21形式 ? ? ? ? ? ?