乘子交替方向法与函数二阶增长条件

发布时间：2018-04-17 02:33

本文选题：乘子交替方向法 + 全局收敛　；参考：《哈尔滨工业大学》2016年博士论文

【摘要】：众所周知,乘子交替方向法(ADMM)的直接推广用于求解多块可分凸优化问题时,不一定具有收敛性。这一事实激励学者们去改进ADMM算法。他们大多采用两种改进方式:第一种方式,在每一次迭代中通过简单的校正ki对直接推广的ADMM算法产生的输出进行校正。另一种方式,通过在直接推广的ADMM算法的每一个子问题中引入一个渐近项对其进行非精确求解。本文结合以上两种方式提出两个有效的求解多块可分凸优化问题的算法。此外,本文利用经典梯度法的思想,设计出一个求解更一般的非凸非光滑复合优化问题的有效算法,并且给出收敛性分析。最后,本文对渐近正则、次可微连续函数的二阶增长条件给出了若干刻画。本文主要内容概括如下:1.本文提出两个求解多块可分凸优化模型的有效方法。这两个方法能够简化子问题的求解,并保证算法的收敛性。由于这两个方法不需要等式约束中的矩阵具有列满秩性质,因此,它的应用范围更广。数值结果表明这两个方法是数值有效的。2.本文证明了在一个弱于强凸性的条件下,直接推广的乘子交替方向法用于求解三块可分凸优化问题具有收敛性。这很好地解释了为什么三块可分凸优化问题的目标函数中没有强凸函数,而乘子交替方向法却有很好的数值表现。3.本文提出了一个求解非凸非光滑复合优化问题的梯度算法。该算法通过引入复合梯度映射,构造出一个辅助问题——其目标函数是两部分的和,第一部分是原目标函数中光滑部分的线性化函数,而第二部分是原目标函数中的非光滑函数,在算法的每次迭代中通过求解这一辅助问题得到算法新的迭代点。该算法具有理论上的收敛性。4.本文证明在一定的条件下,二阶增长条件中非零常数的最紧上界可达,并且建立了渐近正则、次可微连续函数的二阶增长条件与函数次微分的强度量正则性和强度量次正则性之间的等价刻画。
[Abstract]:It is well known that the direct generalization of the multiplier alternating direction method (ADMMM) is not necessarily convergent when it is used to solve multi-block separable convex optimization problems.This fact encourages scholars to improve the ADMM algorithm.Most of them adopt two improved methods: the first way is to correct the output generated by the directly generalized ADMM algorithm through a simple correction Ki in each iteration.In another way, an asymptotic term is introduced into each subproblem of the directly generalized ADMM algorithm to solve the problem inaccurately.In this paper, two effective algorithms for solving multi-block separable convex optimization problems are proposed.In addition, using the idea of classical gradient method, this paper designs an effective algorithm for solving more general nonconvex nonsmooth composite optimization problems, and gives the convergence analysis.Finally, some characterizations of the second order growth conditions for asymptotically regular and subdifferentiable continuous functions are given.The main contents of this paper are summarized as follows: 1: 1.In this paper, two effective methods for solving multi-block separable convex optimization model are presented.These two methods can simplify the solution of the subproblem and ensure the convergence of the algorithm.Because these two methods do not require that the matrices in equality constraints have the property of full column rank, they are more widely used.The numerical results show that the two methods are numerically effective.In this paper, it is proved that under a condition that is weaker than that of strong convexity, the direct extension of the multiplier alternating direction method for solving three block separable convex optimization problems has convergence.This explains why there is no strong convex function in the objective function of the three separable convex optimization problems, but the multiplicator alternating direction method has a good numerical performance.In this paper, a gradient algorithm for nonconvex nonsmooth composite optimization problems is proposed.By introducing compound gradient mapping, the algorithm constructs an auxiliary problem-its objective function is the sum of two parts. The first part is the linearization function of the smooth part of the original objective function.The second part is the non-smooth function in the original objective function. The new iteration point of the algorithm is obtained by solving this auxiliary problem in each iteration of the algorithm.The algorithm has theoretical convergence. 4.In this paper, we prove that under certain conditions, the most compact upper bound of the nonzero constant of the second order growth condition is reachable, and the asymptotic regularity is established.The equivalent characterizations between the second-order growth conditions of subdifferentiable continuous functions and the intensity regularity and intensity subregularity of subdifferential functions.
【学位授予单位】：哈尔滨工业大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O224

【相似文献】