D-Gap Functions for Nonsmooth Variational Inequality Problems

We study the Clarke generalized gradient of the D-gap functions for the variational inequality problem (VIP) defined by a locally Lipschitz, but not necessarily differentiable, function in an Euclidean space. Using these results, we study the relationship between minimizing sequences and stationary sequences of the D-gap function, regardless of the existence of solutions of (VIP).     

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.     

Inexact Operator Splitting Methods with Selfadaptive Strategy for Variational Inequality Problems

The Peaceman-Rachford and Douglas-Rachford operator splitting methods are advantageous for solving variational inequality problems, since they attack the original problems via solving a sequence of systems of smooth equations, which are much easier to solve than the variational inequalities. However, solving the subproblems exactly may be prohibitively difficult or even impossible. In this paper, we propose an inexact operator splitting method, where the subproblems are solved approximately with some relative error tolerance. Another contribution is that we adjust the scalar parameter automatically at each iteration and the adjustment parameter can be a positive constant, which makes the methods more practical and efficient. We prove the convergence of the method and present some preliminary computational results, showing that the proposed method is promising. This work was supported by the NSFC grant 10501024.     

Equivalent Optimization Formulations and Error Bounds for Variational Inequality Problems

We investigate whether some merit functions for variational inequality problems (VIP) provide error bounds for the underlying VIP. Under the condition that the involved mapping F is strongly monotone, but not necessarily Lipschitz continuous, we prove that the so-called regularized gap function provides an error bound for the underlying VIP. We give also an example showing that the so-called D-gap function might not provide error bounds for a strongly monotone VIP.This research was supported by United College and by a direct grant of the Chinese University of Hong Kong. The authors thank the referees for helpful comments and suggestions.     

Derivative-Free Methods for Monotone Variational Inequality and Complementarity Problems

Monotone variational inequality problems with box constraints and complementarity problems are reformulated as simple-bound optimization problems. Some derivative-free methods for these problems are proposed. It is shown that, for these new methods, the updated point sequence remains feasible with respect to its simple constraints if the initial point is feasible. Under certain conditions, these methods are globally convergent.     

Unconstrained Optimization Reformulations of Variational Inequality Problems

Recently, Peng considered a merit function for the variational inequality problem (VIP), which constitutes an unconstrained differentiable optimization reformulation of VIP. In this paper, we generalize the merit function proposed by Peng and study various properties of the generalized function. We call this function the D-gap function. We give conditions under which any stationary point of the D-gap function is a solution of VIP and conditions under which it provides a global error bound for VIP. We also present a descent method for solving VIP based on the D-gap function.     

Smoothing Functions and Smoothing Newton Method for Complementarity and Variational Inequality Problems

This paper provides for the first time some computable smoothing functions for variational inequality problems with general constraints. This paper proposes also a new version of the smoothing Newton method and establishes its global and superlinear (quadratic) convergence under conditions weaker than those previously used in the literature. These are achieved by introducing a general definition for smoothing functions, which include almost all the existing smoothing functions as special cases.     

A Modified Alternating Direction Method for Variational Inequality Problems

The alternating direction method is an attractive method for solving large-scale variational inequality problems whenever the subproblems can be solved efficiently. However, the subproblems are still variational inequality problems, which are as structurally difficult to solve as the original one. To overcome this disadvantage, in this paper we propose a new alternating direction method for solving a class of nonlinear monotone variational inequality problems. In each iteration the method just makes an orthogonal projection to a simple set and some function evaluations. We report some preliminary computational results to illustrate the efficiency of the method. Accepted 4 May 2001. Online publication 19 October, 2001.     

Construction of Iterative Methods for Variational Inequality and Fixed Point Problems

In this article, we first introduce two iterative methods for finding a common element of the set of fixed points of a nonexpansive mapping and the set of solutions of the variational inequality for an inverse strongly monotone mapping in a Hilbert space. Then we show that the proposed iterative methods converge strongly to a minimum norm element of two sets.     

Augmented Lagrangian Theory,Duality and Decomposition Methods for Variational Inequality Problems

In this paper, we develop the augmented Lagrangian theory and duality theory for variational inequality problems. We propose also decomposition methods based on the augmented Lagrangian for solving complex variational inequality problems with coupling constraints.     

On Lanczos Based Methods for the Regularization of Discrete Ill-Posed Problems

