A modified inexact operator splitting method for monotone variational inequalities

The Douglas–Peaceman–Rachford–Varga operator splitting methods (DPRV methods) are attractive methods for monotone variational inequalities. He et al. [Numer. Math. 94, 715–737 (2003)] proposed an inexact self-adaptive operator splitting method based on DPRV. This paper relaxes the inexactness restriction further. And numerical experiments indicate the improvement of this relaxation.      

Self-adaptive operator splitting methods for monotone variational inequalities

Summary. Solving a variational inequality problem VI(Ω,F) is equivalent to finding a solution of a system of nonsmooth equations (a hard problem). The Peaceman-Rachford and /or Douglas-Rachford operator splitting methods are advantageous when they are applied to solve variational inequality problems, because they solve the original problem via solving a series of systems of nonlinear smooth equations (a series of easy problems). Although the solution of VI(Ω,F) is invariant under multiplying F by some positive scalar β, yet the numerical experiment has shown that the number of iterations depends significantly on the positive parameter β which is a constant in the original operator splitting methods. In general, it is difficult to choose a proper parameter β for individual problems. In this paper, we present a modified operator splitting method which adjusts the scalar parameter automatically per iteration based on the message of the iterates. Exact and inexact forms of the modified method with self-adaptive variable parameter are suggested and proved to be convergent under mild assumptions. Finally, preliminary numerical tests show that the self-adaptive adjustment rule is proper and necessary in practice.     

An operator splitting method for variational inequalities with partially unknown mappings

In this paper, we propose a new operator splitting method for solving a class of variational inequality problems in which part of the underlying mappings are unknown. This class of problems arises frequently from engineering, economics and transportation equilibrium problems. At each iteration, by using the information observed from the system, the method solves a system of nonlinear equations, which is well-defined. Under mild assumptions, the global convergence of the method is proved, and its efficiency is demonstrated with numerical examples. The research of D. Han is supported by NSFC grant 10501024 and NSF of Jiangsu Province at Grant No. BK2006214.     

An inexact parallel splitting augmented Lagrangian method for monotone variational inequalities with separable structures

Splitting methods have been extensively studied in the context of convex programming and variational inequalities with separable structures. Recently, a parallel splitting method based on the augmented Lagrangian method (abbreviated as PSALM) was proposed in He (Comput. Optim. Appl. 42:195?C212, 2009) for solving variational inequalities with separable structures. In this paper, we propose the inexact version of the PSALM approach, which solves the resulting subproblems of PSALM approximately by an inexact proximal point method. For the inexact PSALM, the resulting proximal subproblems have closed-form solutions when the proximal parameters and inexact terms are chosen appropriately. We show the efficiency of the inexact PSALM numerically by some preliminary numerical experiments.     

An extraresolvent method for monotone mixed variational inequalities

In this paper, we suggest and analyze a new iterative method for solving monotone mixed variational inequations using the resolvent operator technique. This new method can be viewed as an extension of the extragradient methods for solving the monotone variational inequalities.     

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.     

An LQP-based descent method for structured monotone variational inequalities

This paper proposes a descent method to solve a class of structured monotone variational inequalities. The descent directions are constructed from the iterates generated by a prediction-correction method [B.S. He, Y. Xu, X.M. Yuan, A logarithmic-quadratic proximal prediction-correction method for structured monotone variational inequalities, Comput. Optim. Appl. 35 (2006) 19-46], which is based on the logarithmic-quadratic proximal method. In addition, the optimal step-sizes along these descent directions are identified to accelerate the convergence of the new method. Finally, some numerical results for solving traffic equilibrium problems are reported.     

An APPA-based descent method with optimal step-sizes for monotone variational inequalities

To solve monotone variational inequalities, some existing APPA-based descent methods utilize the iterates generated by the well-known approximate proximal point algorithms (APPA) to construct descent directions. This paper aims at improving these APPA-based descent methods by incorporating optimal step-sizes in both the extra-gradient steps and the descent steps. Global convergence is proved under mild assumptions. The superiority to existing methods is verified both theoretically and computationally.     

有界约束单调变分不等式的内点连续算法

讨论变分不等式问题VIP(X，F)，其中F是单调函数，约束集X为有界区域．利用摄动技术和一类光滑互补函数将问题等价转化为序列合两个参数的非线性方程组，然后据此建立VIP(X，F)的一个内点连续算法．分析和论证了方程组解的存在性和惟一性等重要性质，证明了算法很好的整体收敛性，最后对算法进行了初步的数值试验。     

