Modified subgradient extragradient algorithms for solving monotone variational inequalities

ABSTRACT

In this paper, we introduce two new algorithms for solving classical variational inequalities problem with Lipschitz continuous and monotone mapping in real Hilbert space. We modify the subgradient extragradient methods with a new step size, the convergence of algorithms are established without the knowledge of the Lipschitz constant of the mapping. Finally, some numerical experiments are presented to show the efficiency and advantage of the proposed algorithms.     

New extragradient method for a class of equilibrium problems in Hilbert spaces

The paper proposes a new extragradient algorithm for solving strongly pseudomonotone equilibrium problems which satisfy a Lipschitz-type condition recently introduced by Mastroeni in auxiliary problem principle. The main novelty of the paper is that the algorithm generates the strongly convergent sequences in Hilbert spaces without the prior knowledge of Lipschitz-type constants and any hybrid method. Several numerical experiments on a test problem are also presented to illustrate the convergence of the algorithm.     

A modified subgradient extragradient method for solving the variational inequality problem

The subgradient extragradient method for solving the variational inequality (VI) problem, which is introduced by Censor et al. (J. Optim. Theory Appl. 148, 318–335, 2011), replaces the second projection onto the feasible set of the VI, in the extragradient method, with a subgradient projection onto some constructible half-space. Since the method has been introduced, many authors proposed extensions and modifications with applications to various problems. In this paper, we introduce a modified subgradient extragradient method by improving the stepsize of its second step. Convergence of the proposed method is proved under standard and mild conditions and primary numerical experiments illustrate the performance and advantage of this new subgradient extragradient variant.     

一种新修正的求解变分不等式的双次梯度外梯度算法

当可行集为一光滑凸函数的下水平集时, 本文提出一种修正的双次梯度外梯度算法(MTSEGA)用于求解Hilbert空间中单调且Lipschitz连续的变分不等式. MTSEGA在每步迭代过程中仅需计算向半空间的两次投影及一次映射的值. 在与已知算法相同的假设条件下, 证明了新算法产生的序列能弱收敛到相关问题的一个解.     

On extragradient-viscosity methods for solving equilibrium and fixed point problems in a Hilbert space

Abstract

In this paper, new numerical algorithms are introduced for finding the solution of a variational inequality problem whose constraint set is the common elements of the set of fixed points of a demicontractive mapping and the set of solutions of an equilibrium problem for a monotone mapping in a real Hilbert space. The strong convergence of the iterates generated by these algorithms is obtained by combining a viscosity approximation method with an extragradient method. First, this is done when the basic iteration comes directly from the extragradient method, under a Lipschitz-type condition on the equilibrium function. Then, it is shown that this rather strong condition can be omitted when an Armijo-backtracking linesearch is incorporated into the extragradient iteration. The particular case of variational inequality problems is also examined.     

Numerical solutions to large-scale differential Lyapunov matrix equations

In this paper, we introduce an extension of multiple set split variational inequality problem (Censor et al. Numer. Algor. 59, 301–323 2012) to multiple set split equilibrium problem (MSSEP) and propose two new parallel extragradient algorithms for solving MSSEP when the equilibrium bifunctions are Lipschitz-type continuous and pseudo-monotone with respect to their solution sets. By using extragradient method combining with cutting techniques, we obtain algorithms for these problems without using any product space. Under certain conditions on parameters, the iteration sequences generated by the proposed algorithms are proved to be weakly and strongly convergent to a solution of MSSEP. An application to multiple set split variational inequality problems and a numerical example and preliminary computational results are also provided.     

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.     

Strong Convergence of the Halpern Subgradient Extragradient Method for Solving Variational Inequalities in Hilbert Spaces

Building upon the subgradient extragradient method proposed by Censor et al., we prove the strong convergence of the iterative sequence generated by a modification of this method by means of the Halpern method. We also consider the problem of finding a common element of the solution set of a variational inequality and the fixed-point set of a quasi-nonexpansive mapping with a demiclosedness property.     

Accelerated hybrid and shrinking projection methods for variational inequality problems

ABSTRACT

In this paper, we introduce several new extragradient-like approximation methods for solving variational inequalities in Hilbert spaces. Our algorithms are based on Tseng's extragradient method, subgradient extragradient method, inertial method, hybrid projection method and shrinking projection method. Strong convergence theorems are established under appropriate conditions. Our results extend and improve some related results in the literature. In addition, the efficiency of our algorithms is shown through numerical examples which are defined by the hybrid projection methods.     

