On the linear convergence of the alternating direction method of multipliers

We analyze the convergence rate of the alternating direction method of multipliers (ADMM) for minimizing the sum of two or more nonsmooth convex separable functions subject to linear constraints. Previous analysis of the ADMM typically assumes that the objective function is the sum of only two convex functions defined on two separable blocks of variables even though the algorithm works well in numerical experiments for three or more blocks. Moreover, there has been no rate of convergence analysis for the ADMM without strong convexity in the objective function. In this paper we establish the global R-linear convergence of the ADMM for minimizing the sum of any number of convex separable functions, assuming that a certain error bound condition holds true and the dual stepsize is sufficiently small. Such an error bound condition is satisfied for example when the feasible set is a compact polyhedron and the objective function consists of a smooth strictly convex function composed with a linear mapping, and a nonsmooth \(\ell _1\) regularizer. This result implies the linear convergence of the ADMM for contemporary applications such as LASSO without assuming strong convexity of the objective function.     

On improving the convergence rates of extrapolated alternating direction implicit schemes

This paper describes how a further improvement on the convergence rates of Extrapolated Alternating Direction Implicit schemes is possible. In the case of the first boundary value problem for Laplace's equation over the unit square an analysis is presented which can be extended to cover more general problems. In addition numerical examples which prove the validity of the analysis are given.     

On the convergence of some alternating series

We establish a necessary and sufficient condition for the convergence of the series $\sum_{n=1}^{\infty} (-1)^{n}|\sin(\pi nx)|n^{-\theta}$ in terms of the rational approximations to x. In particular, it follows from our results that the series $\sum_{n=1}^{\infty} (-1)^{n}|\sin n|/n$ converges.     

On the convergence of alternating minimization methods in variational PGD

The approximation of solutions to partial differential equations by tensorial separated representations is one of the most efficient numerical treatment of high dimensional problems. The key step of such methods is the computation of an optimal low-rank tensor to enrich the obtained iterative tensorial approximation. In variational problems, this step can be carried out by alternating minimization (AM) technics, but the convergence of such methods presents a real challenge. In the present work, the convergence of rank-one AM algorithms for a class of variational linear elliptic equations is studied. More precisely, we show that rank-one AM-sequences are in general bounded in the ambient Hilbert tensor space and are compact if a uniform non-orthogonality condition between iterates and the reaction term is fulfilled. In particular, if a rank-one AM-sequence is weakly convergent then it converges strongly and the common limit is a solution of the rank-one optimization problem.     

On inexact alternating direction implicit iteration for continuous Sylvester equations

In this paper, we study the alternating direction implicit (ADI) iteration for solving the continuous Sylvester equation AX + XB = C , where the coefficient matrices A and B are assumed to be positive semi‐definite matrices (not necessarily Hermitian), and at least one of them to be positive definite. We first analyze the convergence of the ADI iteration for solving such a class of Sylvester equations, then derive an upper bound for the contraction factor of this ADI iteration. To reduce its computational complexity, we further propose an inexact variant of the ADI iteration, which employs some Krylov subspace methods as its inner iteration processes at each step of the outer ADI iteration. The convergence is also analyzed in detail. The numerical experiments are given to illustrate the effectiveness of both ADI and inexact ADI iterations.     

On the rate of convergence of stochastic approximation procedures

The rate of convergence of a linear stochastic approximation procedure inR ^d is studied under fairly general assumptions on the coefficients of the equation.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 8, pp. 997–1002, August, 1994.     

On convergence of adaptive estimation procedures with time delays

Adaptive estimation algorithms with time delays are considered in this work. With probability one (w.p.1) convergence is obtained under correlated signals. The conditions in [l] are much weakened and the result is generalized     

On the rate of convergence of some feasible direction algorithms

This paper is concerned with first-order methods of feasible directions. Pironneau and Polak have recently proved theorems which show that three of these methods have a linear rate of convergence for certain convex problems in which the objective functions have positive definite Hessians near the solutions. In the present note, it is shown that these theorems on rate of convergence can be extended to larger classes of problems. These larger classes are determined in part by certain second-order sufficiency conditions, and they include many nonconvex problems. The arguments used here are based on the finite-dimensional version of Hestenes' indirect sufficiency method.     

