Symmetric Alternating Direction Method with Indefinite Proximal Regularization for Linearly Constrained Convex Optimization

The proximal alternating direction method of multipliers is a popular and useful method for linearly constrained, separable convex problems, especially for the linearized case. In the literature, convergence of the proximal alternating direction method has been established under the assumption that the proximal regularization matrix is positive semi-definite. Recently, it was shown that the regularizing proximal term in the proximal alternating direction method of multipliers does not necessarily have to be positive semi-definite, without any additional assumptions. However, it remains unknown as to whether the indefinite setting is valid for the proximal version of the symmetric alternating direction method of multipliers. In this paper, we confirm that the symmetric alternating direction method of multipliers can also be regularized with an indefinite proximal term. We theoretically prove the global convergence of the indefinite method and establish its worst-case convergence rate in an ergodic sense. In addition, the generalized alternating direction method of multipliers proposed by Eckstein and Bertsekas is a special case in our discussion. Finally, we demonstrate the performance improvements achieved when using the indefinite proximal term through experimental results.     

一种求解单调变分不等式的部分并行分裂LQP交替方向法

LQP交替方向法是求解可分离结构型单调变分不等式问题的一种非常有效的方法.它不仅可以充分地利用目标函数的可分结构,将原问题分解为多个更易求解的子问题,还更适合求解大规模问题.对于带有三个可分离算子的单调变分不等式问题,结合增广拉格朗日算法和LQP交替方向法提出了一种部分并行分裂LQP交替方向法,构造了新算法的两个下降方向,结合这两个下降方向得到了一个新的下降方向,沿着这个新的下降方向给出了最优步长.并在较弱的假设条件下,证明了新算法的全局收敛性.     

Local Convergence Properties of Douglas–Rachford and Alternating Direction Method of Multipliers

The Douglas–Rachford and alternating direction method of multipliers are two proximal splitting algorithms designed to minimize the sum of two proper lower semi-continuous convex functions whose proximity operators are easy to compute. The goal of this work is to understand the local linear convergence behaviour of Douglas–Rachford (resp. alternating direction method of multipliers) when the involved functions (resp. their Legendre–Fenchel conjugates) are moreover partly smooth. More precisely, when the two functions (resp. their conjugates) are partly smooth relative to their respective smooth submanifolds, we show that Douglas–Rachford (resp. alternating direction method of multipliers) (i) identifies these manifolds in finite time; (ii) enters a local linear convergence regime. When both functions are locally polyhedral, we show that the optimal convergence radius is given in terms of the cosine of the Friedrichs angle between the tangent spaces of the identified submanifolds. Under polyhedrality of both functions, we also provide conditions sufficient for finite convergence. The obtained results are illustrated by several concrete examples and supported by numerical experiments.     

Multi-block Nonconvex Nonsmooth Proximal ADMM: Convergence and Rates Under Kurdyka–Łojasiewicz Property

Journal of Optimization Theory and Applications - We study the convergence and convergence rates of a multi-block proximal alternating direction method of multipliers (PADMM) for solving linearly...     

Inexact Alternating Direction Methods of Multipliers with Logarithmic–Quadratic Proximal Regularization

In the literature, it was shown recently that the Douglas–Rachford alternating direction method of multipliers can be combined with the logarithmic-quadratic proximal regularization for solving a class of variational inequalities with separable structures. This paper studies the inexact version of this combination, where the resulting subproblems are allowed to be solved approximately subject to different inexactness criteria. We prove the global convergence and establish worst-case convergence rates for the derived inexact algorithms.     

广义交替近似梯度算法的线性收敛分析

针对两个可分凸函数的和在线性约束下的极小化问题,在交替方向法的框架下,提出广义的交替近似梯度算法.在一定的条件下,该算法具有全局及线性收敛性.数值实验表明该算法有好的数值表现.     

修正乘子交替方向法求解三个可分离算子的凸优化

指出直接推广的经典乘子交替方向法对三个算子的问题不能保证收敛的原因, 并且给出将其改造成收敛算法的相应策略. 同时, 在一个统一框架下, 证明了修正的乘子交替方向法的收敛性和遍历意义下具有O(1/t)~收敛速率.     

A Hybrid Approximate Extragradient – Proximal Point Algorithm Using the Enlargement of a Maximal Monotone Operator

We propose a modification of the classical extragradient and proximal point algorithms for finding a zero of a maximal monotone operator in a Hilbert space. At each iteration of the method, an approximate extragradient-type step is performed using information obtained from an approximate solution of a proximal point subproblem. The algorithm is of a hybrid type, as it combines steps of the extragradient and proximal methods. Furthermore, the algorithm uses elements in the enlargement (proposed by Burachik, Iusem and Svaiter) of the operator defining the problem. One of the important features of our approach is that it allows significant relaxation of tolerance requirements imposed on the solution of proximal point subproblems. This yields a more practical proximal-algorithm-based framework. Weak global convergence and local linear rate of convergence are established under suitable assumptions. It is further demonstrated that the modified forward-backward splitting algorithm of Tseng falls within the presented general framework.     

一类自适应广义交替方向乘子法

广义交替方向乘子法是求解凸优化问题的有效算法.当实际问题中子问题难以求解时,可以采用在子问题中添加邻近项的方法处理,邻近矩阵正定时,算法收敛,然而这也会使迭代步长较小.最新研究表明,邻近矩阵可以有一定的不正定性.本文在基于不定邻近项的广义交替方向乘子法框架下,提出一种自适应的广义交替方向乘子法,动态地选择邻近矩阵,增大迭代步长.在一些较弱的假设下,证明了算法的全局收敛性.我们进行一些初等数值实验,验证了算法的有效性.     

Extragradient method for solving quasivariational inequalities

