【摘要】：互補(bǔ)問(wèn)題是優(yōu)化領(lǐng)域中的一個(gè)經(jīng)典而重要的研究課題.它在工程、經(jīng)濟(jì)與交通均衡等領(lǐng)域都有著廣泛的應(yīng)用.而稀疏優(yōu)化是優(yōu)化領(lǐng)域的一個(gè)新的研究課題,它的理論、模型和算法正在迅猛發(fā)展.求互補(bǔ)問(wèn)題的稀疏解,是互補(bǔ)問(wèn)題和稀疏優(yōu)化兩課題的融合,具有重要的理論和應(yīng)用價(jià)值.本文初步探討了互補(bǔ)問(wèn)題稀疏解的一些理論,例如存在性和唯一性等,并提出了四種有效算法求解互補(bǔ)問(wèn)題的稀疏解.主要結(jié)果概括如下：針對(duì)線性互補(bǔ)問(wèn)題稀疏解,在理論方面,給出了Z矩陣線性互補(bǔ)問(wèn)題稀疏解的唯一性.在算法設(shè)計(jì)方面,借助FB互補(bǔ)函數(shù),提出了一個(gè)帶有p(0p1)范數(shù)正則項(xiàng)的無(wú)約束極小化模型.該模型隨著正則參數(shù)的減小能夠很好地逼近稀疏解.隨后建立了局部最優(yōu)解每一非零分量的閾值下界.該下界在數(shù)值計(jì)算中,對(duì)確定零分量起到了精確的界定作用；接著考慮了如何選取合適的正則參數(shù),使最優(yōu)解達(dá)到希望的稀疏度；最后,基于以上理論,提出序列光滑梯度算法(SSG)來(lái)求解lp范數(shù)正則極小化模型.數(shù)值實(shí)驗(yàn)表明SSG算法能夠有效地求解lp范數(shù)正則極小化模型并得到線性互補(bǔ)問(wèn)題的稀疏解.為了進(jìn)一步提高求解線性互補(bǔ)問(wèn)題稀疏解算法的效率,我們將互補(bǔ)約束轉(zhuǎn)化為投影形式的不動(dòng)點(diǎn)方程,由此提出了一個(gè)帶有f1范數(shù)正則項(xiàng)的投影約束極小化模型.緊接著給出了正則問(wèn)題子問(wèn)題解的閾值表示定理,并由此設(shè)計(jì)了一種收縮閾值投影算法(STP).最后,應(yīng)用此算法求解上述l1正則投影極小化問(wèn)題,并給出了算法的收斂性.數(shù)值實(shí)驗(yàn)表明,STP算法能有效的求解l1正則投影極小化模型,而且能得到]LCPs的高質(zhì)量稀疏解.在求解線性互補(bǔ)問(wèn)題稀疏解時(shí),為了更好的逼近向量的l0范數(shù),我們提出了一個(gè)帶有l(wèi)1/2范數(shù)正則項(xiàng)的投影約束極小化模型,進(jìn)而設(shè)計(jì)了一種半閾值投影算法(HTP),并建立了算法的收斂性.最后數(shù)值試驗(yàn)說(shuō)明HTP算法能有效求解l1/2正則投影極小化問(wèn)題,并且輸出LCPs的高質(zhì)量稀疏解.針對(duì)非線性互補(bǔ)問(wèn)題的稀疏解,首先提出了一種帶有f1范數(shù)正則項(xiàng)的投影約束極小化模型,接著設(shè)計(jì)了外梯度閾值算法(ETA)并給出了算法的收斂性分析,證明了ETA算法產(chǎn)生的序列的任一聚點(diǎn)就是NCP問(wèn)題的解.最后,數(shù)值實(shí)驗(yàn)顯示ETA算法能有效求解l1正則投影極小化模型,并且能輸出余強(qiáng)制非線性互補(bǔ)問(wèn)題的高質(zhì)量稀疏解.最后總結(jié)了本文的主要貢獻(xiàn),并對(duì)進(jìn)一步可能的研究方向進(jìn)行了展望.
[Abstract]:Complementarity problem is a classical and important research topic in the field of optimization. It is widely used in engineering, economy and traffic balance. Sparse optimization is a new research topic in the field of optimization, and its theory, model and algorithm are developing rapidly. Finding the sparse solution of the complementarity problem is the fusion of the complementary problem and the sparse optimization problem, which has important theoretical and practical value. In this paper, we discuss some theories of sparse solution of complementarity problem, such as existence and uniqueness, and propose four effective algorithms to solve sparse solution of complementarity problem. The main results are summarized as follows: for the sparse solution of linear complementarity problem, the uniqueness of sparse solution for Z-matrix linear complementarity problem is given in theory. In the aspect of algorithm design, an unconstrained minimization model with p (0p1) norm canonical term is proposed by means of FB complementary function. The model can approach the sparse solution well with the decrease of the regular parameters. Then the threshold lower bound for each nonzero component of the local optimal solution is established. The lower bound plays an accurate role in determining the zero component in the numerical calculation. Then it considers how to select the appropriate regular parameters to make the optimal solution reach the desired sparsity. Finally, based on the above theory, A sequential smooth gradient algorithm (SSG) is proposed to solve the LP norm canonical minimization model. Numerical experiments show that the SSG algorithm can effectively solve the LP norm canonical minimization model and obtain the sparse solution of the linear complementarity problem. In order to further improve the efficiency of sparse solution algorithm for linear complementarity problems, we transform complementary constraints into fixed point equations in projection form, and propose a projective constraint minimization model with F 1 norm regular term. Then, the threshold representation theorem of the solution of the subproblem of the regular problem is given, and a shrinkage threshold projection algorithm (STP) is designed. Finally, the algorithm is applied to solve the above l _ 1 regular projection minimization problem, and the convergence of the algorithm is given. Numerical experiments show that the STP algorithm can effectively solve the L _ 1 regular projection minimization model, and can obtain the high quality sparse solution of] LCPs. In order to better approximate the L _ 0 norm of vector, we propose a projective constrained minimization model with L _ 1 / 2 norm canonical term when solving sparse solution of linear complementarity problem. Then a semi-threshold projection algorithm (HTP) is designed and its convergence is established. Finally, numerical experiments show that the HTP algorithm can effectively solve the l / 2 regular projection minimization problem and output the high quality sparse solution of LCPs. For the sparse solution of nonlinear complementarity problem, a projective constrained minimization model with F 1 norm canonical term is proposed, and then the external gradient threshold algorithm (ETA) is designed and the convergence of the algorithm is analyzed. It is proved that any accumulation point of the sequence generated by the ETA algorithm is the solution of the NCP problem. Finally, numerical experiments show that the ETA algorithm can effectively solve the L 1 regular projection minimization model, and can output the high quality sparse solution of the complementary forced nonlinear complementarity problem. Finally, the main contributions of this paper are summarized, and the further possible research directions are prospected.
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：O221

