鞍点问题和约束优化的几个一阶算法

发布时间：2017-09-06 13:00

  本文关键词：鞍点问题和约束优化的几个一阶算法

  更多相关文章： 凸规划 增广拉格朗日法 交替方向乘子法 临近点算法 L_1-正则化 正交约束

【摘要】：对于两类问题：鞍点问题和约束优化问题,本文提出了几个简单的一阶算法。这两类问题在诸多领域广泛存在,例如图像恢复、高维统计、动力系统、经济、物理等领域。本文提出的所有算法均基于已有的一阶算法,这些一阶算法包括增广拉格朗日法,交替方向乘子法,临近点算法等。在第一章中,我们简单介绍了鞍点问题和约束优化问题已有的相关算法,以及研究这些问题的动机。在第二章中,我们介绍了一些重要的基本概念,例如凸函数、单调算子、投影以及变分不等式,同时也介绍了它们之间的一些相互关系。接下来是本文的主体部分,本文主体部分由两部分构成。第一部分包括第三章和第四章,主要讨论了鞍点问题及其相关算法。对于鞍点问题,原始对偶混合梯度算法是当今流行的一类求解算法,尤其是求解一些基本图像处理模型；然而在现有文献中,该算法仅在一些严格的步长条件下才能证明其收敛性。在第三章,就鞍点问题,我们重新考虑原始对偶混合梯度法的收敛性,并试着更好的理解如何选择步长。具体来说,我们先用一个极端简单的例子来说明当步长固定时,原始对偶混合梯度算法可能不收敛；接下来,我们将证明当鞍点问题中的一个函数是强凸时,固定步长的原始对偶混合梯度法是收敛的；实际上图像处理中的很多鞍点问题都能满足强凸条件。本章还证明了当步长取为常数时,该方法在最坏情况下的收敛速率。如果鞍点问题不满足强凸条件但其中一个问题是线性函数时,我们在第四章中进一步设计了一类基于临近点算法和收缩方法的有效算法。数值试验表明这个新算法对于一些实际问题是有效的。由第五章和第六章构成的第二部分致力于针对结构型约束优化的分解算法。通过拉格朗日乘子理论,虽然许多结构优化问题可以被转化为等价的鞍点问题,但如果机械套用第一部分的算法将忽略目标函数的结构,这可能会导致子问题难以求解,数值效果不好。增广拉格朗日法[7]是一类求解约束优化问题的经典算法。在这一部分,我们考虑如何改进增广拉格朗日算法来求解具有特殊结构的优化问题,并且尝试得到一些理论结果。在第五章,我们考虑三块的线性约束凸优化问题,在比文献[46]条件弱的前提下,我们第一个证明了三块的交替方向乘子法的收敛性。此外,为了加速三块的交替方向乘子法,我们提出了一个放松的交替方向乘子法,该方法需要额外计算最优步长,并且在宽松的条件下证明了它的全局收敛性。在第六章,我们考虑带有正交约束的l1-正则化优化问题。因为该问题目标函数含有非凸非光滑项且约束为正交约束,所以很难求解。基于增广拉格朗日法[2]和交替临近点法[5],我们提出了一类求解带有正交约束的l1-正则化优化问题的算法,并且证明了该方法的子序列收敛性质。
【关键词】：凸规划 增广拉格朗日法 交替方向乘子法 临近点算法 L_1-正则化 正交约束
【学位授予单位】：南京大学
【学位级别】：博士
【学位授予年份】：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
• 攻读博±学位期间完成的学术成果103-105
• Acknowledgements105-106

【参考文献】

中国期刊全文数据库 前1条

1 何炳生;申远;;求解凸规划及鞍点问题定制的PPA算法及其收敛速率[J];中国科学:数学;2012年05期

，

本文编号：803255