本文關(guān)鍵詞：鞍點(diǎn)問(wèn)題和約束優(yōu)化的幾個(gè)一階算法

  更多相關(guān)文章： 凸規(guī)劃 增廣拉格朗日法 交替方向乘子法 臨近點(diǎn)算法 L_1-正則化 正交約束

【摘要】：對(duì)于兩類問(wèn)題：鞍點(diǎn)問(wèn)題和約束優(yōu)化問(wèn)題,本文提出了幾個(gè)簡(jiǎn)單的一階算法。這兩類問(wèn)題在諸多領(lǐng)域廣泛存在,例如圖像恢復(fù)、高維統(tǒng)計(jì)、動(dòng)力系統(tǒng)、經(jīng)濟(jì)、物理等領(lǐng)域。本文提出的所有算法均基于已有的一階算法,這些一階算法包括增廣拉格朗日法,交替方向乘子法,臨近點(diǎn)算法等。在第一章中,我們簡(jiǎn)單介紹了鞍點(diǎn)問(wèn)題和約束優(yōu)化問(wèn)題已有的相關(guān)算法,以及研究這些問(wèn)題的動(dòng)機(jī)。在第二章中,我們介紹了一些重要的基本概念,例如凸函數(shù)、單調(diào)算子、投影以及變分不等式,同時(shí)也介紹了它們之間的一些相互關(guān)系。接下來(lái)是本文的主體部分,本文主體部分由兩部分構(gòu)成。第一部分包括第三章和第四章,主要討論了鞍點(diǎn)問(wèn)題及其相關(guān)算法。對(duì)于鞍點(diǎn)問(wèn)題,原始對(duì)偶混合梯度算法是當(dāng)今流行的一類求解算法,尤其是求解一些基本圖像處理模型；然而在現(xiàn)有文獻(xiàn)中,該算法僅在一些嚴(yán)格的步長(zhǎng)條件下才能證明其收斂性。在第三章,就鞍點(diǎn)問(wèn)題,我們重新考慮原始對(duì)偶混合梯度法的收斂性,并試著更好的理解如何選擇步長(zhǎng)。具體來(lái)說(shuō),我們先用一個(gè)極端簡(jiǎn)單的例子來(lái)說(shuō)明當(dāng)步長(zhǎng)固定時(shí),原始對(duì)偶混合梯度算法可能不收斂；接下來(lái),我們將證明當(dāng)鞍點(diǎn)問(wèn)題中的一個(gè)函數(shù)是強(qiáng)凸時(shí),固定步長(zhǎng)的原始對(duì)偶混合梯度法是收斂的；實(shí)際上圖像處理中的很多鞍點(diǎn)問(wèn)題都能滿足強(qiáng)凸條件。本章還證明了當(dāng)步長(zhǎng)取為常數(shù)時(shí),該方法在最壞情況下的收斂速率。如果鞍點(diǎn)問(wèn)題不滿足強(qiáng)凸條件但其中一個(gè)問(wèn)題是線性函數(shù)時(shí),我們?cè)诘谒恼轮羞M(jìn)一步設(shè)計(jì)了一類基于臨近點(diǎn)算法和收縮方法的有效算法。數(shù)值試驗(yàn)表明這個(gè)新算法對(duì)于一些實(shí)際問(wèn)題是有效的。由第五章和第六章構(gòu)成的第二部分致力于針對(duì)結(jié)構(gòu)型約束優(yōu)化的分解算法。通過(guò)拉格朗日乘子理論,雖然許多結(jié)構(gòu)優(yōu)化問(wèn)題可以被轉(zhuǎn)化為等價(jià)的鞍點(diǎn)問(wèn)題,但如果機(jī)械套用第一部分的算法將忽略目標(biāo)函數(shù)的結(jié)構(gòu),這可能會(huì)導(dǎo)致子問(wèn)題難以求解,數(shù)值效果不好。增廣拉格朗日法[7]是一類求解約束優(yōu)化問(wèn)題的經(jīng)典算法。在這一部分,我們考慮如何改進(jìn)增廣拉格朗日算法來(lái)求解具有特殊結(jié)構(gòu)的優(yōu)化問(wèn)題,并且嘗試得到一些理論結(jié)果。在第五章,我們考慮三塊的線性約束凸優(yōu)化問(wèn)題,在比文獻(xiàn)[46]條件弱的前提下,我們第一個(gè)證明了三塊的交替方向乘子法的收斂性。此外,為了加速三塊的交替方向乘子法,我們提出了一個(gè)放松的交替方向乘子法,該方法需要額外計(jì)算最優(yōu)步長(zhǎng),并且在寬松的條件下證明了它的全局收斂性。在第六章,我們考慮帶有正交約束的l1-正則化優(yōu)化問(wèn)題。因?yàn)樵搯?wèn)題目標(biāo)函數(shù)含有非凸非光滑項(xiàng)且約束為正交約束,所以很難求解。基于增廣拉格朗日法[2]和交替臨近點(diǎn)法[5],我們提出了一類求解帶有正交約束的l1-正則化優(yōu)化問(wèn)題的算法,并且證明了該方法的子序列收斂性質(zhì)。
【關(guān)鍵詞】：凸規(guī)劃 增廣拉格朗日法 交替方向乘子法 臨近點(diǎn)算法 L_1-正則化 正交約束
【學(xué)位授予單位】：南京大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：O241.6
【目錄】：

