A TRUST REGION-TYPE METHOD FOR SOLVINGMONOTONE VARIATIONAL INEQUALITY

1.IntroductionLetSbeanonemptyclosedconvexsubsetofR"andletF:R"-R"beacontinuousmapping.ThevariatiollalillequalityproblemFindx*6Ssuchthat(F(x*),x--x*)20forallxeS(VIP)iswidelyusedtostudyvariousequilibriummodelsarisingilleconomic,operatiollsresearch,transportatiollandregionalsciellces[2'3I?where(.,.)dellotestheinnerproductinR".Manyiterativemethodsfor(VIP)havebeendeveloped,forexample,projectionmethods[7ts],thenonlinearJacobimethod[5],thesuccessiveoverrelaxation.ethod[9]andgeneralizedgradient.…     

Global Method for Monotone Variational Inequality Problems with Inequality Constraints

We consider optimization methods for monotone variational inequality problems with nonlinear inequality constraints. First, we study the mixed complementarity problem based on the original problem. Then, a merit function for the mixed complementarity problem is proposed, and some desirable properties of the merit function are obtained. Through the merit function, the original variational inequality problem is reformulated as simple bounded minimization. Under certain assumptions, we show that any stationary point of the optimization problem is a solution of the problem considered. Finally, we propose a descent method for the variational inequality problem and prove its global convergence.     

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

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

解变分不等式问题的混合方法

By using Fukushima‘s differentiable merit function,Taji,Fukushima and Ibaraki have given a globally convergent modified Newton method for the strongly monotone variational inequality problem and proved their method to be quadratically convergent under certain assumptions in 1993. In this paper a hybrid method for the variational inequality problem under the assumptions that the mapping F is continuously differentiable and its Jacobian matrix F(x) is positive definite for all x∈S rather than strongly monotone and that the set S is nonempty, polyhedral,closed and convex is proposed. Armijo-type line search and trust region strategies as well as Fukushima‘s differentiable merit function are incorporated into the method. It is then shown that the method is well defined and globally convergent and that,under the same assumptions as those of Taji et al. ,the method reduces to the basic Newton method and hence the rate of convergence is quadratic. Computational experiences show the efficiency of the proposed method.     

Globally Convergent Broyden-Like Methods for Semismooth Equations and Applications to VIP, NCP and MCP

In this paper, we propose a general smoothing Broyden-like quasi-Newton method for solving a class of nonsmooth equations. Under appropriate conditions, the proposed method converges to a solution of the equation globally and superlinearly. In particular, the proposed method provides the possibility of developing a quasi-Newton method that enjoys superlinear convergence even if strict complementarity fails to hold. We pay particular attention to semismooth equations arising from nonlinear complementarity problems, mixed complementarity problems and variational inequality problems. We show that under certain conditions, the related methods based on the perturbed Fischer–Burmeister function, Chen–Harker–Kanzow–Smale smoothing function and the Gabriel–Moré class of smoothing functions converge globally and superlinearly.     

Extended Projection Methods for Monotone Variational Inequalities

In this paper, we prove that each monotone variational inequality is equivalent to a two-mapping variational inequality problem. On the basis of this fact, a new class of iterative methods for the solution of nonlinear monotone variational inequality problems is presented. The global convergence of the proposed methods is established under the monotonicity assumption. The conditions concerning the implementability of the algorithms are also discussed. The proposed methods have a close relationship to the Douglas–Rachford operator splitting method for monotone variational inequalities.     

A Class of Combined Relaxation Methods for Decomposable Variational Inequalities

Combined relaxation methods are convergent to a solution of variational inequality problems under rather mild assumptions and admit various auxiliary procedures within their two-level structure. In this work, we consider ways to construct decomposition schemes within one class of combined relaxation methods, which maintain useful convergence properties. An application to primal-dual variational inequality problems is also given.     

一般单调变分不等式的一个改进的预估-校正算法

