An additional projection step to He and Liao's method for solving variational inequalities

In this paper, we proposed a modified extragradient method for solving variational inequalities. The method can be viewed as an extension of the method proposed by He and Liao [Improvement of some projection methods for monotone variational inequalities, J. Optim. Theory Appl. 112 (2002) 111–128], by performing an additional projection step at each iteration and another optimal step length is employed to reach substantial progress in each iteration. We used a self-adaptive technique to adjust parameter ρ$\rho$ at each iteration. Under certain conditions, the global convergence of the proposed method is proved. Preliminary numerical experiments are included to compare our method with some known methods.     

New Parallel Descent-like Method for Solving a Class of Variational Inequalities

To solve a class of variational inequalities with separable structures, some classical methods such as the augmented Lagrangian method and the alternating direction methods require solving two subvariational inequalities at each iteration. The most recent work (B.S. He in Comput. Optim. Appl. 42(2):195–212, 2009) improved these classical methods by allowing the subvariational inequalities arising at each iteration to be solved in parallel, at the price of executing an additional descent step. This paper aims at developing this strategy further by refining the descent directions in the descent steps, while preserving the practical characteristics suitable for parallel computing. Convergence of the new parallel descent-like method is proved under the same mild assumptions on the problem data.     

Contraction behaviour of iteration–discretization based on gradient type projections

There is a wide range of iterative methods in infinite dimensional spaces to treat variational equations or variational inequalities. As a rule, computational handling of problems in infinite dimensional spaces requires some discretization. Any useful discretization of the original problem leads to families of problems over finite dimensional spaces. Thus, two infinite techniques, namely discretization and iteration are embedded into each other. In the present paper, the behaviour of truncated iterative methods is studied, where at each discretization level only a finite number of steps is performed. In our study no accuracy dependent a posteriori stopping criterion is used. From an algorithmic point of view, the considered methods are of iteration–discretization type. The major aim here is to provide the convergence analysis for the introduced abstract iteration–discretization methods. A special emphasis is given on algorithms for the treatment of variational inequalities with strongly monotone operators over fixed point sets of quasi-nonexpansive mappings.     

Proximal-like contraction methods for monotone variational inequalities in a unified framework?II: general methods and numerical experiments

Approximate proximal point algorithms (abbreviated as APPAs) are classical approaches for convex optimization problems and monotone variational inequalities. In Part I of this paper (He et al. in Proximal-like contraction methods for monotone variational inequalities in a unified framework I: effective quadruplet and primary methods, 2010), we proposed a unified framework consisting of an effective quadruplet and a corresponding accepting rule. Under the framework, various existing APPAs can be grouped in the same class of methods (called primary or elementary methods) which adopt one of the geminate directions in the effective quadruplet and take the unit step size. In this paper, we extend the primary methods by using the same effective quadruplet and the accepting rule. The extended (general) contraction methods need only minor extra even negligible costs in each iteration, whereas having better properties than the primary methods in sense of the distance to the solution set. A set of matrix approximation examples as well as six other groups of numerical experiments are constructed to compare the performance between the primary (elementary) and extended (general) methods. As expected, the numerical results show the efficiency of the extended (general) methods are much better than that of the primary (elementary) ones.     

A COMPARISON OF DIFFERENT CONTRACTION METHODS FOR MONOTONE VARIATIONAL INEQUALITIES

It is interesting to compare the efficiency of two methods when their computational loads in each iteration are equal. In this paper, two classes of contraction methods for monotone variational inequalities are studied in a unified framework. The methods of both classes can be viewed as prediction-correction methods, which generate the same test vector in the prediction step and adopt the same step-size rule in the correction step. The only difference is that they use different search directions. The computational loads of each iteration of the different classes are equal. Our analysis explains theoretically why one class of the contraction methods usually outperforms the other class. It is demonstrated that many known methods belong to these two classes of methods. Finally, the presented numerical results demonstrate the validity of our analysis.     

A modified alternating projection based prediction–correction method for structured variational inequalities

In this paper, we propose a novel alternating projection based prediction–correction method for solving the monotone variational inequalities with separable structures. At each iteration, we adopt the weak requirements for the step sizes to derive the predictors, which affords fewer trial and error steps to accomplish the prediction phase. Moreover, we design a new descent direction for the merit function in correction phase. Under some mild assumptions, we prove the global convergence of the modified method. Some preliminary computational results are reported to demonstrate the promising and attractive performance of the modified method compared to some state-of-the-art prediction–contraction methods.     

关于两个非线性算子的一个分裂方法(英文)

<正>This paper generalizes a class of projection type methods for monotone variational inequalities to general monotone inclusion.It is shown that when the normal cone operator in projection is replaced by any maximal monotone operator,the resulting method inherits all attractive convergence properties of projection type methods,and allows an adjusting step size rule.Weaker convergence assumption entails an extra projection at each iteration.Moreover,this paper also addresses applications of the resulting method to convex programs and monotone variational inequalities.     

