本文選題：部分可分非線性方程組　切入點(diǎn)：部分可分最優(yōu)化問(wèn)題　出處：《湖南大學(xué)》2016年博士論文

【摘要】：擬牛頓法是求解非線性方程組和最優(yōu)化問(wèn)題頗受歡迎的一類(lèi)算法.該類(lèi)算法具有超線性收斂速度,而且,若采用適當(dāng)線性搜索或信賴(lài)域技術(shù),算法可具有全局收斂性.然而,擬牛頓法產(chǎn)生的擬牛頓矩陣往往是稠密的,因此不能直接用于求解大規(guī)模問(wèn)題.來(lái)自科學(xué)計(jì)算和工程等領(lǐng)域的許多實(shí)際問(wèn)題一般都具有一些特殊的稀疏結(jié)構(gòu).比如微分方程采用有限元法或者有限差分法離散化后得到的非線性方程組,其Jacobian矩陣具有一定的稀疏結(jié)構(gòu).很多無(wú)約束優(yōu)化問(wèn)題可寫(xiě)成若干個(gè)分量函數(shù)的和,其中每個(gè)分量函數(shù)只跟少數(shù)幾個(gè)變量有關(guān).因此,根據(jù)問(wèn)題的稀疏特征或者目標(biāo)函數(shù)的特殊結(jié)構(gòu),設(shè)計(jì)高效的稀疏擬牛頓算法,具有重要的理論意義和實(shí)際應(yīng)用價(jià)值,也是優(yōu)化界關(guān)注的一個(gè)重要課題,并取得了一系列重要成果.目前已提出了多種稀疏擬牛頓法,這些算法充分利用了問(wèn)題的稀疏特征,并且保留了傳統(tǒng)擬牛頓法的超線性收斂性等重要性質(zhì).稀疏擬牛頓法已成為求解大規(guī)模非線性方程組和最優(yōu)化問(wèn)題的一類(lèi)重要算法.迄今為止,關(guān)于稀疏擬牛頓法的研究主要集中于對(duì)算法的局部收斂性質(zhì)的研究,對(duì)于算法的全局收斂性質(zhì)的研究工作很少.這是由于稀疏擬牛頓法產(chǎn)生的擬牛頓矩陣要保持問(wèn)題的稀疏結(jié)構(gòu),使得傳統(tǒng)擬牛頓法的某些重要性質(zhì)如對(duì)稱(chēng)正定性、最小變化性等發(fā)生了改變,從而大大增加了研究稀疏擬牛頓法的全局收斂性的難度.本文在對(duì)稀疏擬牛頓法的性質(zhì)進(jìn)行深入分析的基礎(chǔ)上,采用線性搜索技術(shù),研究求解非線性方程組和最優(yōu)化問(wèn)題的一些重要的稀疏擬牛頓法的全局收斂性.我們首先研究求解大規(guī)模非線性方程組的稀疏擬牛頓法.Schubert方法是較早被提出的用于求解方程組的稀疏擬牛頓法,作為Broyden秩一修正公式的稀疏推廣,Schubert修正公式能夠精確保持方程組的Jacobian矩陣的稀疏結(jié)構(gòu).但在實(shí)際計(jì)算中,由于Schubert修正公式過(guò)于嚴(yán)格地保持矩陣的稀疏結(jié)構(gòu),數(shù)值表現(xiàn)有時(shí)不如Broyden秩一方法好.在本文中我們重點(diǎn)關(guān)注部分可分離的非線性方程組,借助于分塊BFGS算法的思想,我們提出兩種分塊擬牛頓算法.當(dāng)非線性方程組的導(dǎo)數(shù)信息不可用時(shí),我們提出一種分塊Broyden秩一算法,算法中采用分塊Broyden秩一修正.該算法無(wú)需計(jì)算導(dǎo)數(shù),且能夠近似保持Jacobian矩陣的稀疏結(jié)構(gòu).當(dāng)非線性方程組的導(dǎo)數(shù)信息可通過(guò)自動(dòng)微分間接計(jì)算時(shí),我們提出一種分塊伴隨Broyden算法,算法中采用分塊伴隨Broyden修正.該修正公式也可近似保持Jacobian矩陣的稀疏結(jié)構(gòu),并保留了伴隨Broyden修正公式的線性不變性.我們采用一種無(wú)導(dǎo)數(shù)非單調(diào)線性搜索技術(shù)研究算法的全局收斂性,在適當(dāng)條件下,建立了上述兩種稀疏擬牛頓算法的全局收斂性.我們還證明,經(jīng)過(guò)一定的迭代步后,單位步長(zhǎng)可以取到.此時(shí),算法在方程組解的局部還原為單位步長(zhǎng)稀疏擬牛頓法,從而具有超線性收斂速度.我們還對(duì)算法進(jìn)行數(shù)值檢驗(yàn),并將該兩種稀疏擬牛頓算法與Broyden秩一方法和伴隨Broyden方法進(jìn)行了比較.結(jié)果表明,稀疏算法在迭代次數(shù),函數(shù)值計(jì)算次數(shù)和計(jì)算時(shí)間方面均有出色表現(xiàn).我們也將這兩種稀疏算法與Schubert方法進(jìn)行比較,數(shù)值結(jié)果進(jìn)一步驗(yàn)證了這兩種稀疏擬牛頓算法的優(yōu)越性.其次,針對(duì)目標(biāo)函數(shù)具有部分可分離結(jié)構(gòu)的無(wú)約束優(yōu)化問(wèn)題,我們提出一種稀疏的投影分塊PSB算法.算法針對(duì)目標(biāo)函數(shù)的Hessian矩陣的稀疏結(jié)構(gòu),采用分塊PSB修正.由于簡(jiǎn)單的分塊PSB修正公式不能保正Hessian矩陣的近似矩陣的正定性,從而不能保證擬牛頓方向是目標(biāo)函數(shù)的下降方向.因此我們對(duì)擬牛頓方向進(jìn)行投影,提出一種投影的分塊PSB算法,該算法可以保證產(chǎn)生目標(biāo)函數(shù)的一個(gè)充分下降方向.在適當(dāng)條件下,我們證明了采用Armijo或者Wolfe搜索的算法用于求解一致凸函數(shù)極小化問(wèn)題時(shí)具有全局收斂性和超線性收斂速度.此外我們還通過(guò)數(shù)值計(jì)算,將分塊PSB算法與已有的求解大規(guī)模最優(yōu)化問(wèn)題的著名的分塊BFGS算法以及有限內(nèi)存BFGS(L-BFGS)算法在30個(gè)測(cè)試問(wèn)題上進(jìn)行數(shù)值比較.結(jié)果表明,本文提出的分塊PSB算法在迭代次數(shù),函數(shù)值計(jì)算次數(shù),梯度值計(jì)算次數(shù)和計(jì)算時(shí)間方面均有較好的表現(xiàn).最后,我們研究求解對(duì)稱(chēng)非線性方程組的擬牛頓算法,基于自動(dòng)微分技術(shù),我們提出兩類(lèi)擬牛頓算法.首先,類(lèi)似于Powell對(duì)稱(chēng)化技術(shù),我們將伴隨Broyden修正公式對(duì)稱(chēng)化,提出一種對(duì)稱(chēng)伴隨Broyden修正.該修正公式保持了原伴隨Broyden修正公式的最小變化性質(zhì)和仿射不變性.此外,我們還提出一類(lèi)新的伴隨秩二擬牛頓修正公式,該修正公式不僅具有和BFGS修正公式類(lèi)似的正定性和最小變化性質(zhì),而且能夠精確保證擬牛頓矩陣與方程組的Jacobian矩陣沿?cái)M牛頓方向一致.我們證明,在適當(dāng)條件下這兩種算法均具有全局收斂性和超線性收斂速度.數(shù)值結(jié)果顯示,當(dāng)用于對(duì)稱(chēng)非線性方程組求解時(shí),這兩類(lèi)新算法相比于BFGS方法均具有優(yōu)勢(shì).
[Abstract]:......
【學(xué)位授予單位】：湖南大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類(lèi)號(hào)】：O242.23

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 盧慧芳;楊月婷;;一種新的修正有限內(nèi)存擬牛頓法[J];華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年01期