On the convergence of von Neumann''s alternating projection algorithm for two sets

We give several unifying results, interpretations, and examples regarding the convergence of the von Neumann alternating projection algorithm for two arbitrary closed convex nonempty subsets of a Hilbert space. Our research is formulated within the framework of Fejér monotonicity, convex and set-valued analysis. We also discuss the case of finitely many sets.     

New convergence results for alternating methods

The alternating methods for solving the large system of linear equations Ax=b are investigated. The convergence and the monotone convergence theories for the alternating method are formulated when the coefficient matrix is an H-matrix or a monotone matrix. Sufficient conditions are established for the induced splitting by the alternating method to be a regular splitting. Furthermore, new comparison theorems which improve previous comparison theorems are proved and several concrete applications are given.     

On the convergence of von Neumann's alternating projection algorithm for two sets

We give several unifying results, interpretations, and examples regarding the convergence of the von Neumann alternating projection algorithm for two arbitrary closed convex nonempty subsets of a Hilbert space. Our research is formulated within the framework of Fejér monotonicity, convex and set-valued analysis. We also discuss the case of finitely many sets.     

Extrapolated alternating direction implicit iterative methods

This paper describes a new generalised (extrapolated) A.D.I. method for the solution of Laplace's equation. This method uses (i) a fixed acceleration parameter and (ii) the set of acceleration parameters of Douglas. The theory is applied to the 2-dimensional case and optimum numerical results are obtained.     

On the rate of convergence of the alternating projection method in finite dimensional spaces

Using the results of Smith, Solmon, and Wagner [K. Smith, D. Solomon, S. Wagner, Practical and mathematical aspects of the problem of reconstructing objects from radiographs, Bull. Amer. Math. Soc. 83 (1977) 1227-1270] and Nelson and Neumann [S. Nelson, M. Neumann, Generalizations of the projection method with application to SOR theory for Hermitian positive semidefinite linear systems, Numer. Math. 51 (1987) 123-141] we derive new estimates for the speed of the alternating projection method and its relaxed version in Rm. These estimates can be computed in at most O(m³) arithmetic operations unlike the estimates in papers mentioned above that require spectral information. The new and old estimates are equivalent in many practical cases. In cases when the new estimates are weaker, the numerical testing indicates that they approximate the original bounds in papers mentioned above quite well.     

On descent alternating direction method with LQP regularization for the structured variational inequalities

Optimization Letters - By reviewing the Logarithmic–quadratic proximal (LQP) method, in this paper we suggest and analyze a new LQP alternating direction scheme for the separable constrained...     

On the convergence of gauss' alternating procedure in the method of the least squares

Sunto Gauss ha proposto un procedimento iterativo per risolvere problemi di minimi quadrati. L'autore dà una dimostrazione rigorosa della convergenza di questo metodo, riducendola a un altro teorema dimostrato nella sua Memoria pubblicata nei Rendiconti di Matematica pura ed applicata, serie V, vol. XIII, 1954, pp. 140–163.

---

---

A Giovanni Sansone per il suo 70° compleanno.

---

This work was performed on a National Bureau of Standards contract with The American University, Washington, D. C.     

Parallel alternating direction multiplier decomposition of convex programs

This paper describes two specializations of the alternating direction method of multipliers: the alternating step method and the epigraphic projection method. The alternating step method applies to monotropic programs, while the epigraphic method applies to general block-separable convex programs, including monotropic programs as a special case. The epigraphic method resembles an earlier parallel method due to Spingarn, but solves a larger number of simpler subproblems at each iteration. This paper gives convergence results for both the alternating step and epigraphic methods, and compares their performance on random dense separable quadratic programs.Some of the research described here was performed at the Massachusetts Institute of Technology and was supported by the Army Research Office under Grant DAAL03-86-K-0171 and the National Science Foundation under Grant ECS-85-19058. This portion of the work was supervised by Dimitri P. Bertsekas, for whose support the author is grateful.