Solving a class of variational inequalities with inexact oracle operators

Deren Han (), Wei Xu () and Hai Yang

Mathematical Methods of Operations Research, 2010, vol. 71, issue 3, 427-452

Abstract: Consider a class of variational inequality problems of finding $${x^*\in S}$$ , such that $$f(x^*)^\top (z-x^*)\geq 0,\quad \forall z\in S,$$ where the underlying mapping f is hard to evaluate (sometimes its explicit form is unknown), and S has the following structure $$S=\{x\in R^n\; | \; Ax\le b, x\in K\}.$$ For any given Lagrangian multiplier y associated with the linear inequality constraint in S, a solution of the relaxed variational inequality problem of finding $${\hat x\in K}$$ , such that $$(x^\prime-\hat x)^\top (f(\hat x)+A^\top y)\geq 0 \quad\forall x^\prime \in K \quad\quad\quad\quad (1)$$ 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

Keywords: Variational inequality problems; Inexact oracle; System optimum; Traffic equilibrium (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1007/s00186-009-0299-0 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:71:y:2010:i:3:p:427-452

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-009-0299-0

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().