We study hybrid methods for the solution of linear ill-posed problems. Hybrid methods are based on he Lanczos process, which yields a sequence of small bidiagonal systems approximating the original ill-posed problem. In a second step, some additional regularization, typically the truncated SVD, is used to stabilize the iteration. We investigate two different hybrid methods and interpret these schemes as well-known projection methods, namely least-squares projection and the dual least-squares method. Numerical results are provided to illustrate the potential of these methods. This gives interesting insight in to the behavior of hybrid methods in practice.This revised version was published online in October 2005 with corrections to the Cover Date.     

Nonstationary Iterated Tikhonov Regularization

A convergence rate is established for nonstationary iterated Tikhonov regularization, applied to ill-posed problems involving closed, densely defined linear operators, under general conditions on the iteration parameters. It is also shown that an order-optimal accuracy is attained when a certain a posteriori stopping rule is used to determine the iteration number.     

Solvability of Variational Inequality Problems

This paper presents the new concept of exceptional family of elements for the variational inequality problem with a continuous function over a general unbounded closed convex set. We establish a characterization theorem that can be used to derive several new existence and compactness conditions on the solution set. Our findings generalize well-known results for various types of variational inequality problems. For a pseudomonotone variational inequality problem, our new existence conditions are both sufficient and necessary.     

Quadratic Convergence of a Long-Step Interior-Point Method for Nonlinear Monotone Variational Inequality Problems

This paper offers an analysis on a standard long-step primal-dual interior-point method for nonlinear monotone variational inequality problems. The method has polynomial-time complexity and its q-order of convergence is two. The results are proved under mild assumptions. In particular, new conditions on the invariance of the rank and range space of certain matrices are employed, rather than restrictive assumptions like nondegeneracy.     

Solving Variational Inequality Problems with Linear Constraints by a Proximal Decomposition Algorithm

The alternating direction method solves large scale variational inequality problems with linear constraints via solving a series of small scale variational inequality problems with simple constraints. The algorithm is attractive if the subproblems can be solved efficiently and exactly. However, the subproblem is itself variational inequality problem, which is structurally also difficult to solve. In this paper, we develop a new decomposition algorithm, which, at each iteration, just solves a system of well-conditioned linear equations and performs a line search. We allow to solve the subproblem approximately and the accuracy criterion is the constructive one developed recently by Solodov and Svaiter. Under mild assumptions on the problem's data, the algorithm is proved to converge globally. Some preliminary computational results are also reported to illustrate the efficiency of the algorithm.     

A Combined Feasible-Infeasible Point Continuation Method for Strongly Monotone Variational Inequality Problems

In this paper, we discuss the variational inequality problems VIP(X, F), where F is a strongly monotone function and the convex feasible set X is described by some inequaliy constraints. We present a continuation method for VIP(X, F), which solves a sequence of perturbed variational inequality problems PVIP(X, F, , ) depending on two parameters 0 and >0. It is worthy to point out that the method will be a feasible point type when =0 and an infeasible point type when >0, i.e., it is a combined feasible–infeasible point (CFIFP for short) method. We analyse the existence, uniqueness and continuity of the solution to PVIP(X, F, , ), and prove that any sequence generated by this method converges to the unique solution of VIP(X, F). Moreover, some numerical results of the algorithm are reported which show the algorithm is effective.     

Well-Posedness for Variational Inequality Problems with Generalized Monotone Set-Valued Maps

In this paper, we introduce two new classes of generalized monotone set-valued maps, namely relaxed μ–p monotone and relaxed μ–p pseudomonotone. Relations of these classes with some other well-known classes of generalized monotone maps are investigated. Employing these new notions, we derive existence and well-posedness results for a set-valued variational inequality problem. Our results generalize some of the well-known results. A gap function is proposed for the variational inequality problem and a lower error bound is obtained under the assumption of relaxed μ–p pseudomonotonicity. An equivalence relation between the well-posedness of the variational inequality problem and that of a related optimization problem pertaining to the gap function is also presented.     

Exceptional Families and Existence Theorems for Variational Inequality Problems

This paper introduces the concept of exceptional family for nonlinear variational inequality problems. Among other things, we show that the nonexistence of an exceptional family is a sufficient condition for the existence of a solution to variational inequalities. This sufficient condition is weaker than many known solution conditions and it is also necessary for pseudomonotone variational inequalities. From the results in this paper, we believe that the concept of exceptional families of variational inequalities provides a new powerful tool for the study of the existence theory for variational inequalities.     

Tikhonov Regularization of Large Linear Problems

Many numerical methods for the solution of linear ill-posed problems apply Tikhonov regularization. This paper presents a new numerical method, based on Lanczos bidiagonalization and Gauss quadrature, for Tikhonov regularization of large-scale problems. An estimate of the norm of the error in the data is assumed to be available. This allows the value of the regularization parameter to be determined by the discrepancy principle.