A new inexact alternating directions method for monotone variational inequalities

The alternating directions method (ADM) is an effective method for solving a class of variational inequalities (VI) when the proximal and penalty parameters in sub-VI problems are properly selected. In this paper, we propose a new ADM method which needs to solve two strongly monotone sub-VI problems in each iteration approximately and allows the parameters to vary from iteration to iteration. The convergence of the proposed ADM method is proved under quite mild assumptions and flexible parameter conditions. Received: January 4, 2000 / Accepted: October 2001?Published online February 14, 2002     

Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities

The typical structured variational inequalities can be interpreted as a system of equilibrium problems with a leader and two cooperative followers. Assume that, based on the instruction given by the leader, each follower can solve the individual equilibrium sub-problems in his own way. The responsibility of the leader is to give a more reasonable instruction for the next iteration loop based on the feedback information from the followers. This consideration leads us to present a parallel splitting augmented Lagrangian method (abbreviated to PSALM). The proposed method can be extended to solve the system of equilibrium problems with three separable operators. Finally, it is explained why we cannot use the same technique to develop similar methods for problems with more than three separable operators.     

A continuation method for monotone variational inequalities

This paper presents a continuation method for monotone variational inequality problems based on a new smooth equation formulation. The existence, uniqueness and limiting behavior of the path generated by the method are analyzed.This work was supported by the National Science Foundation Presidential Young Investigator Award ECE-8552773 and by a grant from the Burlington Northern Railroad.     

An explicit algorithm for monotone variational inequalities

We introduce a fully explicit method for solving monotone variational inequalities in Hilbert spaces, where orthogonal projections onto the feasible set are replaced by projections onto suitable hyperplanes. We prove weak convergence of the whole generated sequence to a solution of the problem, under only the assumptions of continuity and monotonicity of the operator and existence of solutions.     

An efficient projection-type method for monotone variational inequalities in Hilbert spaces

Numerical Algorithms - We consider the monotone variational inequality problem in a Hilbert space and describe a projection-type method with inertial terms under the following properties: (a) The...     

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

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

单调混合变分不等式的若干新的迭代算法

In this paper,some new iterative algorithms for monotone mixed variational inequalities and the convergence in real Hilbert spaces are studied.     

An improved general extra-gradient method with refined step size for nonlinear monotone variational inequalities

Extra-gradient method and its modified versions are direct methods for variational inequalities VI(Ω, F) that only need to use the value of function F in the iterative processes. This property makes the type of extra-gradient methods very practical for some variational inequalities arising from the real-world, in which the function F usually does not have any explicit expression and only its value can be observed and/or evaluated for given variable. Generally, such observation and/or evaluation may be obtained via some costly experiments. Based on this view of point, reducing the times of observing the value of function F in those methods is meaningful in practice. In this paper, a new strategy for computing step size is proposed in general extra-gradient method. With the new step size strategy, the general extra-gradient method needs to cost a relatively minor amount of computation to obtain a new step size, and can achieve the purpose of saving the amount of computing the value of F in solving VI(Ω, F). Further, the convergence analysis of the new algorithm and the properties related to the step size strategy are also discussed in this paper. Numerical experiments are given and show that the amount of computing the value of function F in solving VI(Ω, F) can be saved about 12–25% by the new general extra-gradient method.     

Stable monotone variational inequalities

Variational inequalities associated with monotone operators (possibly nonlinear and multivalued) and convex sets (possibly unbounded) are studied in reflexive Banach spaces. A variety of results are given which relate to a stability concept involving a natural parameter. These include characterizations useful as criteria for stable existence of solutions and also several characterizations of surjectivity. The monotone complementarity problem is covered as a special case, and the results are sharpened for linear monotone complementarity and for generalized linear programming.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041 at the University of Wisconsin - Madison and by the National Science Foundation under Grant No. DMS-8405179 at the University of Illinois at Urbana-Champaign.     

A continuation method for (strongly) monotone variational inequalities

We consider the variational inequality problem, denoted by VIP(X, F), whereF is a strongly monotone function and the convex setX is described by some inequality (and possibly equality) constraints. This problem is solved by a continuation (or interior-point) method, which solves a sequence of certain perturbed variational inequality problems. These perturbed problems depend on a parameter > 0. It is shown that the perturbed problems have a unique solution for all values of > 0, and that any sequence generated by the continuation method converges to the unique solution of VIP(X,F) under a well-known linear independence constraint qualification (LICQ). We also discuss the extension of the continuation method to monotone variational inequalities and present some numerical results obtained with a suitable implementation of this method. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.