A Fast Symmetric Alternating Direction Method of Multipliers

In recent years, alternating direction method of multipliers (ADMM) and its variants are popular for the extensive use in image processing and statistical learning. A variant of ADMM: symmetric ADMM, which updates the Lagrange multiplier twice in one iteration, is always faster whenever it converges. In this paper, combined with Nesterov's accelerating strategy, an accelerated symmetric ADMM is proposed. We prove its $\mathcal{O}(\frac{1}{k^2})$ convergence rate under strongly convex condition. For the general situation, an accelerated method with a restart rule is proposed. Some preliminary numerical experiments show the efficiency of our algorithms.     

Stochastic Accelerated Alternating Direction Method of Multipliers with Importance Sampling

In this paper, we incorporate importance sampling strategy into accelerated framework of stochastic alternating direction method of multipliers for solving a class of stochastic composite problems with linear equality constraint. The rates of convergence for primal residual and feasibility violation are established. Moreover, the estimation of variance of stochastic gradient is improved due to the use of important sampling. The proposed algorithm is capable of dealing with the situation, where the feasible set is unbounded. The experimental results indicate the effectiveness of the proposed method.     

A Bregman-style Partially Symmetric Alternating Direction Method of Multipliers for Nonconvex Multi-block Optimization

The alternating direction method of multipliers(ADMM) is one of the most successful and powerful methods for separable minimization optimization. Based on the idea of symmetric ADMM in two-block optimization, we add an updating formula for the Lagrange multiplier without restricting its position for multiblock one. Then, combining with the Bregman distance, in this work, a Bregman-style partially symmetric ADMM is presented for nonconvex multi-block optimization with linear constraints, and the ...     

Nested Alternating Direction Method of Multipliers to Low-Rank and Sparse-Column Matrices Recovery

The task of dividing corrupted-data into their respective subspaces can be well illustrated,both theoretically and numerically,by recovering low-rank and sparse...     

An Alternating Direction Method of Multipliers for MCP-penalized Regression with High-dimensional Data

The minimax concave penalty (MCP) has been demonstrated theoretically and practically to be effective in nonconvex penalization for variable selection and parameter estimation. In this paper, we develop an efficient alternating direction method of multipliers (ADMM) with continuation algorithm for solving the MCP-penalized least squares problem in high dimensions. Under some mild conditions, we study the convergence properties and the Karush–Kuhn–Tucker (KKT) optimality conditions of the proposed method. A high-dimensional BIC is developed to select the optimal tuning parameters. Simulations and a real data example are presented to illustrate the efficiency and accuracy of the proposed method.     

Distributed Solution of Constrained Optimal Control Problems Using the Alternating Direction Method of Multipliers

Many control problems in science and engineering can be formulated as optimal control problems (OCP) such as load changes in process control or point-to-point motion of industrial robots in a time-optimal or energy-optimal way while accounting for physical or security constraints. Hence, an efficient way to handle constrained OCPs is an important topic of research. A promising approach to address this issue is a transformation technique allowing to reformulate an inequality constrained OCP into an equality constrained counterpart. The reformulated OCP reveals to possess a particular structure that is favorable for a decomposition and the application of distributed optimization methods. Motivated by the Augmented Lagrangian approach, the structure of the reformulated OCP can be exploited to derive a decomposition method for splitting up the entire OCP into smaller subproblems. In addition, an algorithm is presented that follows the ideas of the Alternating Direction Method of Multipliers (ADMM) and solves the resulting subproblems in a distributed manner. The approach is applied to a mechatronic example system to demonstrate the performance of the presented method. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

交替方向乘子法求解混合全变差模糊图像复原模型

针对全变差模型在模糊图像复原过程中易产生振铃效应的不足,提出了图像复原的混合全变差模型.混合模型在图像边缘轮廓区域趋向为标准全变差模型,能够有效地保留边缘轮廓信息;而在光滑区域能够逼近为高阶全变差模型,达到抑制振铃效应的目的.实验结果表明,提出的混合全变差模型在复原图像结构信息的同时能够有效地抑制振铃效应的产生,得到的复原图像在客观评价标准和主观视觉效果方面均有所提高.     

Linear Convergence Rates for Variants of the Alternating Direction Method of Multipliers in Smooth Cases

In the present paper, we propose a novel convergence analysis of the alternating direction method of multipliers, based on its equivalence with the overrelaxed primal–dual hybrid gradient algorithm. We consider the smooth case, where the objective function can be decomposed into one differentiable with Lipschitz continuous gradient part and one strongly convex part. Under these hypotheses, a convergence proof with an optimal parameter choice is given for the primal–dual method, which leads to convergence results for the alternating direction method of multipliers. An accelerated variant of the latter, based on a parameter relaxation, is also proposed, which is shown to converge linearly with same asymptotic rate as the primal–dual algorithm.     

求解两块可分离凸极小化问题的惯性交替方向乘子法

The alternating direction method of multipliers(ADMM)is a widely used method for solving many convex minimization models arising in signal and image processing.In this paper,we propose an inertial ADMM for solving a two-block separable convex minimization problem with linear equality constraints.This algorithm is obtained by making use of the inertial Douglas-Rachford splitting algorithm to the corresponding dual of the primal problem.We study the convergence analysis of the proposed algorithm in infinite-dimensional Hilbert spaces.Furthermore,we apply the proposed algorithm on the robust principal component analysis problem and also compare it with other state-of-the-art algorithms.Numerical results demonstrate the advantage of the proposed algorithm.     

