Tight global linear convergence rate bounds for Douglas–Rachford splitting

Recently, several authors have shown local and global convergence rate results for Douglas–Rachford splitting under strong monotonicity, Lipschitz continuity, and cocoercivity assumptions. Most of these focus on the convex optimization setting. In the more general monotone inclusion setting, Lions and Mercier showed a linear convergence rate bound under the assumption that one of the two operators is strongly monotone and Lipschitz continuous. We show that this bound is not tight, meaning that no problem from the considered class converges exactly with that rate. In this paper, we present tight global linear convergence rate bounds for that class of problems. We also provide tight linear convergence rate bounds under the assumptions that one of the operators is strongly monotone and cocoercive, and that one of the operators is strongly monotone and the other is cocoercive. All our linear convergence results are obtained by proving the stronger property that the Douglas–Rachford operator is contractive.     

A contraction proximal point algorithm with two monotone operators

It is a known fact that the method of alternating projections introduced long ago by von Neumann fails to converge strongly for two arbitrary nonempty, closed and convex subsets of a real Hilbert space. In this paper, a new iterative process for finding common zeros of two maximal monotone operators is introduced and strong convergence results associated with it are proved. If the two operators are subdifferentials of indicator functions, this new algorithm coincides with the old method of alternating projections. Several other important algorithms, such as the contraction proximal point algorithm, occur as special cases of our algorithm. Hence our main results generalize and unify many results that occur in the literature.     

Banach空间中含$(H,\eta)$单调算子变分包含组解的迭代法

In this paper, we introduce and study a new system of variational inclusions involving （H, η）-monotone operators in Banach space. Using the resolveut operator associated with （H, η）- monotone operators, we prove the existence and uniqueness of solutions for this new system of variational inclusions. We also construct a new algorithm for approximating the solution of this system and discuss the convergence of the iterative sequence generated by the algorithm.     

Strong convergence studied by a hybrid type method for monotone operators in a Banach space

In this paper, we study a strong convergence for monotone operators. We first introduce the hybrid type algorithm for monotone operators. Next, we obtain a strong convergence theorem (Theorem 3.3) for finding a zero point of an inverse-strongly monotone operator in a Banach space. Finally, we apply our convergence theorem to the problem of finding a minimizer of a convex function.     

Convergence analysis of a new algorithm for strongly pseudomontone equilibrium problems

The paper introduces and analyzes the convergence of a new iterative algorithm for approximating solutions of equilibrium problems involving strongly pseudomonotone and Lipschitz-type bifunctions in Hilbert spaces. The algorithm uses a stepsize sequence which is non-increasing, diminishing, and non-summable. This leads to the main advantage of the algorithm, namely that the construction of solution approximations and the proof of its convergence are done without the prior knowledge of the modulus of strong pseudomonotonicity and Lipschitz-type constants of bifunctions. The strongly convergent theorem is established under suitable assumptions. The paper also discusses the assumptions used in the formulation of the convergent theorem. Several numerical results are reported to illustrate the behavior of the algorithm with different sequences of stepsizes and also to compare it with others.     

A proximal point method for the sum of maximal monotone operators

In this paper, we concentrate on the maximal inclusion problem of locating the zeros of the sum of maximal monotone operators in the framework of proximal point method. Such problems arise widely in several applied mathematical fields such as signal and image processing. We define two new maximal monotone operators and characterize the solutions of the considered problem via the zeros of the new operators. The maximal monotonicity and resolvent of both of the defined operators are proved and calculated, respectively. The traditional proximal point algorithm can be therefore applied to the considered maximal inclusion problem, and the convergence is ensured. Furthermore, by exploring the relationship between the proposed method and the generalized forward‐backward splitting algorithm, we point out that this algorithm is essentially the proximal point algorithm when the operator corresponding to the forward step is the zero operator. Copyright © 2013 John Wiley & Sons, Ltd.     

A general algorithm for multiple-sets split feasibility problem involving resolvents and Bregman mappings