A viscosity of extragradient approximation method for finding equilibrium problems, variational inequalities and fixed point problems for nonexpansive mappings

In this paper, we investigate the problem for finding the set of solutions for equilibrium problems, the set of solutions of the variational inequalities for k-Lipschitz continuous mappings and fixed point problems for nonexpansive mappings in a Hilbert space. We introduce a new viscosity extragradient approximation method which is based on the so-called viscosity approximation method and extragradient method. We show that the sequence converges strongly to a common element of the above three sets under some parameters controlling conditions. Finally, we utilize our results to study some convergence problems for finding the zeros of maximal monotone operators. Our results are generalization and extension of the results of Kumam [P. Kumam, Strong convergence theorems by an extragradient method for solving variational inequalities and equilibrium problems in a Hilbert space, Turk. J. Math. 33 (2009) 85–98], Wangkeeree [R. Wangkeeree, An extragradient approximation method for equilibrium problems and fixed point problems of a countable family of nonexpansive mappings, Fixed Point Theory and Applications, 2008, Article ID 134148, 17 pages, doi:10.1155/2008/134148], Yao et al. [Y. Yao, Y.C. Liou, R. Chen, A general iterative method for an finite family of nonexpansive mappings, Nonlinear Analysis 69 (5–6) (2008) 1644–1654], Qin et al. [X. Qin, M. Shang, Y. Su, A general iterative method for equilibrium problems and fixed point problems in Hilbert spaces, Nonlinear Analysis (69) (2008) 3897–3909], and many others.     

Modified subgradient extragradient algorithms for variational inequality problems and fixed point problems

The subgradient extragradient method can be considered as an improvement of the extragradient method for variational inequality problems for the class of monotone and Lipschitz continuous mappings. In this paper, we propose two new algorithms as combination between the subgradient extragradient method and Mann-like method for finding a common element of the solution set of a variational inequality and the fixed point set of a demicontractive mapping.     

Simultaneous Subgradient Algorithms for the Generalized Split Variational Inclusion Problem in Hilbert Spaces

In this article, we study the generalized split variational inclusion problem. For this purpose, motivated by the projected Landweber algorithm for the split equality problem, we first present a simultaneous subgradient extragradient algorithm and give related convergence theorems for the proposed algorithm. Next, motivated by the alternating CQ-algorithm for the split equality problem, we propose another simultaneous subgradient extragradient algorithm to study the general split variational inclusion problem. As applications, we consider the split equality problem, split feasibility problem, split variational inclusion problem, and variational inclusion problem in Hilbert spaces.     

Strong convergence of the iterative scheme based on the extragradient method for mixed equilibrium problems and fixed point problems of an infinite family of nonexpansive mappings

In this paper, we introduce an iterative scheme based on the extragradient approximation method for finding a common element of the set of common fixed points of a countable family of nonexpansive mappings, the set of solutions of a mixed equilibrium problem, and the set of solutions of the variational inequality problem for a monotone L-Lipschitz continuous mapping in a real Hilbert space. Then, the strong convergence theorem is proved under some parameters controlling conditions. Applications to optimization problems are given. The results obtained in this paper improve and extend the recent ones announced by Wangkeeree [R. Wangkeeree, An extragradient approximation method for equilibrium problems and fixed point problems of a countable family of nonexpansive mappings, Fixed Point Theory and Applications (2008) 17. doi:10.1155/2008/134148. Article ID 134148], Kumam and Katchang [P. Kumam, P. Katchang, A viscosity of extragradient approximation method for finding equilibrium problems, variational inequalities and fixed point problems for nonexpansive mappings, Nonlinear Anal. Hybrid Syst. (2009) doi:10.1016/j.nahs.2009.03.006] and many others.     

Parallel Algorithms for Solving a Class of Variational Inequalities over the Common Fixed Points Set of a Finite Family of Demicontractive Mappings

Abstract

We propose parallel algorithms for solving a class of variational inequalities over the set of common fixed points for a finite family of demicontractive mappings in real Hilbert spaces. Under some suitable conditions, we prove that the sequence generated by the proposed algorithms converges strongly to a solution of the problem. We apply the proposed algorithms to strongly monotone variational inequality problems with pseudomonotone equilibrium constraints by defining a quasi-nonexpansive and demi-closed mapping whose fixed point set coincides with the solution set of the equilibrium problem.     

The Subgradient Extragradient Method for Solving Variational Inequalities in Hilbert Space

