A class of gap functions for variational inequalities. (English) Zbl 0819.65101
Let \(K\) be a closed convex set in \(R^ n\) and \(T : K \to R^ n\) be a continuous operator. The problem of finding \(u \in K\) such that \(\langle Tu,v - u \rangle \geq 0\) for all \(v \in K\), is known as the variational inequality problem (VIP). A function \(g : K \to R \cup \{-\infty, \infty\}\) is a gap (merit) function for (VIP) if (i) \(g\) is restricted in sign on \(K\) and (ii) \(g(u) = 0\) if and only if \(u \in \Omega\), where \(\Omega\) is the solution set of (VIP).
In this interesting paper, the authors consider and study a new class of gap functions. They also discuss some algorithmic equivalence results relating their work to that of S. Dafermos [Math. Program. 26, 40- 47 (1983; Zbl 0506.65026)], G. Cohen [J. Optimization Theory Appl. 59, No. 2, 325-334 (1988; Zbl 0653.90062)] and M. A. Noor [ibid. 73, No. 2, 409-413 (1992; Zbl 0794.49009)]. Using the gap functions, a general descent framework has been developed for finding the approximate solution of variational inequalities. The results presented in this paper represent an improvement of the previously known results in this area.
Remark: In a recent paper, the reviewer [Some nonlinear variational inequalities, Tamkang J. Math. Vol. 26, No. 2 (1995)] has proved that the gap functions discussed in this paper can be derived by using the auxiliary principle technique.
In this interesting paper, the authors consider and study a new class of gap functions. They also discuss some algorithmic equivalence results relating their work to that of S. Dafermos [Math. Program. 26, 40- 47 (1983; Zbl 0506.65026)], G. Cohen [J. Optimization Theory Appl. 59, No. 2, 325-334 (1988; Zbl 0653.90062)] and M. A. Noor [ibid. 73, No. 2, 409-413 (1992; Zbl 0794.49009)]. Using the gap functions, a general descent framework has been developed for finding the approximate solution of variational inequalities. The results presented in this paper represent an improvement of the previously known results in this area.
Remark: In a recent paper, the reviewer [Some nonlinear variational inequalities, Tamkang J. Math. Vol. 26, No. 2 (1995)] has proved that the gap functions discussed in this paper can be derived by using the auxiliary principle technique.
Reviewer: M.A.Noor (Riyadh)
MSC:
| 65K10 | Numerical optimization and variational techniques |
| 49M30 | Other numerical methods in calculus of variations (MSC2010) |
| 49J40 | Variational inequalities |
References:
| [1] | L. Armijo, ”Minimization of functions having Lipschitz continuous first partial derivatives,”Pacific Journal of Mathematics 16 (1966) 1–3. · Zbl 0202.46105 |
| [2] | G. Auchmuty, ”Variational principles for variational inequalities,”Numerical Functional Analysis and Optimization 10 (1989) 863–874. · Zbl 0678.49010 · doi:10.1080/01630568908816335 |
| [3] | A. Auslender,Optimisation: Méthodes Numériques (Masson, Paris, France, 1976). |
| [4] | M.S. Bazaraa and C.M. Shetty,Nonlinear Programming: Theory and Algorithms (Wiley, New York, 1979). |
| [5] | D.P. Bertsekas and J.N. Tsitsiklis,Parallel and Distributed Computation: Numerical Methods (Prentice-Hall, London, 1989). |
| [6] | F.H. Clarke, ”Generalized gradients and applications,”Transactions of the American Mathematical Society 205 (1975) 247–262. · Zbl 0307.26012 · doi:10.1090/S0002-9947-1975-0367131-6 |
| [7] | G. Cohen, ”Auxiliary problem principle and decomposition of optimization problems,”Journal of Optimization Theory and Applications 32 (1980) 277–305. · Zbl 0417.49046 · doi:10.1007/BF00934554 |
| [8] | G. Cohen, ”Auxiliary problem principle extended to variational inequalities,”Journal of Optimization Theory and Applications 59 (1988) 325–333. · Zbl 0628.90069 · doi:10.1007/BF00940305 |
| [9] | R.W. Cottle, ”Nonlinear programs with positively bounded Jacobians,”SIAM Journal on Applied Mathematics 14 (1966) 147–158. · Zbl 0158.18903 · doi:10.1137/0114012 |
| [10] | S. Dafermos, ”An iterative scheme for variational inequalities,”Mathematical Programming 26 (1983) 40–47. · Zbl 0506.65026 · doi:10.1007/BF02591891 |
| [11] | V.F. Demyanov and A.B. Pevnyi, ”Numerical methods for finding saddle points,”USSR Computational Mathematics and Mathematical Physics 12 (1972) 11–52. · Zbl 0282.90040 · doi:10.1016/0041-5553(72)90002-X |
| [12] | V.F. Demyanov and A.M. Rubinov,Approximate Methods in Optimization Problems (Elsevier, New York, 1970). · Zbl 0217.46203 |
| [13] | J.C. Dunn, ”Convergence rates for conditional gradient sequences generated by implicit step length rules,”SIAM Journal on Control and Optimization 18 (1980) 473–487. · Zbl 0457.65048 · doi:10.1137/0318035 |
| [14] | Yu.G. Evtushenko,Numerical Optimization Techniques (Optimization Software, New York, 1985). |
| [15] | M. Fukushima, ”Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems,”Mathematical Programming 53 (1992) 99–110. · Zbl 0756.90081 · doi:10.1007/BF01585696 |
| [16] | J.H. Hammond and T.L. Magnanti, ”A contracting ellipsoid method for variational inequality problems,” Working Paper OR 160-87, Operations Research Center, Massachusetts Institute of Technology (Cambridge, MA, 1987). |
| [17] | P.T. Harker and J.-S. Pang, ”Finite dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications,”Mathematical Programming 48 (1990) 161–220. · Zbl 0734.90098 · doi:10.1007/BF01582255 |
| [18] | D.W. Hearn, ”Network aggregation in transportation planning models, Part I,” Mathtec Final Report DOT-TSC-RSPD-78-8, Mathtec (Princeton, NJ, 1978). |
| [19] | D.W. Hearn, ”The gap function of a convex program,”Operation Research Letters 1 (1982) 67–71. · Zbl 0486.90070 · doi:10.1016/0167-6377(82)90049-9 |
| [20] | D.W. Hearn and S. Lawphongpanich, ”A dual ascent algorithm for traffic assignment problems,” Conference paper, The Italy – USA Joint Seminar on Urban Traffic Networks, Capri, Italy, 1989. |
| [21] | D.W. Hearn, S. Lawphongpanich and S. Nguyen, ”Convex programming formulations of the asymmetric traffic assignment problem,”Transportation Research 18B (1984) 357–365. |
| [22] | D.W. Hearn and S. Nguyen, ”Dual and saddle functions related to the gap function,” Research Report 82-4, Department of Industrial and Systems Engineering, University of Florida (Gainesville, FL, 1982). |
| [23] | W.W. Hogan, ”Point-to-set maps in mathematical programming,”SIAM Review 15 (1973) 591–603. · Zbl 0256.90042 · doi:10.1137/1015073 |
| [24] | S. Kakutani, ”A generalization of Brouwer’s fixed point theorem,”Duke Mathematical Journal 8 (1941) 457–459. · Zbl 0061.40304 · doi:10.1215/S0012-7094-41-00838-4 |
| [25] | S. Karamardian, ”Generalized complementarity problem,”Journal of Optimization Theory and Applications 8 (1971) 161–168. · doi:10.1007/BF00932464 |
| [26] | S. Karamardian, ”An existence theorem for the complementarity problem,”Journal of Optimization Theory and Applications 18 (1976) 445–454. · Zbl 0304.49026 · doi:10.1007/BF00932654 |
| [27] | D. Kinderlehrer and G. Stampacchia,An introduction to variational inequalities and their applications (Academic Press, New York, 1980). · Zbl 0457.35001 |
| [28] | S. Lawphongpanich and D.W. Hearn, ”Simplicial decomposition of the asymmetric traffic assignment problem,”Transportation Research 18B (1984) 123–133. |
| [29] | P. Marcotte, ”A new algorithm for solving variational inequalities with application to the traffic assignment problem,”Mathematical Programming Study 33 (1985) 339–351. · doi:10.1007/BF01584381 |
| [30] | P. Marcotte, ”Gap-decreasing algorithms for monotone variational inequalities,” Conference paper, ORSA/TIMS Joint National Meeting, Miami Beach, FL, 1986. |
| [31] | P. Marcotte and J.-P. Dussault, ”A modified Newton method for solving variational inequalities,” in:Proceedings of the 24th IEEE Conference on Decision and Control (Fort Lauderdale, FL, 1985) pp. 1433–1436. |
| [32] | 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 · doi:10.1016/0167-6377(87)90007-1 |
| [33] | P. Marcotte and J.-P. Dussault, ”A sequential linear programming algorithm for solving monotone variational inequalities,”SIAM Journal on Control and Optimization 27 (1989) 1260–1278. · Zbl 0689.90069 · doi:10.1137/0327064 |
| [34] | P. Marcotte and J. Guélat, ”Adaptation of a modified Newton method for solving the asymmetric traffic equilibrium problem,”Transportation Science 22 (1988) 112–124. · Zbl 0648.90084 · doi:10.1287/trsc.22.2.112 |
| [35] | A. Migdalas, ”A regularization of the Frank–Wolfe algorithm,” Report LiTH-MAT-R-90-10, Linköping Institute of Technology (Linköping, Sweden, 1990) to appear inMathematical Programming. |
| [36] | G.J. Minty, ”Monotone (non-linear) operators in Hilbert space,”Duke Mathematical Journal 29 (1962) 341–346. · Zbl 0111.31202 · doi:10.1215/S0012-7094-62-02933-2 |
| [37] | S. Nguyen and C. Dupuis, ”An efficient method for computing traffic equilibria in networks with asymmetric transportation costs,”Transportation Science 18 (1984) 185–202. · doi:10.1287/trsc.18.2.185 |
| [38] | M.A. Noor, ”General algorithm for variational inequalities,”Journal of Optimization Theory and Applications 73 (1992) 409–413. · Zbl 0794.49009 · doi:10.1007/BF00940189 |
| [39] | J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, New York, 1970). · Zbl 0241.65046 |
| [40] | J.-S. Pang, ”Asymmetric variational inequality problems over product sets: applications and iterative methods,”Mathematical Programming 31 (1985) 206–219. · Zbl 0578.49006 · doi:10.1007/BF02591749 |
| [41] | J.-S. Pang, ”A posteriori error bounds for the linearly-constrained variational inequality problem,”Mathematics of Operations Research 12 (1987) 474–484. · doi:10.1287/moor.12.3.474 |
| [42] | M. Patriksson, ”Partial linearization methods in nonlinear programming,”Journal of Optimization Theory and Applications 78 (1993a) 227–246. · Zbl 0796.90058 · doi:10.1007/BF00939668 |
| [43] | M. Patriksson, ”A unified description of iterative algorithms for traffic equilibria,”European Journal of Operational Research 71 (1993b) 154–176. · Zbl 0802.90074 · doi:10.1016/0377-2217(93)90046-P |
| [44] | M. Patriksson, ”A unified framework of descent algorithms for nonlinear programs and variational inequalities,” Ph.D. thesis, Linköping University (Linköping, Sweden, 1993c). · Zbl 0802.90074 |
| [45] | M. Patriksson, ”A descent algorithm for a class of generalized variational inequalities,” Report LiTH-MAT-R-93-35, Linköping Institute of Technology (Linköping, Sweden, 1993d). · Zbl 0802.90074 |
| [46] | M.E. Primak, ”A computational process of search for equilibrium points,”Cybernetics 9 (1975) 106–113. · doi:10.1007/BF01068672 |
| [47] | R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970). · Zbl 0193.18401 |
| [48] | R.T. Rockafellar,The theory of subgradients and its applications to problems of optimization: Convex and nonconvex functions (Heldermann, Berlin, 1981). · Zbl 0462.90052 |
| [49] | M.J. Smith, ”The existence and calculation of traffic equilibria,”Transportation Research 17B (1983a) 291–303. |
| [50] | M.J. Smith, ”An algorithm for solving asymmetric equilibrium problems with a continuous cost-flow function,”Transportation Research 17B (1983b) 365–371. |
| [51] | K. Taji, M. Fukushima and T. Ibaraki, ”A globally convergent Newton method for solving strongly monotone variational inequalities,”Mathematical Programming 58 (1993) 369–383. · Zbl 0792.49007 · doi:10.1007/BF01581276 |
| [52] | P. Tseng, ”Decomposition algorithm for convex differentiable minimization,”Journal of Optimization Theory and Applications 70 (1991) 109–135. · Zbl 0739.90052 · doi:10.1007/BF00940507 |
| [53] | J.H. Wu, M. Florian and P. Marcotte, ”A general descent framework for the monotone variational inequality problem,” Publication 723, Centre de recherche sur les transports, Université de Montréal (Montréal, Canada, 1991) also inMathematical Programming 61 (1993) 281–300. |
| [54] | W.I. Zangwill,Nonlinear Programming: A Unified Approach (Prentice-Hall, Englewood Cliffs, NJ, 1969). |
| [55] | L. Zhao and S. Dafermos, ”General economic equilibrium and variational inequalities,”Operations Research Letters 10 (1991) 369–376. · Zbl 0743.90021 · doi:10.1016/0167-6377(91)90037-P |
| [56] | S.I. Zuhovickii, R.A. Poljak and M.E. Primak, ”Two methods of search for equilibrium points ofn-person concave games,”Soviet Mathematics Doklady 10 (1969a) 279–282. |
| [57] | S.I. Zuhovickii, R.A. Poljak and M.E. Primak, ”Numerical methods of finding equilibrium points ofn-person games,” in:Proceedings of the First Winter School of Mathematical Programming at Drogobych No. 1 (1969b) 93–130. |
| [58] | S.I. Zuhovickii, R.A. Poljak and M.E. Primak, ”On ann-person concave game and a production model,”Soviet Mathematics Doklady 11 (1970) 522–526. · Zbl 0213.46501 |
| [59] | S.I. Zuhovickii, R.A. Poljak and M.E. Primak, ”Concave multiperson games: numerical methods,”Matekon 9 (1973) 10–30. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
