A Gauss-Seidel iteration method for nonlinear variational inequality problems over rectangles

This paper presents a simple yet practically useful Gauss-Seidel iterative method for solving a class of nonlinear variational inequality problems over rectangles and of nonlinear complementarity problems. This scheme is a nonlinear generalization of a robust iterative method for linear complementarity problems developed by Mangasarian. Global convergence is presented for problems with Z-functions. It is noted that the suggested method can be viewed as a specific case of a class of linear approximation methods studied by Pang and others.     

Newton's method for the nonlinear complementarity problem: A B-differentiable equation approach

This paper describes a damped-Newton method for solving the nonlinear complementarity problem when it is formulated as a system of B-differentiable equations through the use of the Minty-map. This general Newton algorithm contains a one-dimensional line search and possesses a global convergence property under certain conditions; modifications and heuristic implementations of the algorithm for the case when these conditions do not hold are also discussed. The numerical experiments show that, in general, this new scheme is more efficient and robust than the traditional Josephy-Newton algorithm.     

Regularized gap functions for nonsmooth variational inequality problems

Under the condition that the involved function F is locally Lipschitz, but not necessarily differentiable, we investigate the regularized gap function defined by a generalized distance function for the variational inequality problem (VIP). First, we compute exactly the Clarke-Rockafellar directional derivatives of the regularized gap functions (and of some modified ones). Second, using these results, we show that, under the strongly monotonicity assumption, the regularized gap functions have fractional exponent error bounds, and thereby we provide an algorithm of Armijo type to solve the VIP.     

A globally convergent method for solving nonlinear equations without the differentiability condition

We give a general iterative method which computes the maximal real rootx _max of a one variable Lipschitzian function in a given interval. The method generates a monotonically decreasing sequence which converges towardsx _max or demonstrates the non-existence of a real root in the considered interval. We show that the method is globally convergent and locally linearly convergent. We also compute the number of iterations needed to reach the given accuracy.     

Sensitivity analysis for variational inequalities and nonlinear complementarity problems

This paper surveys the main results in the area of sensitivity analysis for finite-dimensional variational inequality and nonlinear complementarity problems. It provides an overview of Lipschitz continuity and differentiability properties of perturbed solutions for variational inequality problems, defined on both fixed and perturbed sets, and for nonlinear complementarity problems.     

Extragradient methods for differential variational inequality problems and linear complementarity systems

In this paper, 2 extragradient methods for solving differential variational inequality (DVI) problems are presented, and the convergence conditions are derived. It is shown that the presented extragradient methods have weaker convergence conditions in comparison with the basic fixed‐point algorithm for solving DVIs. Then the linear complementarity systems, as an important and practical special case of DVIs, are considered, and the convergence conditions of the presented extragradient methods are adapted for them. In addition, an upper bound for the Lipschitz constant of linear complementarity systems is introduced. This upper bound can be used for adjusting the parameters of the extragradient methods, to accelerate the convergence speed. Finally, 4 illustrative examples are considered to support the theoretical results.     

A globally convergent descent method for nonsmooth variational inequalities

We propose a descent method via gap functions for solving nonsmooth variational inequalities with a locally Lipschitz operator. Assuming monotone operator (not necessarily strongly monotone) and bounded domain, we show that the method with an Armijo-type line search is globally convergent. Finally, we report some numerical experiments. This work has been supported by the National Research Program PRIN/2005017083 “Innovative Problems and Methods in Nonlinear Optimization”.     

A nonlinear descent method for a variational inequality on a nonconvex set

In this paper, we consider a generalized variational inequality problem which involves the integrable cost mapping and a nonsmooth mapping with convex components. We propose a new gradient-type method which determines a stepsize by using the smooth part of the cost function. Thus, the method does not utilize analogs of derivatives of nonsmooth functions. We show that its convergence does not require additional assumptions.     

A globally convergent method for nonlinear programming

Recently developed Newton and quasi-Newton methods for nonlinear programming possess only local convergence properties. Adopting the concept of the damped Newton method in unconstrained optimization, we propose a stepsize procedure to maintain the monotone decrease of an exact penalty function. In so doing, the convergence of the method is globalized.This research was supported in part by the National Science Foundation under Grant No. ENG-75-10486.     

Components identification based method for box constrained variational inequality problems with almost linear functions

