Solving a class of variational inequalities with inexact oracle operators
Consider a class of variational inequality problems of finding <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$${x^*\in S}$$</EquationSource> </InlineEquation>, such that <Equation ID="Equa"> <EquationSource Format="TEX">$$f(x^*)^\top (z-x^*)\geq 0,\quad \forall z\in S,$$</EquationSource> </Equation> where the underlying mapping f is hard to evaluate (sometimes its explicit form is unknown), and S has the following structure <Equation ID="Equb"> <EquationSource Format="TEX">$$S=\{x\in R^n\; | \; Ax\le b, x\in K\}.$$</EquationSource> </Equation>For any given Lagrangian multiplier y associated with the linear inequality constraint in S, a solution of the relaxed variational inequality problem of finding <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$${\hat x\in K}$$</EquationSource> </InlineEquation>, such that <Equation ID="Equc"> <EquationSource Format="TEX">$$(x^\prime-\hat x)^\top (f(\hat x)+A^\top y)\geq 0 \quad\forall x^\prime \in K \quad\quad\quad\quad (1)$$</EquationSource> </Equation> can be given by an oracle. This class of problems arises frequently in economics and engineering. In this paper, we focus on considering the above problems where the underlying mapping f, though is unknown, is strongly monotone. We propose an iterative method for solving this class of variational inequality problems. At each iteration, the method consists of two steps: predictor and corrector. At the predictor step, a trial multiplier is given and the oracle is called for a solution of the relaxed variational inequality problem (1); then at the corrector step, the multiplier y is updated, using the information from the predictor step. We allow the oracle to give just an inexact solution of the relaxed variational inequality problem at the predictor step, which makes the method very efficient and practical. Under some suitable conditions, the global convergence of the method is proved. Some numerical examples are presented to illustrate the method. Copyright Springer-Verlag 2010