【相似文獻(xiàn)】

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

1 修乃華;韓繼業(yè);;對(duì)稱(chēng)錐互補(bǔ)問(wèn)題[J];數(shù)學(xué)進(jìn)展;2007年01期

2 張利霞;;廣義互補(bǔ)問(wèn)題弱正則性成立的一個(gè)新的充分條件[J];濟(jì)寧學(xué)院學(xué)報(bào);2007年06期

3 徐迎軍;互補(bǔ)問(wèn)題的非負(fù)最優(yōu)化變形[J];菏澤師專(zhuān)學(xué)報(bào);2000年04期

4 殷洪友,徐成賢,張忠秀;F-互補(bǔ)問(wèn)題及其與極小元問(wèn)題的等價(jià)性[J];數(shù)學(xué)學(xué)報(bào);2001年04期

5 張培愛(ài),何素艷,李興斯;互補(bǔ)問(wèn)題的一種光滑迭代算法[J];大連理工大學(xué)學(xué)報(bào);2003年01期

6 唐嘉;馬昌鳳;;求解混合互補(bǔ)問(wèn)題的一步光滑牛頓法[J];桂林電子科技大學(xué)學(xué)報(bào);2006年06期

7 吳業(yè)軍;楊帆;孫福樹(shù);滑偉;;一種互補(bǔ)問(wèn)題解的存在性區(qū)間檢驗(yàn)方法[J];南京工程學(xué)院學(xué)報(bào)(自然科學(xué)版);2006年03期

