A partially isochronous splitting algorithm for three-block separable convex minimization problems

作者：He, Hongjin; Hou, Liusheng; Xu, Hong-Kun^*

来源：Advances in Computational Mathematics, 2018, 44(4): 1091-1115.

DOI：10.1007/s10444-017-9574-4

• Partially isochronous splitting algorithm
• Alternating direction method of multipliers
• Separable convex minimization
• Variational inequality
• Convergence rate
• Robust principal component analysis

During the last decade, the state-of-the-art alternating direction method of multipliers (ADMM) has successfully been used to solve many two-block separable convex minimization problems arising from several applied areas such as signal/image processing and statistical and machine learning. It however remains an interesting problem of how to implement ADMM to three-block separable convex minimization problems as required by the situation where many objective functions in the above-mentioned areas are actually more conveniently decomposed to the sum of three convex functions, due also to the observation that the straightforward extension of ADMM from the two-block case to the three-block case is apparently not convergent. In this paper, we shall introduce a new algorithm that is called a partially isochronous splitting algorithm (PISA) in order to implement ADMM for the three-block separable model. The main idea of our algorithm is to incorporate only one proximal term into the last subproblem of the extended ADMM so that the resulting algorithm maximally inherits the promising properties of ADMM. A remarkable superiority over the extended ADMM is that we can simultaneously solve two of the subproblems, thereby taking advantages of the separable structure and parallel architectures. Theoretically, we will establish the global convergence of our algorithm under standard conditions, and also the O(1/t) rate of convergence in both ergodic and nonergodic senses, where t is the iteration counter. The computational competitiveness of our algorithm is shown by numerical experiments on an application to the well-tested robust principal component analysis model.

• 出版日期2018-8
• 单位杭州电子科技大学; 南京晓庄学院