We present a method for solving a class of box constrained variational inequality problems. The method makes use of a procedure for identifying some components of the solution by bounding it with an interval vector. It is shown that the method computes an approximate solution of the variational inequality problem by solving at most n reduced systems of equations, where n is the dimension of the problem. Among those systems, only the one of the smallest dimension has to be solved with high accuracy. The others are solved merely to identify some components of the solution, and so the computation can be done under a very mild requirement of accuracy. Numerical results are presented for the obstacle problem, to illustrate the efficiency of the method. AMS subject classification (2000)  90C33, 65G30, 65K10     

A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems

A new algorithm for the solation of large-scale nonlinear complementarity problems is introduced. The algorithm is based on a nonsmooth equation reformulation of the complementarity problem and on an inexact Levenberg-Marquardt-type algorithm for its solution. Under mild assumptions, and requiring only the approximate solution of a linear system at each iteration, the algorithm is shown to be both globally and superlinearly convergent, even on degenerate problems. Numerical results for problems with up to 10 000 variables are presented. Partially supported by Agenzia Spaziale Italiana, Roma, Italy.     

A smoothing inexact Newton method for nonlinear complementarity problems

In this article, we propose a new smoothing inexact Newton algorithm for solving nonlinear complementarity problems (NCP) base on the smoothed Fischer-Burmeister function. In each iteration, the corresponding linear system is solved only approximately. The global convergence and local superlinear convergence are established without strict complementarity assumption at the NCP solution. Preliminary numerical results indicate that the method is effective for large-scale NCP.     

A modified SQP-filter method for nonlinear complementarity problem

The nonlinear complementarity problem can be reformulated as a nonlinear programming. For solving nonlinear programming, sequential quadratic programming (SQP) type method is very effective. Moreover, filter method, for its good numerical results, are extensively studied to handle nonlinear programming problems recently. In this paper, a modified quadratic subproblem is proposed. Based on it, we employ filter technique to tackle nonlinear complementarity problem. This method has no demand on initial point. The restoration phase, which is always used in traditional filter method, is not needed. Global convergence results of the proposed algorithm are established under suitable conditions. Some numerical results are reported in this paper.     

An inexact NE/SQP method for solving the nonlinear complementarity problem

In this paper, we present an extension to the NE/SQP method; the latter is a robust algorithm that we proposed for solving the nonlinear complementarity problem in an earlier article. In this extended version of NE/SQP, instead of exactly solving the quadratic program subproblems, approximate solutions are generated via an inexact rule.Under a proper choice for this rule, this inexact method is shown to inherit the same convergence properties of the original NE/SQP method. In addition to developing the convergence theory for the inexact method, we also present numerical results of the algorithm tested on two problems of varying size.     

A new logarithmic-quadratic proximal method for nonlinear complementarity problems

In this paper, we propose a new modified logarithmic-quadratic proximal (LQP) method for solving nonlinear complementarity problems (NCP). We suggest using a prediction-correction method to solve NCP. The predictor is obtained via solving the LQP system approximately under significantly relaxed accuracy criterion and the new iterate is computed by using a new step size α_k. Under suitable conditions, we prove that the new method is globally convergent. We report preliminary computational results to illustrate the efficiency of the proposed method. This new method can be considered as a significant refinement of the previously known methods for solving nonlinear complementarity problems.     

INEXACT DAMPED NEWTON METHOD FOR NONLINEAR COMPLEMENTARITY PROBLEMS

In this paper, we propose an inexact clamped Newton method for solving nonlinear complementarity problems based on the equivalent B-differentiable equations.Global convergence and locally quadratic convergence are obtained,and numerical results are given.     

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.     

Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory,algorithms and applications

Over the past decade, the field of finite-dimensional variational inequality and complementarity problems has seen a rapid development in its theory of existence, uniqueness and sensitivity of solution(s), in the theory of algorithms, and in the application of these techniques to transportation planning, regional science, socio-economic analysis, energy modeling, and game theory. This paper provides a state-of-the-art review of these developments as well as a summary of some open research topics in this growing field.The research of this author was supported by the National Science Foundation Presidential Young Investigator Award ECE-8552773 and by the AT&T Program in Telecommunications Technology at the University of Pennsylvania.The research of this author was supported by the National Science Foundation under grant ECS-8644098.