凸两分块问题邻近乘子交替方向法的O(1/n)收敛率

On the O(1/n) Convergence Rate of Proximal Alternating Directions Method of Multipliers for Convex Two-block Optimization

乘子交替方向法(ADMM)是求解凸两分块问题的一个十分有效的方法.ADMM有效执行的关键是x和y子问题能否快速有效求解.为简化子问题的求解,一个常用的技巧是引入适当的正则项对x与y子问题进行简化.本文考虑当x和y子问题同时正则化时,ADMM的迭代复杂性,分析了算法在遍历意义下具有O(1/n)的收敛率.

Alternating directions method of multipliers （ADMM） is an minimization problems. The key to solving ADMM is how to deal effective method for convex two-block with x-subproblem and y-subproblem efficiently. It＇s a common technique that introducing appropriate regularization for x and y-subproblems, which makes subproblems much easier. In this paper, we focus on the iteration complexity for ADMM, and show the O （1/ n） convergence rate in ergodic sense for ADMM when we apply the regularization technique to both x-subproblem and y-subproblem.