A note on a globally convergent Newton method for solving monotone variational inequalities

It is well-known (see Pang and Chan [8]) that Newton's method, applied to strongly monotone variational inequalities, is locally and quadratically convergent. In this paper we show that Newton's method yields a descent direction for a non-convex, non-differentiable merit function, even in the absence of strong monotonicity. This result is then used to modify Newton's method into a globally convergent algorithm by introducing a linesearch strategy. Furthermore, under strong monotonicity (i) the optimal face is attained after a finite number of iterations, (ii) the stepsize is eventually fixed to the value one, resulting in the usual Newton step. Computational results are presented.     

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.     

A modified projection method for solving co-coercive variational inequalities

This paper presents a modified projection method for solving variational inequalities, which can be viewed as an improvement of the method of Yan, Han and Sun [X.H. Yan, D.R. Han, W.Y. Sun, A modified projection method with a new direction for solving variational inequalities, Applied Mathematics and Computation 211 (2009) 118-129], by adopting a new prediction step. Under the same assumptions, we establish the global convergence of the proposed algorithm. Some preliminary computational results are reported.     

A non-interior-point smoothing method for variational inequality problem

In this paper, we focus on the variational inequality problem. Based on the Fischer-Burmeister function with smoothing parameters, the variational inequality problem can be reformulated as a system of parameterized smooth equations, a non-interior-point smoothing method is presented for solving the problem. The proposed algorithm not only has no restriction on the initial point, but also has global convergence and local quadratic convergence, moreover, the local quadratic convergence is established without a strict complementarity condition. Preliminary numerical results show that the algorithm is promising.     

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.     

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”.     

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

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.     

A globally convergent Newton method for convex SC1 minimization problems

This paper presents a globally convergent and locally superlinearly convergent method for solving a convex minimization problem whose objective function has a semismooth but nondifferentiable gradient. Applications to nonlinear minimax problems, stochastic programs with recourse, and their extensions are discussed.The research of the first author is based on work supported by the National Science Foundation under Grants DDM-9104078 and CCR-9213739. This research was carried out while he was visiting the University of New South Wales. The research of the second author is based on work supported by the Australian Research Council.     

A globally convergent BFGS method for nonlinear monotone equations without any merit functions

Since 1965, there has been significant progress in the theoretical study on quasi-Newton methods for solving nonlinear equations, especially in the local convergence analysis. However, the study on global convergence of quasi-Newton methods is relatively fewer, especially for the BFGS method. To ensure global convergence, some merit function such as the squared norm merit function is typically used. In this paper, we propose an algorithm for solving nonlinear monotone equations, which combines the BFGS method and the hyperplane projection method. We also prove that the proposed BFGS method converges globally if the equation is monotone and Lipschitz continuous without differentiability requirement on the equation, which makes it possible to solve some nonsmooth equations. An attractive property of the proposed method is that its global convergence is independent of any merit function.We also report some numerical results to show efficiency of the proposed method.

     

A nonmonotone smoothing Newton algorithm for solving general box constrained variational inequalities

In this paper, based on a new smoothing function, the general box constrained variational inequalities are solved by a smoothing Newton algorithm with a nonmonotone line search. The proposed algorithm is proved to be globally and locally superlinearly convergent under suitable assumptions. The preliminary numerical results are reported.