（應(yīng)用數(shù)學(xué)專業(yè)論文）求解大規(guī)模無(wú)約束優(yōu)化與約束單調(diào)方程組的下降prp共軛梯度法.pdf

河南大學(xué)碩士學(xué)位論文 摘要 共軛梯度算法是求解最優(yōu)化問題的有效算法，它特別適合于求解大規(guī)模的最優(yōu) 化問題這一類算法的一個(gè)顯著的優(yōu)點(diǎn)是它具有較好的收斂性，而且存儲(chǔ)量也很小 但是，大部分共軛梯度法不能保證產(chǎn)生下降方向，有些共軛梯度算法雖然具有下降 性，但是也很強(qiáng)地依賴于算法所采用的線搜索本論文研究一種基于新的共軛條件 的p r p 共軛梯度算法，主要討論此方法的收斂性和數(shù)值表現(xiàn)全文共分四章 第一章，我們簡(jiǎn)要地介紹了數(shù)值最優(yōu)化的發(fā)展背景，本文所用到的一些記號(hào)、基 本概念、定義及本文的主要結(jié)果 第二章，我們?cè)趌 i ，t a n g 和w 西的修正p 1 0 如r i b 論渺p o l y a k ( p r p ) 共軛梯度法的基 礎(chǔ)上( 1 1 ，提出一種求解非凸極小化化問題的新方法，此方法的一個(gè)顯著特點(diǎn)是搜索 方向總保持下降，使用a r m i j o 型線搜索我們證明此方法具有全局收斂性，并對(duì)所提算 法做了大量的數(shù)值試驗(yàn)，結(jié)果表明我們的算法非常有效 第三章，我們提出求解凸約束的非線性單調(diào)方程組新的p r p 共軛梯度算法該 算法的優(yōu)點(diǎn)是，可用于求解大規(guī)模非線性方程組的問題，并證明了該算法的全局收 斂性 第四章，總結(jié)本文，從而使我們對(duì)求解無(wú)約束的非線性共軛梯度法有了更進(jìn)一 步的認(rèn)識(shí)，并提出一些值得繼續(xù)研究的問題 關(guān)鍵詞：無(wú)約束最優(yōu)化；共軛梯度法；p r p 方法；a r m i j o - t y p e 線搜索 i 河南大學(xué)碩士學(xué)位論文 a b s t r a c t c o n j u g a t eg r a d i e n tm e t h o di sa ni m p o r t a n ti t e r a t i v em e t h o df o rs o l v i n go p t i m i z a t i o n p r o b l e m s i ti sp a r t i c u l a r l yw e l c o m ei nt h es o l u t i o no fl a r g e - s c a l eo p t i m i z a t i o np r o b l e m s a g o o dp r o p e r t yo ft h ec o n j u g a t eg r a d i e n tm e t h o di si t sl o w e rs t o r a g ea n dg o o dc o n v e r g e n c e p r o p e r t y h o w e v e r ，m o s te x i s t i n gc o n j u g a t eg r a d i e n tm e t h o d sd on o tg u a r a b t e et og e t d e s c e n td i r e c t i o n sf o rt h eo b j e c t i v ef u n c t i o n a l t h o u g hs o m eh a v ed e s c e n t ，b u ta l s ov e r y d e p e n d e n to nt h ea l g o r i t h mu s e db yl i n es e a r c h i nt h i ss t u d y , b a s e do nt h ec o n d i t i o n so f n e wc o n j u g a t ep r pc o n j u g a t eg r a d i e n tm e t h o d t h i sm e t h o df o c u s e so nc o n v e r g e n c ea n d n u m e r i c a lp e r f o r m a n c e t h e r ea r ef o u rc h a p t e r si nt h i sp a p e r t h ef i r s tc h a p t e r ，w eb r i e f l yi n t r o d u c e dt h eb a c k g r o u n do ft h ed e v e l o p m e n to fn u - m e r i c a lo p t i m i z a t i o n ，s o m en o t a t i o n su s e di nt h i sp a p e r ，b a s i cc o n c e p t s ，d e f i n i t i o n sa n d m a i nr e s u l t s c h a p t e ri i ，b a s i n go nl i ，t a n ga n dw e ia m e n d m e n tp l o a k - r i b i 毛r e - p o l y a k ( p r p ) c o n j u g a t eg r a d i e n tm e t h o d 1 w ep r o p o s e dt ot h en e wm e t h o do fs o l v i n gt h ep r o b l e mo f n o n - c o n v e xm i n i m i z a t i o n t h i sm e t h o di sc h a r a c t e r i z e db yas i g n i f i c a n to v e r a l ld o w n w a r d d i r e c t i o no ft h es e a r c h ，u s i n ga r m i j o - t y p el i n es e a r c hp r o v et h i sm e t h o dh a v i n gg l o b a l c o n v e r g e n c e ，a n dt h ea l g o r r h mh a sd o n ea l o to fn u m e r i c a le x p e r i m e n t s t h er e s u l t s s h o wt h a to u ra l g o r i t h mi sv e r ye f f e c t i v e c h a p t e ri i i w ep r o p o s en e wp r pc o n j u g a t eg r a d i e n ta l g o r i t h mf o rs o l v i n gc o n - s t r a i n e dn o n l i n e a rm o n o t o n ee q u a t i o n s t h ea d v a n t a g eo ft h i si st h a ti tc a nb eu s e dt o s o l v el a r g e - s c a l en o n l i n e a re q u a t i o n so ft h ep r o b l e m ，a n dp r o v et h eg l o b a lc o n v e r g e n c eo f t h ea l g o r i t h m c h a p t e ri v ，t h o u g hc o n c l u d i n gt h i sp a p e r ，w eh a v ef u r t h e ru n d e r s t a n d i n go fm e t h o d w i t hs o l v i n gu n c o n s t r a i n e dn o n l i n e a rc o n j u g a t eg r a d i e n ta n dp r o p o s es o m ew o r t h w h i l et o c o n t i n u er e s e a r c h k e yw o r d s ：u n c o n s t r a i n e do p t i m i z a t i o n ；c o n j u g a t eg r a d i e n tm e t h o d ；a r m i j o - t y p e l i n es e a r c h ；p r pm e t h o d i i 關(guān)于學(xué)位論文獨(dú)立完成和內(nèi)容創(chuàng)新的聲明 了刪僦= 露鯔釜一 ，? ：q 。 ：t薯。：j 。 ti ， ，x i ，1 1 ， 學(xué)位中請(qǐng)丸“e 學(xué)位論文作者) 一釜名：；：z 復(fù)! ! = = ! 萋? 一誓0 鐮。0 五j f 移豫“l(fā) j ，j ：暑| j 。 ：爹譬? 孫t 鐫j j 2 j 卑一j , z 硼，孽目 囊；、，；，i 霎”0 ：譬囊參- j ，7 、了j 一，享i o 、+ 一。! 善 j # 一一 “ 1 鬻，關(guān)于學(xué)位論文著作權(quán)使用授權(quán)書。荔 學(xué)位獲得者( 學(xué)位論文作者) 釜名： 2 0年 月 日 學(xué)位論文指導(dǎo)教師鍪名：互毖么鷙 2 0年月 日 第一章緒論 最優(yōu)化理論與方法是一門應(yīng)用性很強(qiáng)的學(xué)科，它的起源可以追溯到微積分誕生 的年代然而，直到上世紀(jì)三四十年代，由于軍事和工業(yè)生產(chǎn)的迫切需要，才使得最 優(yōu)化技術(shù)得到蓬勃發(fā)展近年來(lái)，隨著計(jì)算機(jī)的發(fā)展和網(wǎng)絡(luò)的普及，各種優(yōu)化模型的 數(shù)值優(yōu)化算法在經(jīng)濟(jì)計(jì)劃、工程設(shè)計(jì)、交通運(yùn)輸?shù)阮I(lǐng)域得到廣泛的應(yīng)用 在生產(chǎn)管理、經(jīng)濟(jì)計(jì)劃、石油勘探、大氣模擬、航空航天、數(shù)據(jù)挖掘、工程設(shè)計(jì) 等以及許多高尖端的科技領(lǐng)域經(jīng)常出現(xiàn)未知變量越來(lái)越多大規(guī)模問題可以視為目 標(biāo)函數(shù)的結(jié)構(gòu)非常復(fù)雜，而且約束條件數(shù)量也十分龐大的優(yōu)化問題研究求解大規(guī) 模問題具有十分重要的理論和實(shí)際意義計(jì)算機(jī)領(lǐng)域的發(fā)展，以及國(guó)際互聯(lián)網(wǎng)絡(luò)的 出現(xiàn)，對(duì)求解大規(guī)模優(yōu)化問題提供了方便進(jìn)入2 1 世紀(jì)以來(lái)，求解大規(guī)模優(yōu)化問題的 算法設(shè)計(jì)以及理論創(chuàng)新已經(jīng)受到數(shù)學(xué)家們的廣泛關(guān)注 1 1非線性共軛梯度法概述 無(wú)約束最優(yōu)化問題的一般形式為： r a i nf ( z ) ，z r n ， ( 1 1 ) 其中函數(shù)，：r n _ 豫連續(xù)可微，且它在x k 處的梯度記作g ( x k ) ，并簡(jiǎn)寫為g k 求解問題( 1 1 ) ，通常采用迭代算法即給一個(gè)初始點(diǎn)x o r 幾，按照一定的準(zhǔn)則產(chǎn) 生一個(gè)點(diǎn)列 z 知】- ，使當(dāng)z 知是有限點(diǎn)列時(shí)，其最后一點(diǎn)是問題( 1 1 ) 的最優(yōu)解；當(dāng)z 七是無(wú) 窮點(diǎn)列時(shí)，它有極限點(diǎn)，且其極限點(diǎn)是問題( 1 1 ) 的最優(yōu)解，其迭代形式為： x k + l2x k + q 七d k ， 其中步長(zhǎng)o l 七由一些線搜索得出，毗為搜索方向 最速下降法，取d 七= 一g 七，即每步都以負(fù)梯度方向作為搜索方向由于負(fù)梯度 方向是目標(biāo)函數(shù)值下降的方向，故該方法稱為最速下降法這種方法每次迭代的運(yùn) 算量不大，且初始點(diǎn)不用很接近最優(yōu)點(diǎn)，但是其收斂速度慢 牛頓法是求解優(yōu)化問題的古老而有效的方法，取嗾= 一g i l 9 k ，( g 七是目標(biāo)函數(shù) 在z 七的h e s s e 矩陣) ，這個(gè)方向也源于牛頓方程g 七d 七+ g k = 0 ，稱為牛頓方向相對(duì)于其 】 河南大學(xué)碩士學(xué)位論文 它的求解無(wú)約束問題的方法，該方法在找到最優(yōu)點(diǎn)時(shí)需要較少的迭代次數(shù)和函數(shù)值 計(jì)算次數(shù)然而，牛頓法要求計(jì)算目標(biāo)函數(shù)的二階導(dǎo)數(shù)，并且當(dāng)?shù)c(diǎn)遠(yuǎn)離問題的解 時(shí)，h e s s e 矩陣可能不正定甚至奇異，從而導(dǎo)致牛頓法失敗 共軛梯度算法僅需要利用一階導(dǎo)數(shù)的信息，不僅克服了最速下降法收斂慢的 缺點(diǎn)，又避免了存儲(chǔ)和計(jì)算擬牛頓法所需的二階導(dǎo)數(shù)的信息共軛梯度法最早是 由h e s t e n e sf 2 1 和s t i e f e l 3 在1 9 5 2 年求解線性方程組 a x = b z 艫 ( 1 2 ) 時(shí)而獨(dú)立提出的，合作文章 4 詳細(xì)地討論了求解線性方程組的共軛梯度法的性質(zhì)以 及它和其他方法的聯(lián)系在a 為正定矩陣時(shí)，線性方程組( 1 2 ) 就等價(jià)于無(wú)約束最優(yōu)化 問題 1 一一 m i n f ( x ) = 丟za x + bz z r n ，( 1 3 ) 由此，h e s t e n e s 和s t i e f e l 的方法也可視為求二次函數(shù)極小值的共軛梯度法1 9 6 4 年f l e t c h e i 和r e e v e s 3 0 將此方法推廣到求解非線性極小化問題中，提出了求解非凸函數(shù)極小值 的共軛梯度方法 非線性共軛梯度法的迭代公式是 x k + l = z 知+ a k d k ，k = 0 ，1 ，( 1 4 ) 其中步長(zhǎng)o l k 由線搜索得出，x o 為初始迭代點(diǎn)，搜索方向毗由f 面公式得出 1 b 如果梏0 ( 1 5 ) 【一g k + 覦d k 一1 ，如果k 1 ， 其中鯫= v ，( 砜) ，仇是參數(shù)，鳳的不同取法對(duì)應(yīng)不同的非線性共軛梯度法，常見形 式為： 簇r ：磐( f l e t c h e r - r e e v e s 3 0 】，1 9 6 4 ) ； ( 1 6 ) “一1 鯫一1 茚哮掣 釅= 面9 ：麗( g k - - 了q k - 石1 ) ( p o l a k - r i b i e r e - p o l y a k 【5 】 1 9 6 9 ) ；( 1 7 ) 2 ( h e s t e n s e s - s t i e f e l 4 】，1 9 5 2 ) ； ( 1 8 ) 河南大學(xué)碩士學(xué)位論文 船k 面蓑爭(zhēng)磊( d a i - y u a n 【6 ，1 9 9 9 ) ； ( 1 9 ) d 一囂( c o n j u g a t e d e s c e n t f 7 1 9 8 7 ) ( 1 1 0 ) 艫一掣( l i u s t o r e y 【8 ，1 9 9 1 ) ( 1 1 1 ) 硭y 一日s = m a x 0 ，m i n z b y , p 日s ) ( d a i - y u a n 9 】，2 0 0 1 ) ( 1 1 2 ) 其相應(yīng)的共軛方法縮寫為f r 、p r p 、h s 、d y 、c d 、l s 、d y - h s 方法如果，是嚴(yán)格 二次凸函數(shù)，那么這些方法在使用精確線搜索且第一個(gè)搜索方向是最速下降方向時(shí)， 上面的非線性共軛梯度法等價(jià)對(duì)于非凸的極小化問題，這些方法則大不相同因 此，這些方法近年來(lái)受到廣泛關(guān)注 1 0 、 1 1 、 1 2 、【1 3 、 1 4 、【1 5 、【1 6 、 17 】它具有 算法簡(jiǎn)單、易于實(shí)現(xiàn)、存儲(chǔ)需求少等優(yōu)點(diǎn)，非常適合于大規(guī)模優(yōu)化問題因此，研究 共軛梯唐法有很日呂的理論和實(shí)際煮義 1 2線搜索 為了保證算法的全局收斂，需要利用某種線搜索方法來(lái)確定步長(zhǎng)因子q 七，它是 從迭代點(diǎn)釓沿搜索方向九尋找一個(gè)“好”的點(diǎn)作為下一個(gè)迭代點(diǎn)顯然，最好的點(diǎn)是 在這個(gè)方向函數(shù)值達(dá)到最小的點(diǎn)，步長(zhǎng)因子q 詹的計(jì)算也至關(guān)重要，下面我們就給出 幾種常用的確定步長(zhǎng)因子a 知的線搜索準(zhǔn)則 ( 1 ) 精確線搜索 求步長(zhǎng)因子q 七滿足 ，( z 七+ q 七d 七) = m i n f ( x k + a d k ) ，( 1 1 3 ) 即要求下一個(gè)迭代點(diǎn)是搜索方向如上的精確極小值點(diǎn) 因?yàn)榫_線搜索要求一個(gè)單變量函數(shù)的極小值，計(jì)算量較大，所以在實(shí)際計(jì)算 中常用非精確線搜索下面介紹幾種非精確線搜索： ( 2 ) a r m i j o 型線搜索 步長(zhǎng)因子a 知 o 滿足 ， 豇+ 口| c d ) f ( x 磚) + 6 q 七g - j d k ，( 1 1 4 ) 3 河南大學(xué)碩士學(xué)位論文 其中0 6 1 ( 3 ) 標(biāo)準(zhǔn)的w o l f e 線搜索 步長(zhǎng)因子q 七滿足 f ( x k + o t k d k ) ，( z 知) + , 5 a k g ；d k ， g ( x k + o e k d k ) ld k 盯9 2d k ， 其中0 6 0 - 1 是兩個(gè)常數(shù) ( 4 ) 強(qiáng)w o l f e 型線搜索 求步長(zhǎng)因子a 七滿足 ( 1 1 5 ) ( 1 1 6 ) f ( x k + a k d k ) s ( x k ) + 8 a k g - j d k ，( 1 1 7 ) i g ( x k + a k d k ) t d k l 0 - g - 丁d k ，( 1 1 8 ) 其中o 6 盯 1 是兩個(gè)常數(shù)當(dāng)仃= o 時(shí)，必有夕矗1 d k = 0 ，因此，強(qiáng)w | o l f e 型線搜索 是精確線搜索的一種推廣 ( 5 ) 廣義的w o l f e 型線搜索 求步長(zhǎng)因子q 七滿足 ，( z 七+ a k d k ) f ( x k ) + 6 a k g j d k ，( 1 1 9 ) 0 - 1 9 - j d k 冬g ( x k + a k d ) t d k 0 - 2 訂d k ，( 1 2 0 ) 其中0 0 - 1 1 ，o 2 0 上面所有的線搜索準(zhǔn)則，都要求搜索方向也是下降的，從而使目標(biāo)函數(shù)，( z ) 找 到最好的點(diǎn)稱滿足紙t 也 o 的搜索方 h - j d k 為下降方向，稱總是能產(chǎn)生下降方向的算 法為下降算法當(dāng)采用非精確線搜索方法時(shí)，不一定所有的非線性共軛梯度算法都 能保證每一步都能產(chǎn)生下降方向，此時(shí)大家一般采用負(fù)梯度方向作為搜索方向，但 是如果多次使用負(fù)梯度方向收斂速度會(huì)很慢，所以大家常常會(huì)重新開始 1 3p r p 方法 p r p 方法是f h p o l a k 、r i b i 爸r e 和p o l y a k 在1 9 6 9 年分別獨(dú)立提出的一種非線性共軛 梯度法，它簡(jiǎn)稱為p r p 方法，此方法被認(rèn)為是目前數(shù)值表現(xiàn)最好的共軛梯度法之一 4 河南大學(xué)碩士學(xué)位論文 因?yàn)楫?dāng)算法產(chǎn)生一個(gè)小步長(zhǎng)時(shí)，f i j p a p 方法定義的搜索方向如會(huì)自動(dòng)靠近負(fù)梯度方 向，從而具有自動(dòng)開始的功能，較為有效的避免了f r 方法可能連續(xù)產(chǎn)生小步長(zhǎng)的缺 點(diǎn) p o w e l l 1 s 證明了當(dāng)步長(zhǎng)s 七一0 ，8 k = x k + 1 一z & = q 七d k 時(shí)p r p 方法的全局收斂性， 并且證明了采取精確線搜索的p r p 方法對(duì)于一致凸函數(shù)是全局收斂的但對(duì)于一般 的一致凸函數(shù)，p o w e l l 1 9 舉出了一個(gè)反例，說明p f u p 方法也可能在幾個(gè)迭代點(diǎn)附近 循環(huán)，而其中任何一個(gè)迭代點(diǎn)都不是目標(biāo)函數(shù)，( z ) 的穩(wěn)定點(diǎn)，因而破壞了算法的全局 收斂性 如果使用非精確線搜索，比如強(qiáng)w o l f e 型線搜索，d 面 2 0 】舉例說明了即使原函數(shù) 一致凸，且參數(shù)0 0 和0 p 1 ，令 q 知= m a x 乃而# l g 礦d a l ，j = 0 1 ) ， ( 1 2 1 ) 使其滿足 f ( x 知+ 1 ) 一f ( x 知) 一引j q 七d 知1 1 2 ，( 1 2 2 ) 和 c 1 9 ( x k + a ) 1 1 2 9 ( z 1 ) t d 七+ 1 - c 2 l l g ( x k + 1 ) 1 1 2 ，( 1 2 3 ) 其中o c 2 1 c 1 是常數(shù) 5 河南大學(xué)碩士學(xué)位論文 另外，d a i 采 y u a n 2 2 討論t p r p 方法的一個(gè)新性質(zhì)，即取常數(shù)因子的p r p 方法在 每次迭代都產(chǎn)生一個(gè)下降的方向，而且證明了其全局收斂性但這種常數(shù)步長(zhǎng)因子 的選取依賴于l i p s c h i t z 常數(shù)厶而常數(shù)l 往往不能預(yù)先估計(jì)，因此在實(shí)際計(jì)算中不容 易操作 h a g e r 和z h a n g 2 3 提出了一種不依賴線性搜索能產(chǎn)生下降方向的非線性共軛梯 度法： 似坐掣- - s k _ l y k _ 1 k - 1 ) ，m 2 4 ， 1 rr - k - t 頭下8 k2x k + l x k ，y k - 159 一g k - 1 近來(lái)，w e i ，y a o 和l i u 2 4 1 提出了一個(gè)結(jié)合f r 和p r p 方法的共軛梯度法公式： 硝y l ：g k t ( g a 丁- 黜一g k - 1 ) ( w e i - y a o - l i u 2 4 , 2 0 0 6 ) , 夕一l g k 一1 該方法在s w p 線搜索條件下具有充分下降和仇o 的性質(zhì)，同時(shí)在g r i p p o - l u c i d i 線搜 索、w o l f e - p o w e l l 線搜索和精確線搜索條件下都具有全局收斂性除了以上對(duì)p r p 共 軛梯度方法的收斂性介紹以外，關(guān)于其他的共軛梯度算法，及其修正算法和相關(guān)算 法的收斂性分析等問題，可參考h a g e r $ f l z h a n g 笆j 綜述性文獻(xiàn) 1 2 及d a i 和y u a n 關(guān)于非 線性共軛梯度法的專著f 2 2 】 最后，我們給出求解問題( 1 1 ) 的非線性共軛梯度法( p r p 算法) 的算法步驟如 下： 算法1 3 1 步0 取初始點(diǎn)z o r n ，d o = 一g o 令k ：= 0 步1 若i | 鯫ij = 0 ，則算法終止，得問題的解瓢，否則，轉(zhuǎn)步2 步2 由p 糾式確定d ，其中鳳= 茚即 步3 由線搜索確定步長(zhǎng)o e 七，令x k + 1 = z 七- i - a k d k 步4 令k ：= k + 1 ，轉(zhuǎn)步1 6 河南大學(xué)碩士學(xué)位論文 1 4 本文主要工作 本論文研究新的共軛條件的p r p 共軛梯度算法，主要討論此方法的收斂性和數(shù) 值表現(xiàn) 第二章，l i ，t a n g 和w e i z 提出了求解無(wú)約束最優(yōu)化問題的一種p r p 方法，并分 析了該算法求解一致凸函數(shù)的及小化最優(yōu)解的收斂性，本章基于【2 5 提出的共軛梯 度法，修正【1 中的算法，使之能夠求解非凸極小化問題此方法的一個(gè)顯著特點(diǎn)是搜 索方向總保持下降，使用a r m i j o - t y p e 線搜索我們證明此方法具有全局收斂性，并對(duì) 所提算法做了大量的數(shù)值試驗(yàn)，結(jié)果表明我們的算法非常有效 第三章，推廣第二章所提算法使之求解凸約束的非線性單調(diào)方程組的問題該 方法不需要j a c o b i a n 矩陣信息，迭代簡(jiǎn)單，存儲(chǔ)量小 7 河南大學(xué)碩士學(xué)位論文 1 5本文所用記號(hào) z ：實(shí)變量 ，( z ) ：目標(biāo)函數(shù) n ：目標(biāo)函數(shù)的維數(shù) z 七：第k 次迭代點(diǎn) 酞：全體實(shí)數(shù)組成的集合 r n ：全體n 維實(shí)向量組成的集合 g k ：目標(biāo)函數(shù)，( z ) 在點(diǎn)x k 處的梯度 j ：幾階單位矩陣 ：向量的無(wú)窮模 怙：矩陣的f r o b e n i u s 范數(shù) i i ：向量的歐氏范數(shù) f ( z ) ：非線性方程組 a t ：矩陣a 的轉(zhuǎn)置 j ：?jiǎn)挝痪仃?8 第二章一種基于新共軛條件的p r p 共軛梯度算法 2 1引言 本章我們考慮大規(guī)模無(wú)約束優(yōu)化問題 r a i n ，( z ) ，z r n ， 其中函數(shù)，：時(shí)_ r 連續(xù)可微，且它在a ：k 處的梯度記作g ( x 知) ，并簡(jiǎn)寫為g j c p r p 方法是由p o l a k 、r i b i 色r e 和p o l y a k 在1 9 6 9 年獨(dú)立提出的種非線性共軛梯度 法，這種方法具有如下迭代形式： x k + l2x k 十o c k d k ，k = 0 ，1 ， ( 2 1 ) 其中 d 七= 一- - 9 9 知k , + 風(fēng)d 憊一。，：蓁：蓁： c 2 2 ， 其中參數(shù)覷由以下公式計(jì)算： 雕r p ：亟拿二旦出 2 0 0 7 年，l i ，t a n g 和w e i 1 提出了求解無(wú)約束最優(yōu)化問題的一種p r p 方法，并分析了該 算法求解一致凸函數(shù)的極小化最優(yōu)解的收斂性，本章基于【2 5 提出的共軛梯度法，修 正【1 中的算法，使之能夠求解非凸極小化問題 2 2算法設(shè)計(jì) 本節(jié)，簡(jiǎn)單描述l i ，t a n g 和w e i 1 提出的修正p r p 共軛梯度方法首先給出兩個(gè) 假設(shè)條件： 假設(shè)2 2 1 水平集廠= z r n f ( z ) ，( z o ) ) 有界 假設(shè)2 2 2 在廠的鄰域上，可微且梯度l 匆s 咖i t 璉續(xù)，即存在l 滿足 i t g ( x ) 一g ( y ) l ls 工1 1 2 可憶比，y ( 2 3 ) q 河南大學(xué)碩士學(xué)位論文 由假設(shè)可知存在一個(gè)正常粉使得 i b ( z ) i i 可，v z 尸 ( 2 4 ) 在求解無(wú)約束最優(yōu)化問題( 1 1 ) b f l ，為了得到目標(biāo)函數(shù)的更精確逼近，w e i ，l i 和q i 提 出了一個(gè)新的割線條件【2 6 】： b k 8 k 一1 = 皖一1 = 譏一1 + a j c 一1 8 k 一1 ，( 2 5 ) 其中鼠是v 2 ，( z 知) 的一個(gè)近似，并且 址= 坐吐氣黼 型生 ( 2 6 ) 在( 2 5 ) 式提出的新的割線條件的基礎(chǔ)上，l i ，g 和w 西【1 修改了關(guān)于鳳的p r p 方法， 即 盧f p r p _ 丞， ( 2 7 ) 其中玩一1 = y k 一1 + m a x a 一1 ，o s k 一1 由以上式子我們可以看出，這個(gè)新的方程不僅 包含梯度值信息，而且包含函數(shù)值信息結(jié)合強(qiáng)w 6 l 缸p o w e u 線搜索，由( 2 7 ) 式所定義 的共軛梯度法可用于求解一致凸極小化問題，但是求解非凸極小化問題的收斂性分 析沒有給出 近來(lái)，z h a n g 、z h o u _ ； 1 l i 2 5 提出修正的p r p 共軛梯度法，即 d 七= 一- 鯫g k + 鳳d 七一，一日七弧一。翥蓁：蓁；： c 2 8 ， 其中釓= 碳蠐結(jié)合( 2 5 ) 所定義的緱一1 ，有 虻 咄 如果枉o ( 2 9 ) 【一鯫+ 硝p 即呶一1 一靠玩一1 如果k 1 ， 。 其中靠= 秩蠐，易知，由上述所定義的比滿足 g - j d k = 一i i 鯫愾 ( 2 1 0 ) 下面我們提出新的算法( n p r p 算法) ，如下 步0 取初始點(diǎn)z o r n ，假設(shè)o 6 1 ，d o = 一g o 令k ：= 0 河南大學(xué)碩士學(xué)位論文 步1 若i l 鯫l = 0 ，則算法終止 步2 由( 2 9 ) 式確定如 步3 由下式確定步長(zhǎng)q 七 f ( x k + o e k d k ) 一f ( x k ) - - 5 1 1 a k d k 1 2 ，( 2 1 1 ) 令x k + 1 = z 七+ q 島d 七 步4 令k ：= k + 1 ，轉(zhuǎn)步1 2 3收斂性分析 本節(jié)我們給出新算法的收斂性分析為了證明的需要我們首先給出幾個(gè)引理 引理2 3 1 在假設(shè)幺2 1 2 2 堿立的條件下，有 證明：由( 2 1 1 ) 式得口七因此，由( 2 1 0 ) 和( 2 1 1 ) n - i 得 + 1 一 一6 f q 七比i i 2 0 ， ( 2 1 2 ) ( 2 1 3 ) 且p i k 是遞減序列，且 z 七】在，中，從假設(shè)2 2 1 2 2 2 可以得到存在一個(gè)常數(shù)，+ ，使 得 1 i m = ，+ ，( 2 1 4 ) 從( 2 1 4 ) 可得 ( 一 一1 ) + o o k - - o 再由( 2 1 3 ) 可得( 2 1 2 ) 證畢 引理2 3 2 在假設(shè)2 2 j 2 ，2 堿立的條件下，有 其中l(wèi) 是由假設(shè)2 2 綻義的 i 玩一1 | 2 l i i s , i i ， 1 1 ( 2 1 5 ) 2 k d k q 6 腳 河南大學(xué)碩士學(xué)位論文 證明：由( 2 1 3 ) 式得 x k 廠，v k 1 另一方面，由中值定理可得存在訊【0 ，1 ，使得 ( 2 1 6 ) + 1 一 = 夕( 。知) + 叼( x k + 1 一z 七) t ( z 七+ 1 一z 七) = g ( x 七+ ，7 奄s 七) t 8 k ( 2 1 7 ) 1 ：1 = 1 ( 2 1 0 ) 式得 z i c + 輒s 七= x k + 吼( z 知+ 1 一。知) 靜， 其中掰表示廠的閉凸包，吼定義為 入七 = 0 ，使得 g k l i ，v k 0 ， d k l i m ，v k 0 證明：f i 了d k 的定義和( 2 3 ) 、( 2 4 ) 、( 2 1 0 ) 、( 2 1 8 ) 可得 酬i l g k l l + 2 必筍 彳+ 1 2 ( 2 1 8 ) ( 2 1 9 ) 河南大學(xué)碩士學(xué)位論文 引理( 2 3 1 ) 表明當(dāng)k 一。o 時(shí)a k d k 一0 ，存在一常數(shù)，y ( 0 ，1 ) 和一整數(shù)，使得對(duì)于所 有的k k o 有以下不等式成立： 裂嘗吣。i l d k 一。雌7 百孺q 知一1 1 l i s7 因此，對(duì)任意k k o l 了+ 圳如一1 峪7 ( 1 + 7 十7 2 十+ 礦一幻一1 ) 4 - 7 k - k 。l j d k o l l 擊+ l l d k 。i l ， 令m = m a x l l d l l l ，i i d 2 l l ，i l d k o l l ，吉+ i l d k 。i i ，一z 。到ii 以l f m 證畢 利用以上引理，給出定理以及證明 定理2 3 1 在以中，步長(zhǎng)q 知由弱a 帆力d 型線搜索償j 砂得到假設(shè)2 2 1 2 2 2 成 立，有 l i mi n fi i g kl l = 0 ( 2 2 0 ) 尤 o o 證明：假設(shè)結(jié)論不成立，則存在一個(gè)正常數(shù)使得 | f 鯫l ，k 0 ( 2 2 1 ) 如果l 蛐i n f q j c 0 ，由( 2 1 0 ) 和( 2 1 2 ) 知l 歸i i l f l l = 0 ，與( 2 1 2 ) 矛盾假設(shè)岫i n f o l k = 尤啼o 。擰，c 斗o 。 0 ，存在一個(gè)無(wú)限集合k 使得 ，l i m a 南= 0 ， ( 2 2 2 ) k 。+ o 。 a 南由( 2 1 1 ) 得出，存在一個(gè)充分大的指枋誘使得七石，k i 存在p 一1 a k 不滿足( 2 1 1 ) ， 即 ，( 。七4 - p - ：o , d k ) f ( x k ) 一p - 2 a l l a k d k1 1 2 ( 2 2 3 ) 由中值定理、引理2 3 1 和式( 2 3 ) 、( 2 1 0 ) ，可知，存在r k ( 0 ，1 ) ，使得 f ( x k 十p - z a k d k ) 一f ( x k ) = p - ：a k g ( x 七+ 班p 一1 q 膏d k ) t d k = p - ：a g 奄- r d k + p 一1 0 f ( 9 ( z 磨4 - 叼p 一1 a k d k ) 一夕七) t d k p - ：a k 夕七t d k + l p 2 a 20 比f(wàn) 1 2 ， 1 3 河南大學(xué)碩士學(xué)位論文 代入不等式( 2 2 3 ) ，得到所有的七仡， i 舊七i | 2 p - 1 ( l + 6 ) 口南l i 毗l f 2 由_ 【如) 有界及啦i n f q k = 0 可得l 啦i n fl = 0 ，與( 2 。2 1 ) 矛盾，所以結(jié)論成立證畢 2 4 數(shù)值試驗(yàn) 本節(jié)，對(duì)給出的n p r p 算法，從數(shù)值計(jì)算的角度，檢驗(yàn)其數(shù)值效果，并與標(biāo)準(zhǔn)p r p 方 法進(jìn)行數(shù)值比較所有的算法都采用f o r t r a n 編程，并在c p u 處理器為1 6 g h z ，r a m 內(nèi) 存為5 1 2 m 的電腦上實(shí)現(xiàn)，對(duì)7 3 個(gè)大規(guī)模無(wú)約束優(yōu)化問題進(jìn)行測(cè)試，對(duì)于每個(gè)問題，改 變其維數(shù)，測(cè)試維數(shù)1 0 0 0 ，2 0 0 0 ，1 0 0 0 0 部分測(cè)試問題是從c u t e 2 7 函數(shù)庫(kù)里提取 的，其f o r t r a n 表達(dá)式可以見n a n d r e i 的主頁(yè)采用下面的終止準(zhǔn)則 l i g ( z k ) l i 1 0 ，( 2 2 4 ) 為了評(píng)估算法的性能，我們?cè)谕瑯拥膯栴}上還對(duì)常規(guī)的p r p 方法進(jìn)行了試驗(yàn)，算法和 程序可以從j n o c e d a l s 的主頁(yè)上下載，網(wǎng)址是h t t p ：w v w e c e n o r t h w e s t e r n e d u - n o c e d a l l s o f t w a r e h t m l 在運(yùn)行上述程序的時(shí)候，所有的參數(shù)值都是默認(rèn)的，并使 用終止準(zhǔn)貝j j ( 2 2 4 ) ，此外，若算法求解問題時(shí)函數(shù)值計(jì)算次數(shù)超過2 0 0 0 ，則程序?qū)⒈黄?終止 我 f 用d o l a n 和m o r d 2 s 提供的方式比較各種算法的性能，具體如下：假設(shè)使用 種算法同時(shí)求解唧個(gè)測(cè)試問題，對(duì)測(cè)試問鼢和算法s ，令如，。為算法s 求解問題p 所 用的時(shí)間，定義 亡d 8 壇s2 盂麗荔麗 即求解問題s 各種算法的效率，其中s 為算法集合，顯然，。 1 對(duì)所有的s 和p ，取 參數(shù)7 m 仲，。，若算法s 不能成功求解問題p ，則直接取飾，。= r m 為了估計(jì)算法s 對(duì) 所有測(cè)試問題的效率，令 1 p s ( 7 ) 。恚防p ：伽7 1 ， 其中 】表示集合中元素的個(gè)數(shù)，p 表示測(cè)試問題集合p 8 ( 丁) 是飾一的分布函數(shù)且 有p 。( 7 ) 1 可見，幾( 丁) 的值越大，則算法的數(shù)值效果越好下面兩個(gè)圖表是算 1 4 河南大學(xué)碩士學(xué)位論文 法n p r p 和p r p 分別基于迭代次數(shù)、函數(shù)值計(jì)算次數(shù)s s c e u 運(yùn)_ 算時(shí)間的分布函數(shù)p ( 丁) 曲 線 數(shù)值試驗(yàn)表明，算法n p i ：l p 和p r p f i 邑成功算出所有的測(cè)試問題，從下面兩個(gè)圖表 我們清楚的看到，算法n p r p 的曲線總是在上面，這表明算法n p r p 是這兩種方法中 最好方法，它需要更少的迭代次數(shù)、更少的函數(shù)值計(jì)算次數(shù)由圖我們也可以看出， 算法n p r p 要比算法p r p 節(jié)省計(jì)算時(shí)間 1 5 河南大學(xué)碩士學(xué)位論文 圖2 1 基于迭代次數(shù)的比較 1 6 河南大學(xué)碩士學(xué)位論文 圖2 2 基于函數(shù)值計(jì)算次數(shù)的比較 1 7 第三章求解凸約束的單調(diào)非線性方程組的共軛梯度法 3 1引言 考慮下面的約束非線性方程組問題：定義向量z 瞅使得， f ( x ) = 0 ，z q ， 其中qc 舯是非空閉凸集，f ：艫_ 黔連續(xù)單調(diào)，即 ( 3 1 ) ( f ( x ) 一f ( 秒) ，z y ) 0 vi t , ，y r n ( 3 2 ) 本節(jié)，我們提出一種求解凸問題( 3 1 ) 共軛梯度算法該方法可以存儲(chǔ)量小、迭代簡(jiǎn) 單 3 2 算法設(shè)計(jì) 令效益函數(shù) p ( z ) = 1 1 1 f ( z ) 愾 則問題( 3 1 ) 等價(jià)如下無(wú)約束最優(yōu)化問題 蛐 p ( z ) $ r n ) ，( 3 3 ) 其中p ：r n _ r 是連續(xù)可微函數(shù)本章所提共軛梯度法的迭代公式是 x k + l2x k + 口忌反， 其中步長(zhǎng)q 奄由線搜索得出，搜索f j 向d 七由下式?jīng)Q定 呶= 二竺+ 鳳毗一。一幺玩一。：蓁：三三： 其中矗= 矗譬澤，和菇一1 = 班一1 + m 越 a 七一1 ，o 8 七一1 且覷定義為 鳳= 縟， ( 3 4 ) ( 3 5 ) ( 3 6 ) 河南大學(xué)碩士學(xué)位論文 與第二章所定義的a 南一1 不同，設(shè) 址，= 墜摯 ( 3 7 ) 可知也總滿足 ( 風(fēng)，d k ) = 一i | 最愾( 3 8 ) 為了引入我們的算法，我們先介紹下投影算子的定義：從映射q 是舯上的一個(gè) 非空閉凸子集： h ：= 盯g r a 分i n n 怕一z l l ，vx 艫， 其中i i 表示2 范數(shù)，算子的一個(gè)重要的性質(zhì)是不擴(kuò)張性，即 l i p q x 一p q 可川i i z y l l ，vz ，y 妒 算法3 2 1 步0 給定初始點(diǎn)z o q 和常數(shù)p ( 0 ，1 ) ，仃( 0 ，1 ) ，盧 0 ，令k ：= 0 步1 如果最= 0 ，算法終止，如由p 糾得到 步2 確定步長(zhǎng)札= m a x p p i ：i = 0 ，1 ，) 滿足 ( f ( x k + t 七d k ) ，d k ) 冬- - o t k l l d k l l 2 ， ( 3 9 ) 令魂：= x k + t k d k 步3 計(jì)算 x k + l = 【z 矗一a k f ( z k ) ， 其中 a 七= 聳播 步4 令：= 斃+ 1 ，轉(zhuǎn)步i 注記3 2 2 孟是p j j 的解，使得f ( 2 ) = 0 ，并且互q 由f 是單調(diào)的，我們得到 伊( 釓) ，牙一z k ) 0 ， 假設(shè)給定某個(gè)搜索方向也，通過沿搜索方向毗實(shí)施某種線性搜索，產(chǎn)生點(diǎn)張= z 七- 4 - q 七d k ，若 ( f ( z k ) ，x k z k ) 0 ， 河南大學(xué)碩士學(xué)位論文 這意味著超平面 a 知= z r n l 0 使得 f ( x ) 一f ( y ) i i l i i x 一矽l l ，v z ，y q ( 3 1 0 ) 假設(shè)3 3 2 如果f 單調(diào)且三枷如t 比連續(xù)，則有 ( f ( z ) 一f ( 暑) ，z y ) 0vz ，y q ( 3 1 1 ) 假設(shè)3 3 31 ：1 墨4 ( s j ) 的解集s 非空 引理3 3 1 對(duì)所有忌 0 ，存在一個(gè)非負(fù)數(shù)滿足p 圳 證明：首先，如果在第k 次迭代該算法終止，即風(fēng)= 0 ，因此z 知是一個(gè)解下面假 設(shè)對(duì)于所有的七，凡0 ，因此由( 3 8 ) 矢g d k 0 假設(shè)算法產(chǎn)生有界無(wú)限序列 z 知 我 們現(xiàn)在證明線搜索( 3 9 ) 具有有限終止性，若t 如p ，貝u t k = p - i t k 不滿足( 3 9 ) ，即 一怛( ) ，d k ) 0 ，使得 l i f ( x k ) l l m ( 3 1 4 ) 證明：對(duì)于任一牙s ，由不放大的投影算子，我們有 | i z 七+ 1 一牙1 1 2 = i i p q x k c t k f ( z k ) 】一面i | 2 i i z 七一a k f ( z k ) 一孟| | 2 = i l z j c 一孟1 1 2 2 a k i f ( z k ) ，x k 一牙) + a 2 1 l f ( z k ) 1 1 2 i | z 七一牙i f 2 2 a k ( f ( z k ) ，x k 一魂) + q 2 l l f ( z k ) 1 1 2 = i i x 七- z l l 2 一蘆 i 慨一刮2 ，( 3 1 5 ) 所以對(duì)于所有的k 都有 f ( x k ) l i = l i f ( z k ) 一f ( 牙) i | l l l x 七一圣l i l l l x o 一牙m(xù) 河南大學(xué)碩士學(xué)位論文 令m = l i i x o 一別，即得( 3 1 4 ) 證畢 根據(jù)上面的引理，我們現(xiàn)在分析算法( 3 2 1 ) 的全局收斂性： 定理3 3 4 假設(shè)條t c 3 s s 一3 3 減立，序列 z 七) 和 魂) 由算法舅幺j 生成則有 l 徊i n fi l 凡0 = 0 ( 3 1 6 ) r - - - * 證明：假如( 3 1 6 ) 不成立，存在e 0 使得 l i 凡l i e vk 0 ( 3 1 7 ) 由( 3 8 ) 可知| | 最l i i i d y l l ，所以 i i d k l i e vk 0 ( 3 1 8 ) 由沁的定義得 址墮辭迅粼忪洲乩( 3 1 9 )饑2 可麗廣一s 麗礦惻i 2l j 通過定義玩和假設(shè)2 2 2 ，可得 | i 玩一1 l f = i f 耖k + m a x ；l k ，o s k l i l 秒- 4 - l s k l f i l y k l f + l l t s 磚l l 2 l i i s k l l 類似引理2 3 3 的證明可知存在正標(biāo)量c ，使得 i i d k l i d 所以對(duì)( 3 1 2 ) ，和不等式( 3 1 7 ) ，( 3 1 8 ) 所有足夠大的七滿足 枷鳧i i m i n 掘而p 麗i i f k l l 2 川, 毗 n l i n i n e ，南) ， 這與( 3 1 3 ) 矛盾，所以結(jié)論成立證畢 ( 3 2 0 ) 第四章結(jié)論 本文主要研究求解無(wú)約束最優(yōu)化問題，以及求解凸約束的非線性單調(diào)方程組的 共軛梯度算法，提出了改進(jìn)的算法并對(duì)算法進(jìn)行了收斂性分析首先在修正p r p 共 軛梯度法的基礎(chǔ)上，提出求解大規(guī)模無(wú)約束優(yōu)化問題的一種新方法，此方法的特殊 優(yōu)勢(shì)在于搜索方向總保持下降，并證