We study methods for solving a class of the quasivariational inequalities in Hilbert space when the changeable set is described by translation of a fixed, closed and convex set. We consider one variant of the gradient-type projection method and an extragradient method. The possibilities of the choice of parameters of the gradient projection method in this case are wider than in the general case of a changeable set. The extragradient method on each iteration makes one trial step along the gradient, and the value of the gradient at the obtained point is used at the first point as the iteration direction. In the paper, we establish sufficient conditions for the convergence of the proposed methods and derive a new estimate of the rates of the convergence. The main result of this paper is contained in the convergence analysis of the extragradient method.     

Application of the alternating direction method of multipliers to separable convex programming problems

This paper presents a decomposition algorithm for solving convex programming problems with separable structure. The algorithm is obtained through application of the alternating direction method of multipliers to the dual of the convex programming problem to be solved. In particular, the algorithm reduces to the ordinary method of multipliers when the problem is regarded as nonseparable. Under the assumption that both primal and dual problems have at least one solution and the solution set of the primal problem is bounded, global convergence of the algorithm is established.     

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 proximal point algorithm revisit on the alternating direction method of multipliers

The alternating direction method of multipliers(ADMM)is a benchmark for solving convex programming problems with separable objective functions and linear constraints.In the literature it has been illustrated as an application of the proximal point algorithm(PPA)to the dual problem of the model under consideration.This paper shows that ADMM can also be regarded as an application of PPA to the primal model with a customized choice of the proximal parameter.This primal illustration of ADMM is thus complemental to its dual illustration in the literature.This PPA revisit on ADMM from the primal perspective also enables us to recover the generalized ADMM proposed by Eckstein and Bertsekas easily.A worst-case O(1/t)convergence rate in ergodic sense is established for a slight extension of Eckstein and Bertsekas’s generalized ADMM.     

Hybrid Methods for Solving Simultaneously an Equilibrium Problem and Countably Many Fixed Point Problems in a Hilbert Space

This paper presents a framework of iterative methods for finding a common solution to an equilibrium problem and a countable number of fixed point problems defined in a Hilbert space. A general strong convergence theorem is established under mild conditions. Two hybrid methods are derived from the proposed framework in coupling the fixed point iterations with the iterations of the proximal point method or the extragradient method, which are well-known methods for solving equilibrium problems. The strategy is to obtain the strong convergence from the weak convergence of the iterates without additional assumptions on the problem data. To achieve this aim, the solution set of the problem is outer approximated by a sequence of polyhedral subsets.     

An alternating direction method of multipliers for elliptic equation constrained optimization problem

We propose an alternating direction method of multipliers (ADMM) for solving the state constrained optimization problems governed by elliptic equations. The unconstrained as well as box-constrained cases of the Dirichlet boundary control, Robin boundary control, and right-hand side control problems are considered here. These continuous optimization problems are transformed into discrete optimization problems by the finite element method discretization, then are solved by ADMM. The ADMM is an efficient first order algorithm with global convergence, which combines the decomposability of dual ascent with the superior convergence properties of the method of multipliers. We shall present exhaustive convergence analysis of ADMM for these different type optimization problems. The numerical experiments are performed to verify the efficiency of the method.     

A HOMOTOPY-BASED ALTERNATING DIRECTION METHOD OF MULTIPLIERS FOR STRUCTURED CONVEX OPTIMIZATION

The alternating direction method of multipliers(ADMM for short) is efficient for linearly constrained convex optimization problem. The practical computational cost of ADMM depends on the sub-problem solvers. The proximal point algorithm is a common sub-problem-solver. However, the proximal parameter is sensitive in the proximal ADMM. In this paper, we propose a homotopy-based proximal linearized ADMM, in which a homotopy method is used to solve the sub-problems at each iteration. Under some suitable conditions, the global convergence and the convergence rate of O(1/k) in the worst case of the proposed method are proven. Some preliminary numerical results indicate the validity of the proposed method.     

Solving policy design problems: Alternating direction method of multipliers-based methods for structured inverse variational inequalities

Inverse variational inequalities have broad applications in various disciplines, and some of them have very appealing structures. There are several algorithms (e.g., proximal point algorithms and projection-type algorithms) for solving the inverse variational inequalities in general settings, while few of them have fully exploited the special structures. In this paper, we consider a class of inverse variational inequalities that has a separable structure and linear constraints, which has its root in spatial economic equilibrium problems. To design an efficient algorithm, we develop an alternating direction method of multipliers (ADMM) based method by utilizing the separable structure. Under some mild assumptions, we prove its global convergence. We propose an improved variant that makes the subproblems much easier and derive the convergence result under the same conditions. Finally, we present the preliminary numerical results to show the capability and efficiency of the proposed methods.     

Convergence study on the proximal alternating direction method with larger step size

Numerical Algorithms - The alternating direction method of multipliers (ADMM) is a popular method for solving separable convex programs with linear constraints, and its proximal version is an...     

A UNIFIED FRAMEWORK FOR SOME INEXACT PROXIMAL POINT ALGORITHMS*

We present a unified framework for the design and convergence analysis of a class of algorithms based on approximate solution of proximal point subproblems. Our development further enhances the constructive approximation approach of the recently proposed hybrid projection–proximal and extragradient–proximal methods. Specifically, we introduce an even more flexible error tolerance criterion, as well as provide a unified view of these two algorithms. Our general method possesses global convergence and local (super)linear rate of convergence under standard assumptions, while using a constructive approximation criterion suitable for a number of specific implementations. For example, we show that close to a regular solution of a monotone system of semismooth equations, two Newton iterations are sufficient to solve the proximal subproblem within the required error tolerance. Such systems of equations arise naturally when reformulating the nonlinear complementarity problem.

     

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.