【正文】 軛方向法計算 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ù)可微的嚴(yán)格凸函數(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 ???由任意 開始， 依次進(jìn)行 k 次精確線搜索： ( 1 ) ( ) , 1 , 2 , ,ii iix x d i k?? ? ? ?則： （１） kidgiTk ?,2,1,01 ???（２） ( 1)kx ? 是 ? ?xf在 kH上的極小點． 推論 : 當(dāng) 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形式 ? ? ? ? ? ? ?????????????????????????????212121 0,21113,21xxxxxxxf( 0 ) 24x???????? ( 0 )0126g Gx b???? ? ?????(1) 0126d ??? ?????17500000 ??? GdddgTT?( 1 ) ( 0 )0026173817x x d???????? ? ???????116171217g Gx b??????? ? ??????? ?g(2) 289100110 ?? ggggTT???????????????????289210289900011 dgd ?171011111 ??? GdddgTT? ( 2 ) ( 1 )1111x x d???? ? ?????02 ?g * ( 2 ) 11xx ???? ????例 5： 用 FR共軛梯度法求解： ? ? ? ? ? ?2 2 ( 0 )1 2 011mi n 1 , 1 1 , 022 TTf x x x x d? ? ? ? ?解： 化成 ? ? cxbGxxxf TT ??? 21形式 ? ? ? ? ?????????????????2121 1001,21xxxxxf(0 ) 11x??????? (0 )011g Gx b??? ? ?????(1) ???????? ??010d100000 ??? GdddgTT? ( 1 ) ( 0 ) 0001x x d???? ? ?????( 1 )101g Gx b??? ? ?????11 ?g(2) 2100110 ?? ggggTT? ??????????????1210011 dgd ?5411111 ??? GdddgTT? ( 2 ) ( 1 )112515x x d????????? ? ???????( 2 )22515g Gx b???????? ? ???????2 1 / 5g ?(3)2211115TTgggg? ??2 2 1 131025d g d???????? ? ? ????????2222225TTgdd Gd? ? ? ?( 3 ) ( 2 )22125125x x d????????? ? ???????( 3 )3125125g Gx b???????? ? ???????32 ,25g ?注意： FR方法中初始搜索方向必須取最速下降方向，才滿足二次終止性。 FR共軛梯度法收斂定理 ? ?kx（ ）定理 4: 假定 ? ?xf 在有界水平集 ? ? ? ?? ?0nL x R f x f x? ? ? （ ）上連續(xù)可微， 且有下界， 那么采用精確線搜索下的 FR共軛梯度法產(chǎn)生的點列 ? ?kx（ ）至少有一個聚點 是駐點，即： (1) 當(dāng) 是有窮點列時， 其最后一個點是 ? ?xf 的駐點． (2) 當(dāng) 是無窮點列時， 它必有聚點， 且任一 聚點都是 ? ?xf的駐點． ? ?kx（ ）再開始 FR共軛梯度法算法 Step1: 給出 0 , 0 1 , : 0nx R k?? ? ? ? ?（ ）Step2: 計算 ? ?00 ,g f x?? （ ）如果 ,0 ??g停， Step4: 否則 .00 gd ??Step3: 由精確線搜索求 ,k?并令： 1 , 1 .kk kkx x d k k?? ? ? ? ?（ ） （ ）計算 ? ? ,kkg f x?? （ ）若 , 1 ??kkTkggg令 0 :,kxx?（ ） （ ） 轉(zhuǎn) Step2。 如果 ,??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ù)， 然后把它加到目標(biāo)函數(shù)中去，將約束問題的 求解化為一系列無約束問題的求解． 懲罰策略 ： 企圖違反約束的迭代點給予很大的 目標(biāo)函數(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。2P x M x x M x x? ? ? ? ?其中 M 是很大的正數(shù)． 求解此無約束問題得： ? ? ? ?12221MM MxxM?? ?當(dāng) M ? ?? 時， 有： ? ? ? ?? ? ? ? ? ?**1 2 1 2, , 1 , 1T T TMMx x x x??等式約束問題 ? ? ? ?m i n 1nf x x R?? ? ? ?. 0 1 , 2 , ,jst h x j J q? ? ?構(gòu)造： ? ? ? ? ? ?,P x M f x M P x??其中 0M ? 為參數(shù)，稱為罰因子． 分析： ? ? ? ? 21qjjP x h x???? ???當(dāng) x 不是可行解時， ? ? ? ?0 , 0 ,jh x P x??M 越大， 懲罰越重． 因此當(dāng) M 充分大時， ? ?xP~ 應(yīng)充分?。? 即 ? ?,P x M 的極小點應(yīng)充分逼近可行域， 進(jìn)而 逼近 (1)的最優(yōu)解． 不等式約束問題 ? ? ? ?m in 2nf x x R?? ? ? ?. 0 1 , 2 , ,ist g x i I p? ? ?構(gòu)造： ? ? ? ? ? ?,P x M f x M P x??分析： ? ? ? ?? ?21m i n 0 ,piiP x g x???? ???當(dāng) x 不是可行解時， ? ? ? ?0 , 0 ,ig x P x??M 越大， 懲罰越重． 因此當(dāng) M 充分大時， ? ?xP~ 應(yīng)充分小． 即 ? ?,P x M 的極小點應(yīng)充分逼近可行域， 進(jìn)而 逼近 (2)的最優(yōu)解． 一般約束問題 ? ? ? ?m in 3nf x x R?? ? ? ?0 1 , 2 , ,jh x j J q? ? ?? ? ? ?. . 0 1 , ,is t g x i I p? ? ?構(gòu)造： ? ? ? ? ? ? ? ?,4P x M f x M P x??? ? ? ?? ? ? ?2211m in 0 ,pqijijP x g x h x???? ???? ??????其中： 例 1： 用外罰函數(shù)法求解： ? ?01.m i n12221???