8 劉常麗;;輔助問(wèn)題方法求解隱互補(bǔ)問(wèn)題[J];泰山醫(yī)學(xué)院學(xué)報(bào);2007年05期

9 張帆;;關(guān)于二階錐互補(bǔ)問(wèn)題解的一些性質(zhì)[J];科技信息;2009年02期

10 何素艷;姜昱汐;李興斯;;基于凝聚函數(shù)的互補(bǔ)問(wèn)題的光滑化算法[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2009年07期

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

1 賴(lài)炎連;張立平;高自友;;效益函數(shù)與變分不等式及半定互補(bǔ)問(wèn)題的算法[A];中國(guó)運(yùn)籌學(xué)會(huì)第六屆學(xué)術(shù)交流會(huì)論文集（上卷）[C];2000年

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

1 胡喜珍;幾類(lèi)互補(bǔ)問(wèn)題算法研究[D];武漢大學(xué);2012年

2 商美娟;互補(bǔ)問(wèn)題的稀疏解[D];北京交通大學(xué);2015年

3 唐嘉;互補(bǔ)問(wèn)題的算法研究[D];西安電子科技大學(xué);2010年

4 劉麗霞;幾類(lèi)對(duì)稱(chēng)錐互補(bǔ)問(wèn)題的算法研究[D];西安電子科技大學(xué);2011年

5 張培愛(ài);互補(bǔ)問(wèn)題的有效算法研究[D];大連理工大學(xué);2002年

6 王勇;兩類(lèi)問(wèn)題的互補(bǔ)求解方法及二階錐互補(bǔ)問(wèn)題解的性質(zhì)[D];天津大學(xué);2012年

7 何素艷;互補(bǔ)問(wèn)題算法研究及其在力學(xué)中的應(yīng)用[D];大連理工大學(xué);2003年

8 朱見(jiàn)廣;互補(bǔ)問(wèn)題與非線性系統(tǒng)的算法研究[D];西安電子科技大學(xué);2011年

9 魯禮勇;互補(bǔ)問(wèn)題重構(gòu)方法的進(jìn)一步研究[D];天津大學(xué);2011年

10 孫秀萍;互補(bǔ)問(wèn)題的非內(nèi)點(diǎn)光滑型算法研究[D];天津大學(xué);2008年

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

1 賈紅;ERM方法求解隨機(jī)線性二階錐互補(bǔ)問(wèn)題[D];大連理工大學(xué);2015年

2 陳源;P-階錐互補(bǔ)問(wèn)題解法和量子化粒子群算法性質(zhì)的研究[D];西安電子科技大學(xué);2014年

3 林釗;求解互補(bǔ)問(wèn)題數(shù)值算法的一些研究[D];福建師范大學(xué);2009年

4 楊少君;一類(lèi)隨機(jī)互補(bǔ)問(wèn)題的算法研究[D];西安電子科技大學(xué);2011年

5 楊曉麗;半定互補(bǔ)問(wèn)題算法的研究[D];西安電子科技大學(xué);2011年

6 吳源;互補(bǔ)問(wèn)題的解法研究[D];西北大學(xué);2001年

7 劉常麗;隱互補(bǔ)問(wèn)題的迭代算法[D];南京航空航天大學(xué);2005年

8 包衛(wèi)軍;一種求解互補(bǔ)問(wèn)題的光滑算法[D];南京航空航天大學(xué);2006年

9 袁泉;隱互補(bǔ)問(wèn)題[D];南京航空航天大學(xué);2002年

10 姜合峰;求解廣義互補(bǔ)問(wèn)題的磨光方法[D];曲阜師范大學(xué);2004年

，

本文編號(hào)：2137902