广义乘子交替方向法求解线性约束不可分非凸优化问题的收敛性

In this paper, we consider the convergence of the generalized alternating direction method of multipliers(GADMM) for solving linearly constrained nonconvex minimization model whose objective contains coupled functions. Under the assumption that the augmented Lagrangian function satisfies the Kurdyka-Lojasiewicz inequality, we prove that the sequence generated by the GADMM converges to a critical point of the augmented Lagrangian function when the penalty parameter in the augmented Lagrangian function is sufficiently large. Moreover, we also present some sufficient conditions guaranteeing the sublinear and linear rate of convergence of the algorithm.     

A Simplified Form of Block-Iterative Operator Splitting and an Asynchronous Algorithm Resembling the Multi-Block Alternating Direction Method of Multipliers

This paper develops what is essentially a simplified version of the block-iterative operator splitting method already proposed by the author and P. Combettes, but with more general initialization conditions. It then describes one way of implementing this algorithm asynchronously under a computational model inspired by modern high-performance computing environments, which consist of interconnected nodes each having multiple processor cores sharing a common local memory. The asynchronous implementation framework is then applied to derive an asynchronous algorithm which resembles the alternating direction method of multipliers with an arbitrary number of blocks of variables. Unlike earlier proposals for asynchronous variants of the alternating direction method of multipliers, the algorithm relies neither on probabilistic control nor on restrictive assumptions about the problem instance, instead making only standard convex-analytic regularity assumptions. It also allows the proximal parameters to range freely between arbitrary positive bounds, possibly varying with both iterations and subproblems.     

Pointwise and Ergodic Convergence Rates of a Variable Metric Proximal Alternating Direction Method of Multipliers

In this paper, we obtain global pointwise and ergodic convergence rates for a variable metric proximal alternating direction method of multipliers for solving linearly constrained convex optimization problems. We first propose and study nonasymptotic convergence rates of a variable metric hybrid proximal extragradient framework for solving monotone inclusions. Then, the convergence rates for the former method are obtained essentially by showing that it falls within the latter framework. To the best of our knowledge, this is the first time that global pointwise (resp. pointwise and ergodic) convergence rates are obtained for the variable metric proximal alternating direction method of multipliers (resp. variable metric hybrid proximal extragradient framework).     

Linearized Alternating Direction Method of Multipliers for Separable Convex Optimization of Real Functions in Complex Domain

The alternating direction method of multipliers (ADMM) for separable convex optimization of real functions in complex variables has been proposed recently[21]. Furthermore, the convergence and $O(1/K)$ convergence rate of ADMM in complex domain have also been derived[22]. In this paper, a fast linearized ADMM in complex domain has been presented as the subproblems do not have closed solutions. First, some useful results in complex domain are developed by using the Wirtinger Calculus technique. Second, the convergence of the linearized ADMM in complex domain based on the VI is established. Third, an extended model of least absolute shrinkage and selectionator operator (LASSO) is solved by using linearized ADMM in complex domain. Finally, some numerical simulations are provided to show that linearized ADMM in complex domain has the rapid speed.     

A Dynamic Alternating Direction of Multipliers for Nonconvex Minimization with Nonlinear Functional Equality Constraints

Journal of Optimization Theory and Applications - This paper studies the minimization of a broad class of nonsmooth nonconvex objective functions subject to nonlinear functional equality...     

A High Accuracy Alternating Direction Method for the Wave Equation

The alternating direction implicit (ADI) method of Lees forsolving the wave equation in two space dimensions is generalizedand an ADI method of increased accuracy obtained. The new methodis demonstrated by a numerical example. An extension is alsogiven to cover the case of the wave equation in three spacedimensions.     

Comments on a Simplified Form of Block-Iterative Operator Splitting,and an Asynchronous Algorithm Resembling the Multi-block Alternating Direction Method of Multipliers

This note gives an improved version of the proof of Proposition 4.2 in “A Simplified Form of Block-Iterative Operator Splitting, and an Asynchronous Algorithm Resembling the Multi-block Alternating Direction Method of Multipliers,” Journal of Optimization Theory and Applications 173(1): 155–182 (2017).     

A Modified Alternating Direction Method for Variational Inequality Problems

The alternating direction method is an attractive method for solving large-scale variational inequality problems whenever the subproblems can be solved efficiently. However, the subproblems are still variational inequality problems, which are as structurally difficult to solve as the original one. To overcome this disadvantage, in this paper we propose a new alternating direction method for solving a class of nonlinear monotone variational inequality problems. In each iteration the method just makes an orthogonal projection to a simple set and some function evaluations. We report some preliminary computational results to illustrate the efficiency of the method. Accepted 4 May 2001. Online publication 19 October, 2001.     

求解鲁棒主成分分析的新交替下降方向法

鲁棒主成分分析作为统计与数据科学领域的基本工具已被广泛研究,其核心原理是把观测数据分解成低秩部分和稀疏部分.本文基于鲁棒主成分分析的非凸模型,提出了一种新的基于梯度方法和非单调搜索技术的高斯型交替下降方向法.在新算法中,交替更新低秩部分和稀疏部分相关的变量,其中低秩部分的变量是利用一步带有精确步长的梯度下降法进行更新,...