Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. (English) Zbl 0756.90081

Fukushima, Masao

Math. Program., Ser. A 53, No. 1, 99-110 (1992).

The variational inequality problem is (1): Find \(x^*\in S\subset\mathbb{R}^ n\) such that \(\langle F(x^*),x-x^*\rangle\geq 0\), \(\forall x\in\mathbb{R}^ n\) where \(S\neq\emptyset\) is closed and convex and \(F: \mathbb{R}^ n\to\mathbb{R}^ n\). Now with \(G\) being any \(n\times n\) positive definite matrix consider the program (2): \(\min\{\phi(y): y\in S\}\) where \(\phi(y)=\langle F(x),(y-x)\rangle+{1\over 2}\langle(y-x),G(y-x)\rangle\), and let \(-f(x): \mathbb{R}^ n\to\mathbb{R}\) be the optimal objective value of \(\phi(y)\) in (2).
The main result is now: (i) \(f(x)\geq 0\), \(\forall x\in S\), and (ii) \(x^*\) solves (1) if and only if it solves the program (3): \(\min\{f(x): x\in S\}\) and that happens if and only if \(f(x^*)=0\), \(x^*\in S\). Moreover \(f\) is continuously differentiable (continuous) if \(F\) is continuously differentiable (continuous). In the first case descent methods are presented to solve the program (3) by an iteration process.
A list of sixteen references closes the paper.

Reviewer: A.G.Azpeitia (Boston)

MSC:

90C30	Nonlinear programming
49J40	Variational inequalities
90-08	Computational methods for problems pertaining to operations research and mathematical programming
90C33	Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C99	Mathematical programming

References:

[1]	A. Auslender,Optimisation: Méthodes Numériques (Masson, Paris, 1976).
[2]	S. Dafermos, ”Traffic equilibrium and variational inequalities,”Transportation Science 14 (1980) 42–54.
[3]	S. Dafermos, ”An iterative scheme for variational inequalities,”Mathematical Programming 26 (1983) 40–47. · Zbl 0506.65026
[4]	J.E. Dennis, Jr. and R.B. Schnabel,Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Prentice-Hall, Englewood Cliffs, NJ, 1983).
[5]	M. Florian, ”Mathematical programming applications in national, regional and urban planning,” in: M. Iri and K. Tanabe, eds.,Mathematical Programming: Recent Developments and Applications (KTK Scientific Publishers, Tokyo, 1989) pp. 57–81. · Zbl 0679.90087
[6]	J.H. Hammond and T.L. Magnanti, ”Generalized descent methods for asymmetric systems of equations,”Mathematics of Operations Research 12 (1987) 678–699. · Zbl 0642.65035
[7]	P.T. Harker and J.S. Pang, ”Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications,”Mathematical Programming (Series B) 48 (1990) 161–220. · Zbl 0734.90098
[8]	D.W. Hearn, ”The gap function of a convex program,”Operations Research Letters 1 (1982) 67–71. · Zbl 0486.90070
[9]	T. Itoh, M. Fukushima and T. Ibaraki, ”An iterative method for variational inequalities with application to traffic equilibrium problems,”Journal of the Operations Research Society of Japan 31 (1988) 82–103. · Zbl 0637.90037
[10]	D. Kinderlehrer and G. Stampacchia,An Introduction to Variational Inequalities and Their Applications (Academic Press, New York, 1980). · Zbl 0457.35001
[11]	P. Marcotte, ”A new algorithm for solving variational inequalities with application to the traffic assignment problem,”Mathematical Programming 33 (1985) 339–351.
[12]	P. Marcotte and J.P. Dussault, ”A note on a globally convergent Newton method for solving monotone variational inequalities,”Operations Research Letters 6 (1987) 35–42. · Zbl 0623.65073
[13]	A. Nagurney, ”Competitive equilibrium problems, variational inequalities and regional science,”Journal of Regional Science 27 (1987) 503–517.
[14]	J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, New York, 1970). · Zbl 0241.65046
[15]	J.S. Pang and D. Chan, ”Iterative methods for variational and complementarity problems,”Mathematical Programming 24 (1982) 284–313. · Zbl 0499.90074
[16]	W.I. Zangwill,Nonlinear Programming: A Unified Approach (Prentice-Hall, Englewood Cliffs, NJ, 1969).