We present a subgradient extragradient method for solving variational inequalities in Hilbert space. In addition, we propose a modified version of our algorithm that finds a solution of a variational inequality which is also a fixed point of a given nonexpansive mapping. We establish weak convergence theorems for both algorithms.     

A hybrid extragradient method for general variational inequalities

In this paper, we introduce and study a hybrid extragradient method for finding solutions of a general variational inequality problem with inverse-strongly monotone mapping in a real Hilbert space. An iterative algorithm is proposed by virtue of the hybrid extragradient method. Under two sets of quite mild conditions, we prove the strong convergence of this iterative algorithm to the unique common element of the set of fixed points of a nonexpansive mapping and the set of solutions of the general variational inequality problem, respectively. L. C. Zeng’s research was partially supported by the National Science Foundation of China (10771141), Ph.D. Program Foundation of Ministry of Education of China (20070270004), and Science and Technology Commission of Shanghai Municipality grant (075105118). J. C. Yao’s research was partially supported by a grant from the National Science Council of Taiwan.     

Dual extragradient algorithms extended to equilibrium problems

In this paper we propose two iterative schemes for solving equilibrium problems which are called dual extragradient algorithms. In contrast with the primal extragradient methods in Quoc et al. (Optimization 57(6):749–776, 2008) which require to solve two general strongly convex programs at each iteration, the dual extragradient algorithms proposed in this paper only need to solve, at each iteration, one general strongly convex program, one projection problem and one subgradient calculation. Moreover, we provide the worst case complexity bounds of these algorithms, which have not been done in the primal extragradient methods yet. An application to Nash-Cournot equilibrium models of electricity markets is presented and implemented to examine the performance of the proposed algorithms.     

A splitting algorithm for a class of bilevel equilibrium problems involving nonexpansive mappings

We propose splitting, parallel algorithms for solving strongly equilibrium problems over the intersection of a finite number of closed convex sets given as the fixed-point sets of nonexpansive mappings in real Hilbert spaces. The algorithm is a combination between the gradient method and the Mann-Krasnosel’skii iterative scheme, where the projection can be computed onto each set separately rather than onto their intersection. Strong convergence is proved. Some special cases involving bilevel equilibrium problems with inverse strongly monotone variational inequality, monotone equilibrium constraints and maximal monotone inclusions are discussed. An illustrative example involving a system of integral equations is presented.     

On Finite Convergence of Iterative Methods for Variational Inequalities in Hilbert Spaces

In a Hilbert space, we study the finite termination of iterative methods for solving a monotone variational inequality under a weak sharpness assumption. Most results to date require that the sequence generated by the method converges strongly to a solution. In this paper, we show that the proximal point algorithm for solving the variational inequality terminates at a solution in a finite number of iterations if the solution set is weakly sharp. Consequently, we derive finite convergence results for the gradient projection and extragradient methods. Our results show that the assumption of strong convergence of sequences can be removed in the Hilbert space case.     

Hybrid iterative scheme by a relaxed extragradient method for solutions of equilibrium problems and a general system of variational inequalities with application to optimization

In this paper, we introduce a new iterative process for finding the common element of the set of fixed points of a nonexpansive mapping, the set of solutions of an equilibrium problem and the solutions of the variational inequality problem for two inverse-strongly monotone mappings. We introduce a new viscosity relaxed extragradient approximation method which is based on the so-called relaxed extragradient method and the viscosity approximation method. We show that the sequence converges strongly to a common element of the above three sets under some parametric controlling conditions. Moreover, using the above theorem, we can apply to finding solutions of a general system of variational inequality and a zero of a maximal monotone operator in a real Hilbert space. The results of this paper extended, improved and connected with the results of Ceng et al., [L.-C. Ceng, C.-Y. Wang, J.-C. Yao, Strong convergence theorems by a relaxed extragradient method for a general system of variational inequalities, Math. Meth. Oper. Res. 67 (2008), 375–390], Plubtieng and Punpaeng, [S. Plubtieng, R. Punpaeng, A new iterative method for equilibrium problems and fixed point problems of nonexpansive mappings and monotone mappings, Appl. Math. Comput. 197 (2) (2008) 548–558] Su et al., [Y. Su, et al., An iterative method of solution for equilibrium and optimization problems, Nonlinear Anal. 69 (8) (2008) 2709–2719], Li and Song [Liwei Li, W. Song, A hybrid of the extragradient method and proximal point algorithm for inverse strongly monotone operators and maximal monotone operators in Banach spaces, Nonlinear Anal.: Hybrid Syst. 1 (3) (2007), 398-413] and many others.