2 孫文瑜;擬牛頓法中的數(shù)值相關(guān)技術(shù)[J];高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào);1983年04期

3 張建中;雙邊投影擬牛頓法的收斂性[J];科學(xué)通報(bào);1988年18期

4 姜子文;;直接優(yōu)化矩陣分解因子的阻尼擬牛頓法[J];濱州師專(zhuān)學(xué)報(bào);1991年04期

5 楊富貴,盛松柏;錐模型擬牛頓法[J];高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào);1995年04期

6 高巖;極大值函數(shù)非光滑方程組的牛頓法和擬牛頓法[J];自然雜志;2000年01期

7 懷麗波;;利用函數(shù)值信息的修正多步擬牛頓法[J];南京大學(xué)學(xué)報(bào)數(shù)學(xué)半年刊;2007年01期

8 黃海;林穗華;;幾種修正擬牛頓法的比較[J];廣西民族師范學(xué)院學(xué)報(bào);2011年03期

9 桂勝華;張倩;邢麗;徐玲;;弱互補(bǔ)函數(shù)的拉格朗日-擬牛頓法[J];上海第二工業(yè)大學(xué)學(xué)報(bào);2005年04期

10 李亮;孫秦;;求解高維非線性?xún)?yōu)化的并行分塊對(duì)角擬牛頓法[J];南昌航空大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年01期