• 中文摘要4-6
• abstract6-11
• Chapter 1 Introduction11-21
• 1.1 Motivation and related approaches11-17
• 1.2 Contributions of the thesis17-18
• 1.3 Organization of the thesis18
• 1.4 Notations18-21
• Chapter 2 Preliminaries21-27
• 2.1 Convex functions and monotone operators21-22
• 2.2 Projection and variational inequality22-25
• 2.3 Some source problems of Ⅵ25-27
• 2.3.1 Convex programming25
• 2.3.2 Structured constrained convex optimization25-26
• 2.3.3 Saddle point problems26-27
• Chapter 3 Primal-Dual Hybrid Gradient Algorithm27-41
• 3.1 Introduction27
• 3.2 Preliminaries27-28
• 3.3 The divergence of PDHG-An illustrative example28-31
• 3.4 The convergence of PDHG31-39
• 3.4.1 Additional assumptions for(3.1)31-33
• 3.4.2 The contraction property33-37
• 3.4.3 Convergence37
• 3.4.4 Convergence rate37-39
• 3.5 Conclusions39-41
• Chapter 4 PPA Based Contraction Methods41-59
• 4.1 Introduction41-42
• 4.2 Preliminaries of PPA and the motivation42-44
• 4.3 Predictor via PPA44-46
• 4.4 PPA based contraction method46-51
• 4.5 Convergence rate in an ergodic sense51-55
• 4.6 Numerical results55-59
• 4.6.1 The special example(3.6)55-56
• 4.6.2 Nearest correlation matrix problem56-57
• 4.6.3 Matrix completion problem57-59
• Chapter 5 ADMM with Three Blocks for Linearly Constrained Convex Pro-gramming Problem59-69
• 5.1 Introduction59-60
• 5.2 Preliminaries60-61
• 5.3 The ADMM with 3 block61-66
• 5.4 Relaxed ADMM with 3 Blocks66-68
• 5.5 Conclusions remarks68-69
• Chapter 6 l_1-Regularized Optimization Problems with Orthogonality Con-straints69-95
• 6.1 Introduction69-72
• 6.1.1 Notations and preliminaries on non-smooth analysis70-72
• 6.2 PAMAL method72-80
• 6.2.1 Algorithm for Step 1 of Algorithm 175-76
• 6.2.2 Well-definedness of Step 1 in the PAMAL method76-80
• 6.3 Convergence analysis80-87
• 6.3.1 Linear Independence and KKT first-order necessary conditions82-84
• 6.3.2 Limit points are also KKT points84-86
• 6.3.3 Existence of Limit points86-87
• 6.4 The compressed modes for variational problems in physics87-93
• 6.4.1 Background on compressed modes87-89
• 6.4.2 Existing methods for compressed modes89-90
• 6.4.3 Computations of CMs via the PAMAL method90-93
• 6.5 Conclusion93-95
• Bibliography95-103
• 攻讀博±學(xué)位期間完成的學(xué)術(shù)成果103-105
• Acknowledgements105-106

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前1條

1 何炳生;申遠(yuǎn);;求解凸規(guī)劃及鞍點(diǎn)問(wèn)題定制的PPA算法及其收斂速率[J];中國(guó)科學(xué):數(shù)學(xué);2012年05期

，

本文編號(hào)：803255