An improved Goldstein's type method for a class of variant variational inequalities

This paper aims at presenting an improved Goldstein's type method for a class of variant variational inequalities. In particular, the iterate computed by an existing Goldstein's type method [He, A Goldstein's type projection method for a class of variant variational inequalities J. Comput. Math. 17(4) (1999) 425–434]. is used to construct a descent direction, and thus the new method generates the new iterate by searching the optimal step size along the descent direction. Some restrictions on the involving functions of the existing Goldstein's type methods are relaxed, while the global convergence of the new method is proved without additional assumptions. The computational superiority of the new method is verified by the comparison to some existing methods.     

Generalized iterative process and associated regularization for J-Pseudomonotone mixed variational inequalities

A generalized iterative process for solving mixed variational inequalities with J-Pseudomonotone operators in uniformly smooth Banach spaces is proposed and its weak convergence is established. An application to the stationary filtration problem is given. For such variational inequalities, a generalized iterative regularization method is constructed and its weak convergence under the assumption that the iterative parameter may vary from step to step is analyzed. Our results extend and generalize the corresponding theorems of [A.M. Saddeek, S.A. Ahmed, Convergence analysis of iterative methods for some variational inequalities with J-Pseudomonotone operators in uniformly smooth Banach spaces, Appl. Sci. Comput., accepted for publication, A.M. Saddeek, S.A. Ahmed, On the convergence of some iteration processes for J-Pseudomonotone mixed variational inequalities in uniformly smooth Banach spaces, Math. Comput. Modell., 46(3-4) (2007) 557-572].     

PPA BASED PREDICTION-CORRECTION METHODS FOR MONOTONE VARIATIONAL INEQUALITIES

In this paper we study the proximal point algorithm (PPA) based prediction-correction (PC) methods for monotone variational inequalities. Each iteration of these methods consists of a prediction and a correction. The predictors are produced by inexact PPA steps. The new iterates are then updated by a correction using the PPA formula. We present two profit functions which serve two purposes: First we show that the profit functions are tight lower bounds of the improvements obtained in each iteration. Based on this conclusion we obtain the convergence inexactness restrictions for the prediction step. Second we show that the profit functions are quadratically dependent upon the step lengths, thus the optimal step lengths are obtained in the correction step. In the last part of the paper we compare the strengths of different methods based on their inexactness restrictions.     

THE KACANOV METHOD FOR A NONLINEAR VARIATIONAL INEQUALITY OF THE SECOND KIND ARISING IN ELASTOPLASTICITY

The authors first prove a convergence result on the Ka(?)anov method for solving generalnonlinear variational inequalities of the second kind and then apply the Kacanov method tosolve a nonlinear variational inequality of the second kind arising in elastoplasticity. In additionto the convergence result, an a posteriori error estimate is shown for the Kacanov iterates. Ineach step of the Ka(?)anov iteration, one has a (linear) variational inequality of the secondkind, which can be solved by using a regularization technique. The Ka(?)anov iteration andthe regularization technique together provide approximations which can be readily computednumerically. An a posteriori error estimate is derived for the combined effect of the Ka(?)anoviteration and the regularization.     

Some algorithms for general monotone mixed variational inequalities

We consider some new iterative methods for solving general monotone mixed variational inequalities by using the updating technique of the solution. The convergence analysis of these new methods is considered and the proof of convergence is very simple. These new methods are versatile and are easy to implement. Our results differ from those of He [1,2], Solodov and Tseng [3], and Noor [4–6] for solving the monotone variational inequalities.     

一类单调变分不等式的非精确交替方向法

交替方向法适合于求解大规模问题.该文对于一类变分不等式提出了一种新的交替方向法.在每步迭代计算中,新方法提出了易于计算的子问题,该子问题由强单调的线性变分不等式和良态的非线性方程系统构成.基于子问题的精确求解,该文证明了算法的收敛性.进一步,又提出了一类非精确交替方向法,每步迭代计算只需非精确求解子问题.在一定的非精确条件下,算法的收敛性得以证明.     

一类变分不等式问题的信赖域算法

基于J.M.Peng研究一类变分不等式问题（简记为VIP）时所提出的价值函数，本文提出了求解强单调的VIP的一个新的信赖域算法。和已有的处理VIP的信赖域方法不同的是：它在每步迭代时，不必求解带信赖域界的子问题，仅解一线性方程组而求得试验步。这样，计算的复杂性一般来说可降低。在通常的假设条件下，文中还证明了算法的整体收敛性。最后，在梯度是半光滑和约束是矩形域的假设下，该算法还是超线性收敛的。     

Progressive Regularization of Variational Inequalities and Decomposition Algorithms

For nonsymmetric operators involved in variational inequalities, the strong monotonicity of their possibly multivalued inverse operators (referred to as the Dunn property) appears to be the weakest requirement to ensure convergence of most iterative algorithms of resolution proposed in the literature. This implies the Lipschitz property, and both properties are equivalent for symmetric operators. For Lipschitz operators, the Dunn property is weaker than strong monotonicity, but is stronger than simple monotonicity. Moreover, it is always enforced by the Moreau–Yosida regularization and it is satisfied by the resolvents of monotone operators. Therefore, algorithms should always be applied to this regularized version or they should use resolvents: in a sense, this is what is achieved in proximal and splitting methods among others. However, the operation of regularization itself or the computation of resolvents may be as complex as solving the original variational inequality. In this paper, the concept of progressive regularization is introduced and a convergent algorithm is proposed for solving variational inequalities involving nonsymmetric monotone operators. Essentially, the idea is to use the auxiliary problem principle to perform the regularization operation and, at the same time, to solve the variational inequality in its approximately regularized version; thus, two iteration processes are performed simultaneously, instead of being nested in each other, yielding a global explicit iterative scheme. Parallel and sequential versions of the algorithm are presented. A simple numerical example demonstrates the behavior of these two versions for the case where previously proposed algorithms fail to converge unless regularization or computation of a resolvent is performed at each iteration. Since the auxiliary problem principle is a general framework to obtain decomposition methods, the results presented here extend the class of problems for which decomposition methods can be used.     

A new projection and contraction method for linear variational inequalities

In this paper, we presented a new projection and contraction method for linear variational inequalities, which can be regarded as an extension of He's method. The proposed method includes several new methods as special cases. We used a self-adaptive technique to adjust parameter β at each iteration. This method is simple, the global convergence is proved under the same assumptions as He's method. Some preliminary computational results are given to illustrate the efficiency of the proposed method.     

Modified self-adaptive projection method for solving pseudomonotone variational inequalities

In this paper, a self-adaptive projection method with a new search direction for solving pseudomonotone variational inequality (VI) problems is proposed, which can be viewed as an extension of the methods in [B.S. He, X.M. Yuan, J.Z. Zhang, Comparison of two kinds of prediction-correction methods for monotone variational inequalities, Computational Optimization and Applications 27 (2004) 247-267] and [X.H. Yan, D.R. Han, W.Y. Sun, A self-adaptive projection method with improved step-size for solving variational inequalities, Computers & Mathematics with Applications 55 (2008) 819-832]. The descent property of the new search direction is proved, which is useful to guarantee the convergence. Under the relatively relaxed condition that F is continuous and pseudomonotone, the global convergence of the proposed method is proved. Numerical experiments are provided to illustrate the efficiency of the proposed method.     

A general composite explicit iterative scheme of fixed point solutions of variational inequalities for nonexpansive semigroups

In this paper, we introduce a composite explicit viscosity iteration method of fixed point solutions of variational inequalities for nonexpansive semigroups in Hilbert spaces. We prove strong convergence theorems of the composite iterative schemes which solve some variational inequalities under some appropriate conditions. Our result extends and improves those announced by Li et al [General iterative methods for a one-parameter nonexpansive semigroup in Hilbert spaces, Nonlinear Anal. 70 (2009) 3065–3071], Plubtieng and Punpaeng [S. Plubtieng, R. Punpaeng, Fixed-point solutions of variational inequalities for nonexpansive semigroups in Hilbert spaces, Math. Comput. Modelling 48 (2008) 279–286], Plubtieng and Wangkeeree [S. Plubtieng, R. Wangkeeree, A general viscosity approximation method of fixed point solutions of variational inequalities for nonexpansive semigroups in Hilbert spaces, Bull. Korean Math. Soc. 45 (4) (2008) 717–728] and many others.     

An approximate proximal-extragradient type method for monotone variational inequalities

Proximal point algorithms (PPA) are attractive methods for monotone variational inequalities. The approximate versions of PPA are more applicable in practice. A modified approximate proximal point algorithm (APPA) presented by Solodov and Svaiter [Math. Programming, Ser. B 88 (2000) 371–389] relaxes the inexactness criterion significantly. This paper presents an extended version of Solodov–Svaiter's APPA. Building the direction from current iterate to the new iterate obtained by Solodov–Svaiter's APPA, the proposed method improves the profit at each iteration by choosing the optimal step length along this direction. In addition, the inexactness restriction is relaxed further. Numerical example indicates the improvement of the proposed method.     

A variant of forward-backward splitting method for the sum of two monotone operators with a new search strategy

In this paper, we propose variants of Forward-Backward splitting method for finding a zero of the sum of two operators. A classical modification of Forward-Backward method was proposed by Tseng, which is known to converge when the forward and the backward operators are monotone and with Lipschitz continuity of the forward operator. The conceptual algorithm proposed here improves Tseng’s method in some instances. The first and main part of our approach, contains an explicit Armijo-type search in the spirit of the extragradient-like methods for variational inequalities. During the iteration process, the search performs only one calculation of the forward-backward operator in each tentative of the step. This achieves a considerable computational saving when the forward-backward operator is computationally expensive. The second part of the scheme consists in special projection steps. The convergence analysis of the proposed scheme is given assuming monotonicity on both operators, without Lipschitz continuity assumption on the forward operator.