相關(guān)會(huì)議論文 前6條

1 時(shí)貞軍;孫國(guó);;對(duì)角稀疏擬牛頓法及其收斂特征[A];第六屆中國(guó)青年運(yùn)籌與管理學(xué)者大會(huì)論文集[C];2004年

2 王樂(lè)斌;王曉純;白玉星;高建嶺;;擬牛頓法在火災(zāi)作用下結(jié)構(gòu)倒塌機(jī)構(gòu)中的應(yīng)用[A];北京力學(xué)會(huì)第15屆學(xué)術(shù)年會(huì)論文摘要集[C];2009年

3 于杰;倪勤;;改進(jìn)的多步擬牛頓法及其收斂性[A];中國(guó)運(yùn)籌學(xué)會(huì)第十屆學(xué)術(shù)交流會(huì)論文集[C];2010年

4 樊宇璐;李世作;張志斌;;基于擬牛頓法的電力系統(tǒng)潮流計(jì)算[A];中國(guó)高等學(xué)校電力系統(tǒng)及其自動(dòng)化專(zhuān)業(yè)第二十四屆學(xué)術(shù)年會(huì)論文集（上冊(cè)）[C];2008年

5 劉洪偉;王明潔;章祥蓀;;基于非單調(diào)線搜索非擬牛頓法的全局收斂性[A];中國(guó)運(yùn)籌學(xué)會(huì)第八屆學(xué)術(shù)交流會(huì)論文集[C];2006年

6 樊宇璐;李世作;張志斌;;基于擬牛頓法的電力系統(tǒng)潮流計(jì)算[A];第二十屆電工理論學(xué)術(shù)年會(huì)論文集[C];2008年

相關(guān)博士學(xué)位論文 前3條

1 曹慧平;部分可分非線性方程組與優(yōu)化問(wèn)題的稀疏擬牛頓法[D];湖南大學(xué);2016年

2 周偉軍;擬牛頓法及其收斂性[D];湖南大學(xué);2006年

3 程萬(wàn)友;求解最優(yōu)化問(wèn)題的非線性共軛梯度法和自調(diào)比擬牛頓法[D];湖南大學(xué);2008年

相關(guān)碩士學(xué)位論文 前9條

1 陳金慧;帶函數(shù)值的多步擬牛頓法[D];南京理工大學(xué);2009年

2 于杰;改進(jìn)的多步擬牛頓法及其收斂性[D];南京航空航天大學(xué);2012年

3 王偉;不精確擬牛頓法的收斂性[D];大連理工大學(xué);2006年

4 金紅艷;求解大規(guī)模優(yōu)化問(wèn)題的有限記憶擬牛頓法[D];湖南大學(xué);2013年

5 馮冬冬;一類(lèi)精細(xì)修正牛頓法和擬牛頓法研究[D];中南大學(xué);2012年

6 夏丹丹;求不可約非負(fù)張量的最大特征值的擬牛頓法[D];南京航空航天大學(xué);2012年

7 孫國(guó);無(wú)約束優(yōu)化問(wèn)題的稀疏擬牛頓法[D];曲阜師范大學(xué);2003年

8 王娟;Hilbert空間中算子方程的不精確擬牛頓法的局部收斂性分析[D];大連理工大學(xué);2006年

9 李寶美;多維filter與兩項(xiàng)迭代算法[D];南京理工大學(xué);2013年

，

本文編號(hào)：1668352