最近何炳生等提出了解大规模单调变分不等式的一种预估-校正算法,然而,这个方法在计算每一个试验点时需要一次投影运算,因而计算量较大．为了克服这个缺点,我们提出了一个解一般大规模g-单调变分不等式的新的预估-校正算法,该方法使用了一个非常有效的预估步长准则,每个步长的选取只需要计算一次投影,这将大大减少计算量．数值试验说明我们的算法比最新文献中出现的投影类方法有效．     

An Affine Scaling Interior Trust Region Method via Optimal Path for Solving Monotone Variational Inequality Problem with Linear Constraints

Based on a differentiable merit function proposed by Taji et al. in ＂Math. Prog. Stud., 58, 1993, 369-383＂, the authors propose an affine scaling interior trust region strategy via optimal path to modify Newton method for the strictly monotone variational inequality problem subject to linear equality and inequality constraints. By using the eigensystem decomposition and affine scaling mapping, the authors form an affine scaling optimal curvilinear path very easily in order to approximately solve the trust region subproblem. Theoretical analysis is given which shows that the proposed algorithm is globally convergent and has a local quadratic convergence rate under some reasonable conditions.     

Viscosity Approximation Methods for a Class of Generalized Split Feasibility Problems with Variational Inequalities in Hilbert Space

Strong convergence theorem of viscosity approximation methods for nonexpansive mapping have been studied. We also know that CQ algorithm for solving the split feasibility problem (SFP) has a weak convergence result. In this paper, we use viscosity approximation methods and some related knowledge to solve a class of generalized SFP’s with monotone variational inequalities in Hilbert space. We propose some iterative algorithms based on viscosity approximation methods and get strong convergence theorems. As applications, we can use algorithms we proposed for solving split variational inequality problems (SVIP), split constrained convex minimization problems and some related problems in Hilbert space.     

解可分离结构变分不等式的一种新的交替方向法

交替方向法是求解可分离结构变分不等式问题的经典方法之一, 它将一个大型的变分不等式问题分解成若干个小规模的变分不等式问题进行迭代求解. 但每步迭代过程中求解的子问题仍然摆脱不了求解变分不等式子问题的瓶颈. 从数值计算上来说, 求解一个变分不等式并不是一件容易的事情.因此, 本文提出一种新的交替方向法, 每步迭代只需要求解一个变分不等式子问题和一个强单调的非线性方程组子问题. 相对变分不等式问题而言, 我们更容易、且有更多的有效算法求解一个非线性方程组问题. 在与经典的交替方向法相同的假设条件下, 我们证明了新算法的全局收敛性. 进一步的数值试验也验证了新算法的有效性.     

Solving variational inequalities by a modified projection method with an effective step-size

In this paper, we propose a new projection method for the solution of variational inequality problems. The method is simple, which uses only function evaluations and projections onto the feasible set. We adopt a new step-size rule and a new search direction in the new method. Under the mild conditions, we prove the proposed method is globally convergent. Preliminary numerical results are reported.     

箱约束变分不等式的一种新NCP-函数及其广义牛顿法

１．引 言设，变分不等式，记为ＶＩ（Ｘ，Ｆ），是指：求ｘ＝Ｘ使记为箱式约束时，称 ＶＩ（Ｘ，Ｆ）为箱约束变分不等式，记为 ＶＩ（［ａ，ｂ］，Ｆ）．若ａｉ＝０，ｂｉ＝＋∞，　　　　　　　　　　　　　　　　　　　　　　　　　为非线性互补问题ＮＣＰ（Ｆ）：求ｘ∈Ｒ     

求解不可微箱约束变分不等式的下降算法

1 引 论 设X(?)Rn是非空闭集,F:Rn→Rn连续映射,变分不等式问题VI(X,F)是指:求x∈X,使 F(x)T(y-x)≥0,　 (?)y∈X,(1)记指标集N=(1,2,…,n},当 X=[a,b]≡{x∈Rn|a≤xi≤bi,i∈N},(2)其中a={a1,a2,…,an}T,b={b1,b2,…,bn}T∈Rn时,VI(X,F)化为箱约束变分不等式VI(a,b,F).若ai=0,bi=+∞,i∈N,即X=R+n≡{x∈Rn|x≥0}时,VI(a,b,F)化为非线性     