In this paper, by using Bregman distance, we introduce a new iterative process involving products of resolvents of maximal monotone operators for approximating a common element of the set of common fixed points of a finite family of multi-valued Bregman relatively nonexpansive mappings and the solution set of the multiple-sets split feasibility problem and common zeros of maximal monotone operators. We derive a strong convergence theorem of the proposed iterative algorithm under appropriate situations. Finally, we mention several corollaries and two applications of our algorithm.     

New iterative schemes for strongly relatively nonexpansive mappings and maximal monotone operators

In this paper, some new iterative schemes for approximating the common element of the set of fixed points of strongly relatively nonexpansive mappings and the set of zero points of maximal monotone operators in a real uniformly smooth and uniformly convex Banach space are proposed. Some weak convergence theorems are obtained, which extend and complement some previous work.     

Strong convergence of the forward–backward splitting method with multiple parameters in Hilbert spaces

Many problems arising from machine learning, signal & image recovery, and compressed sensing can be casted into a monotone inclusion problem for finding a zero of the sum of two monotone operators. The forward–backward splitting algorithm is one of the most powerful and successful methods for solving such a problem. However, this algorithm has only weak convergence in the infinite dimensional settings. In this paper, we propose a new modification of the FBA so that it possesses a norm convergent property. Moreover, we establish two strong convergence theorems of the proposed algorithms under more general conditions.     

Forcing strong convergence of proximal point iterations in a Hilbert space

This paper concerns with convergence properties of the classical proximal point algorithm for finding zeroes of maximal monotone operators in an infinite-dimensional Hilbert space. It is well known that the proximal point algorithm converges weakly to a solution under very mild assumptions. However, it was shown by Güler [11] that the iterates may fail to converge strongly in the infinite-dimensional case. We propose a new proximal-type algorithm which does converge strongly, provided the problem has a solution. Moreover, our algorithm solves proximal point subproblems inexactly, with a constructive stopping criterion introduced in [31]. Strong convergence is forced by combining proximal point iterations with simple projection steps onto intersection of two halfspaces containing the solution set. Additional cost of this extra projection step is essentially negligible since it amounts, at most, to solving a linear system of two equations in two unknowns. Received January 6, 1998 / Revised version received August 9, 1999?Published online November 30, 1999     

Hilbert空间上新的变分不等式问题和不动点问题的粘性迭代算法

本文在Hilbert空间上引入了一个新的粘性迭代算法,找到了关于两个逆强单调算子的变分不等式问题的解集与非扩张映射的不动点集的公共元.通过修改的超梯度算法,得到了强收敛定理,也给出了一个数值例子.所得结果改进了许多最新结果.     

A stochastic inertial forward–backward splitting algorithm for multivariate monotone inclusions

We propose an inertial forward–backward splitting algorithm to compute a zero of a sum of two monotone operators allowing for stochastic errors in the computation of the operators. More precisely, we establish almost sure convergence in real Hilbert spaces of the sequence of iterates to an optimal solution. Then, based on this analysis, we introduce two new classes of stochastic inertial primal–dual splitting methods for solving structured systems of composite monotone inclusions and prove their convergence. Our results extend to the stochastic and inertial setting various types of structured monotone inclusion problems and corresponding algorithmic solutions. Application to minimization problems is discussed.     

Lagrangian Penalization Scheme with Parallel Forward–Backward Splitting

We propose a new iterative algorithm for the numerical approximation of the solutions to convex optimization problems and constrained variational inequalities, especially when the functions and operators involved have a separable structure on a product space, and exhibit some dissymmetry in terms of their component-wise regularity. Our method combines Lagrangian techniques and a penalization scheme with bounded parameters, with parallel forward–backward iterations. Conveniently combined, these techniques allow us to take advantage of the particular structure of the problem. We prove the weak convergence of the sequence generated by this scheme, along with worst-case convergence rates in the convex optimization setting, and for the strongly non-degenerate monotone operator case. Implementation issues related to the penalization of the constraint set are discussed, as well as applications in image recovery and non-Newtonian fluids modeling. A numerical illustration is also given, in order to prove the performance of the algorithm.     

A PENALTY TECHNIQUE FOR NONLINEAR COMPLEMENTARITY PROBLEMS

