非凸优化问题Douglas-Rachford分裂方法的收敛性分析

发布时间：2018-06-21 14:29

本文选题：乘子交替方向法 + Kurdyka-Lojasiewicz不等式　；参考：《南京师范大学》2017年博士论文

【摘要】：在本文中,我们研究了 Douglas-Rachford算子分裂方法求解非凸优化问题的收敛性分析.论文由四部分构成,结构如下:第一、二章,给出了本文的研究背景及所要用到的一些预备知识.第三章,我们考虑乘子交替方向法求解线性约束非凸优化问题的收敛性分析.本质上,乘子交替方向法可以看作Douglas-Rachford分裂方法应用到两块线性约束可分凸优化问题的对偶问题.对于许多应用问题中的大规模可分优化问题,目标函数为凸函数或是非凸函数,利用经典的乘子交替方向法来求解是非常有效的.虽然对于凸目标函数的情形已经有了非常多的收敛性分析结果,目标函数为非凸的情形仍然是一个公开问题,这方面的研究仍在初期.我们考虑三种问题,即线性约束两块可分非凸优化问题,线性约束多块可分非凸优化问题,具有耦合目标函数的线性约束非凸优化问题.通过假定相应的增广拉格朗日函数满足Kurdyka-Lojasiewicz不等式,当增广拉格朗日函数中的罚参数充分大时,我们证明了用乘子交替方向法求解这些问题产生的迭代序列收敛到增广拉格朗日函数的稳定点.在一些更多的假设下,我们分析了该算法的收敛速率.第四章,我们考虑利用Douglas-Rachford分裂方法求解极小化一个强凸函数与一个弱凸函数和的优化问题的收敛性分析.该模型有非常多的应用,特别是某些稀疏性驱动的问题,可以避免通常用凸的罚项产生的偏差估计.若目标函数中的两个函数都是凸函数,Douglas-Rachford分裂方法的收敛性已经有了非常多地研究.然而当目标函数中含有非凸函数时,包括“强凸+弱凸”的情形,该算法的收敛性研究仍在初期.与现有的文献相比,我们在相对较弱的假设下证明了 Douglas-Rachford分裂方法求解“强凸+弱凸”问题的收敛性.更多地,我们证明了Douglas-Rachford算子的渐近正则速率,并且在度量次正则性假设下,我们证明了该算法的局部线性收敛速率.
[Abstract]:In this paper we study the convergence analysis of the Douglas-Rachford operator splitting method for solving nonconvex optimization problems. The paper is composed of four parts. The structure is as follows: the first and second chapters give the research background and some preparatory knowledge to be used in this paper. In chapter 3, we consider the convergence analysis of the linear constrained nonconvex optimization problem with the multiplicator alternating direction method. In essence, the multiplier alternating direction method can be considered as a dual problem for two linear constrained separable convex optimization problems by using the Douglas Rachford splitting method. For the large scale separable optimization problems in many applications, the objective function is convex function or non-convex function, so it is very effective to solve the problem by using the classical alternating direction method of multipliers. Although there are many convergence analysis results for convex objective functions, the case where the objective functions are non-convex is still an open problem, and the research on this aspect is still in its infancy. We consider three kinds of problems, namely, linear constraint two block separable nonconvex optimization problem, linear constraint multi block separable nonconvex optimization problem, linear constrained nonconvex optimization problem with coupling objective function. By assuming that the corresponding augmented Lagrange function satisfies the Kurdyka-Lojasiewicz inequality, when the penalty parameters in the augmented Lagrangian function are sufficiently large, We prove that the iterative sequence generated by the method of alternating direction of multipliers converges to the stable point of the augmented Lagrange function. Under some more assumptions, we analyze the convergence rate of the algorithm. In chapter 4, we consider the convergence analysis of minimization of a strongly convex function and a weak convex function sum by using the Douglas -Rachford splitting method. This model has a lot of applications, especially for some sparse driving problems, which can avoid the deviation estimation caused by convex penalty term. If both of the objective functions are convex, the convergence of the Douglas Rachford splitting method has been studied. However, when the objective function contains a non-convex function, including the case of "strong convexity and weak convexity", the convergence of the algorithm is still in its infancy. Compared with the existing literatures, we prove the convergence of the Douglas-Rachford splitting method for solving "strong convex and weak convex" problems under relatively weak assumptions. Furthermore, we prove the asymptotic regular rate of the Douglas Rachford operator, and we prove the local linear convergence rate of the algorithm under the assumption of metric subregularity.
【学位授予单位】：南京师范大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：O224

【相似文献】