A B-differentiable equation-based,globally and locally quadratically convergent algorithm for nonlinear programs,complementarity and variational inequality problems

This paper presents a globally convergent, locally quadratically convergent algorithm for solving general nonlinear programs, nonlinear complementarity and variational inequality problems. The algorithm is based on a unified formulation of these three mathematical programming problems as a certain system of B-differentiable equations, and is a modification of the damped Newton method described in Pang (1990) for solving such systems of nonsmooth equations. The algorithm resembles several existing methods for solving these classes of mathematical programs, but has some special features of its own; in particular, it possesses the combined advantage of fast quadratic rate of convergence of a basic Newton method and the desirable global convergence induced by one-dimensional Armijo line searches. In the context of a nonlinear program, the algorithm is of the sequential quadratic programming type with two distinct characteristics: (i) it makes no use of a penalty function; and (ii) it circumvents the Maratos effect. In the context of the variational inequality/complementarity problem, the algorithm provides a Newton-type descent method that is guaranteed globally convergent without requiring the F-differentiability assumption of the defining B-differentiable equations.This work was based on research supported by the National Science Foundation under Grant No. ECS-8717968.     

仿射变换内点信赖域类方法解单调变分不等式问题

基于Taji引入的一类可微的简单边界约束的严格单调变分不等式问题的势函数,本文提出了仿射变换内点信赖域类修正牛顿法.进一步,作者不仅从理论上证明了该算法的整体收敛性,并且在合理的假设条件下,给出了算法具有局部二次收敛速率.     

A projected gradient method with nonmonotonic backtracking technique for solving convex constrained monotone variational inequality problem

Based on a differentiable merit function proposed by Taji, et al in “Mathematical Programming, 1993, 58： 369-383”, a projected gradient trust region method for the monotone variational inequality problem with convex constraints is presented. Theoretical analysis is given which proves that the proposed algorithm is globally convergent and has a local quadratic convergence rate under some reasonable conditions. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.     

A Global Linear and Local Quadratic Continuation Smoothing Method for Variational Inequalities with Box Constraints

In this paper, we propose a continuation method for box constrained variational inequality problems. The continuation method is based on the class of Gabriel-Moré smooth functions and has the following attractive features: It can start from any point; It has a simple and natural neighborhood definition; It solves only one approximate Newton equation at each iteration; It converges globally linearly and locally quadratically under nondegeneracy assumption at the solution point and other suitable assumptions. A hybrid method is also presented, which is shown to preserve the above convergence properties without the nondegeneracy assumption at the solution point. In particular, the hybrid method converges finitely for affine problems.     

Descent method with inexact linesearch for mixed variational inequalities

We propose a descent method with respect to a merit function for the mixed variational inequality involving a general nonlinear mapping and a convex, but not necessarily differentiable function. The method utilizes an inexact linesearch procedure. Its convergence is proved under the additional assumptions of continuity and strong monotonicity of the cost mapping.     

Iterative methods for variational and complementarity problems

In this paper, we study both the local and global convergence of various iterative methods for solving the variational inequality and the nonlinear complementarity problems. Included among such methods are the Newton and several successive overrelaxation algorithms. For the most part, the study is concerned with the family of linear approximation methods. These are iterative methods in which a sequence of vectors is generated by solving certain linearized subproblems. Convergence to a solution of the given variational or complementarity problem is established by using three different yet related approaches. The paper also studies a special class of variational inequality problems arising from such applications as computing traffic and economic spatial equilibria. Finally, several convergence results are obtained for some nonlinear approximation methods.This research was based on work supported by the National Science Foundation under grant ECS-7926320.