1.IntroductionConsiderthefollowingnonlinearcomplementarityproblemsNCP(F)offindinganxER",suchthatwhereFisamappingfromR"intoitself.ItisanimportantformofthefollowingvariationalinequalityVI(F,X)offindinganxEX,suchthatwhereXCReisaclosedconvexset.WhenX=R7,(1.1)…     

Duality methods with an automatic choice of parameters Application to shallow water equations in conservative form

Summary.   In [3] a duality numerical algorithm for solving variational inequalities based on certain properties of the Yosida approximation of maximal monotone operators has been introduced. The performance of this algorithm strongly depends on the choice of two constant parameters. In this paper, we consider a new class of algorithms where these constant parameters are replaced by functions. We show that convergence properties are preserved and look for optimal values of these two functions. In general these optimal values cannot be computed, as they depend on the exact solution. Therefore, we propose some strategies in order to approximate them. The resulting algorithms are applied to three variational inequalities in order to compare their performance with that of the original algorithm. Received July 20, 1998 / Revised version received November 26, 1999 / Published online February 5, 2001     

A new inertial-type hybrid projection-proximal algorithm for monotone inclusions

This paper investigates an enhanced proximal algorithm with interesting practical features and convergence properties for solving non-smooth convex minimization problems, or approximating zeroes of maximal monotone operators, in Hilbert spaces. The considered algorithm involves a recent inertial-type extrapolation technique, the use of enlargement of operators and also a recently proposed hybrid strategy, which combines inexact computation of the proximal iteration with a projection. Compared to other existing related methods, the resulting algorithm inherits the good convergence properties of the inertial-type extrapolation and the relaxed projection strategy. It also inherits the relative error tolerance of the hybrid proximal-projection method. As a special result, an update of inexact Newton-proximal method is derived and global convergence results are established.     

General Strongly Nonlinear Quasivariational Inequalities with Relaxed Lipschitz and Relaxed Monotone Mappings

In this paper, we introduce and study a new class of general strongly nonlinear quasivariational inequalities and construct a general iterative algorithm by using the projection method. We establish the existence of a unique solution for general strongly nonlinear quasivariational inequalities involving relaxed Lipschitz, relaxed monotone, and strongly monotone mappings; we obtain the convergence and stability of the iterative sequences generated by the algorithm. Our results extend, improve, and unify many known results due to Bose, Noor, Siddiqi-Ansari, Verma, Yao, Zeng, and others.     

Modified parallel projection methods for the multivalued lexicographic variational inequalities using proximal operator in Hilbert spaces

In this paper, building upon projection methods and parallel splitting-up techniques with using proximal operators, we propose new algorithms for solving the multivalued lexicographic variational inequalities in a real Hilbert space. First, the strong convergence theorem is shown with Lipschitz continuity of the cost mapping, but it must satisfy a strongly monotone condition. Second, the convergent results are also established to the multivalued lexicographic variational inequalities involving a finite system of demicontractive mappings under mild assumptions imposed on parameters. Finally, some numerical examples are developed to illustrate the behavior of our algorithms with respect to existing algorithms.     

Iterative methods for solving monotone equilibrium problems via dual gap functions

This paper proposes an iterative method for solving strongly monotone equilibrium problems by using gap functions combined with double projection-type mappings. Global convergence of the proposed algorithm is proved and its complexity is estimated. This algorithm is then coupled with the proximal point method to generate a new algorithm for solving monotone equilibrium problems. A class of linear equilibrium problems is investigated and numerical examples are implemented to verify our algorithms.     

Modified hybrid projection methods for finding common solutions to variational inequality problems

In this paper we propose several modified hybrid projection methods for solving common solutions to variational inequality problems involving monotone and Lipschitz continuous operators. Based on differently constructed half-spaces, the proposed methods reduce the number of projections onto feasible sets as well as the number of values of operators needed to be computed. Strong convergence theorems are established under standard assumptions imposed on the operators. An extension of the proposed algorithm to a system of generalized equilibrium problems is considered and numerical experiments are also presented.