發(fā)布時間：2017-09-06 13:00

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

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

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

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

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

，

本文編號：803255