【摘要】：互補問題是優(yōu)化領(lǐng)域中的一個經(jīng)典而重要的研究課題.它在工程、經(jīng)濟與交通均衡等領(lǐng)域都有著廣泛的應(yīng)用.而稀疏優(yōu)化是優(yōu)化領(lǐng)域的一個新的研究課題,它的理論、模型和算法正在迅猛發(fā)展.求互補問題的稀疏解,是互補問題和稀疏優(yōu)化兩課題的融合,具有重要的理論和應(yīng)用價值.本文初步探討了互補問題稀疏解的一些理論,例如存在性和唯一性等,并提出了四種有效算法求解互補問題的稀疏解.主要結(jié)果概括如下：針對線性互補問題稀疏解,在理論方面,給出了Z矩陣線性互補問題稀疏解的唯一性.在算法設(shè)計方面,借助FB互補函數(shù),提出了一個帶有p(0p1)范數(shù)正則項的無約束極小化模型.該模型隨著正則參數(shù)的減小能夠很好地逼近稀疏解.隨后建立了局部最優(yōu)解每一非零分量的閾值下界.該下界在數(shù)值計算中,對確定零分量起到了精確的界定作用；接著考慮了如何選取合適的正則參數(shù),使最優(yōu)解達到希望的稀疏度；最后,基于以上理論,提出序列光滑梯度算法(SSG)來求解lp范數(shù)正則極小化模型.數(shù)值實驗表明SSG算法能夠有效地求解lp范數(shù)正則極小化模型并得到線性互補問題的稀疏解.為了進一步提高求解線性互補問題稀疏解算法的效率,我們將互補約束轉(zhuǎn)化為投影形式的不動點方程,由此提出了一個帶有f1范數(shù)正則項的投影約束極小化模型.緊接著給出了正則問題子問題解的閾值表示定理,并由此設(shè)計了一種收縮閾值投影算法(STP).最后,應(yīng)用此算法求解上述l1正則投影極小化問題,并給出了算法的收斂性.數(shù)值實驗表明,STP算法能有效的求解l1正則投影極小化模型,而且能得到]LCPs的高質(zhì)量稀疏解.在求解線性互補問題稀疏解時,為了更好的逼近向量的l0范數(shù),我們提出了一個帶有l(wèi)1/2范數(shù)正則項的投影約束極小化模型,進而設(shè)計了一種半閾值投影算法(HTP),并建立了算法的收斂性.最后數(shù)值試驗說明HTP算法能有效求解l1/2正則投影極小化問題,并且輸出LCPs的高質(zhì)量稀疏解.針對非線性互補問題的稀疏解,首先提出了一種帶有f1范數(shù)正則項的投影約束極小化模型,接著設(shè)計了外梯度閾值算法(ETA)并給出了算法的收斂性分析,證明了ETA算法產(chǎn)生的序列的任一聚點就是NCP問題的解.最后,數(shù)值實驗顯示ETA算法能有效求解l1正則投影極小化模型,并且能輸出余強制非線性互補問題的高質(zhì)量稀疏解.最后總結(jié)了本文的主要貢獻,并對進一步可能的研究方向進行了展望.
[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é)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：O221

【相似文獻】

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

1 修乃華;韓繼業(yè);;對稱錐互補問題[J];數(shù)學(xué)進展;2007年01期

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 劉麗霞;幾類對稱錐互補問題的算法研究[D];西安電子科技大學(xué);2011年

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

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

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

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

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

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

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

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

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

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

4 楊少君;一類隨機互補問題的算法研究[D];西安電子科技大學(xué);2011年

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

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

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

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

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

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

，

本文編號：2137902