A continuation method for (strongly) monotone variational inequalities. (English) Zbl 0920.90131
Summary: We consider the variational inequality problem, denoted by \(\text{VIP}(X, F)\), where \(F\) is a strongly monotone function and the convex set \(X\) is described by some inequality (and possibly equality) constraints. This problem is solved by a continuation (or interior-point) method, which solves a sequence of certain perturbed variational inequality problems. These perturbed problems depend on a parameter \(\mu>0\). It is shown that the perturbed problems have a unique solution for all values of \(\mu> 0\), and that any sequence generated by the continuation method converges to the unique solution of \(\text{VIP}(X,F)\) under a well-known linear independence constraint qualification (LICQ). We also discuss the extension of the continuation method to monotone variational inequalities and present some numerical results obtained with a suitable implementation of this method.
Keywords:
strongly monotone functions; interior-point method; variational inequality; continuation methodReferences:
| [1] | B. Chen, P.T. Harker, A noninterior continuation method for quadratic and linear programming, SIAM Journal on Optimization 3 (1993) 503–515. · Zbl 0795.90040 · doi:10.1137/0803024 |
| [2] | B. Chen, P.T. Harker, A non-interior-point continuation method for linear complementarity problems, SIAM Journal on Matrix Analysis and Applications 14 (1993) 1168–1190. · Zbl 0788.65073 · doi:10.1137/0614081 |
| [3] | B. Chen, P.T. Harker, A continuation method for monotone variational inequalities, Mathematical Programming 69 (1995) 237–253. · Zbl 0844.90093 · doi:10.1007/BF01585559 |
| [4] | F.H. Clarke, Optimization and Nonsmooth Analysis, Wiley, New York, 1983 (reprinted by SIAM, Philadelphia, PA, 1990). · Zbl 0582.49001 |
| [5] | S.P. Dirkse, M.C. Ferris, The PATH solver: A nonmonotone stabilization scheme for mixed complementarity problems, Optimization Methods and Software 5 (1995) 123–156. · doi:10.1080/10556789508805606 |
| [6] | S.P. Dirkse, M.C. Ferris, MCPLIB: A collection of nonlinear mixed complementarity problems, Optimization Methods and Software 5 (1995) 319–345. · doi:10.1080/10556789508805619 |
| [7] | F. Facchinei, H. Jiang, L. Qi, A smoothing method for mathematical programs with equilibrium constraints, Technical Report, School of Mathematics, Department of Applied Mathematics, University of New South Wales, Sydney, Australia (1996). · Zbl 0959.65079 |
| [8] | A.V. Fiacco, G.P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques, Wiley, New York, 1969 (reprinted by SIAM, Philadelphia, PA, 1990). · Zbl 0218.90045 |
| [9] | A. Fischer, C. Kanzow, On finite termination of an iterative method for linear complementarity problems, Mathematical Programming 74 (1996) 279–292. · Zbl 0855.90125 |
| [10] | M. Fukushima, A relaxed projection method for variational inequalities, Mathematical Programming 35 (1986) 58–70. · Zbl 0598.49024 · doi:10.1007/BF01589441 |
| [11] | 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 |
| [12] | M. Fukushima, Z.-Q. Luo, J.-S. Pang, A globally convergent sequential quadratic programming algorithm for mathematical programs with linear complementarity constraints (to appear in Computational Optimization and Applications). · Zbl 0904.90153 |
| [13] | P.T. Harker, Accelerating the convergence of the diagonalization and projection algorithms for finitedimensional variational inequalities, Mathematical Programming 41 (1988) 29–59. · Zbl 0825.49019 · doi:10.1007/BF01580752 |
| [14] | P.T. Harker, Lectures on Computation of Equilibria with Equation-Based Methods, CORE Lecture Series, CORE Foundation, Université Catholique de Louvain, Louvain-la-Neuve, Belgium, 1993. |
| [15] | P.T. Harker, 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 |
| [16] | W. Hock, K. Schittkowski, Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems, vol. 187, Springer, Berlin, 1981. · Zbl 0452.90038 |
| [17] | C. Kanzow, Some noninterior continuation methods for linear complementarity problems, SIAM Journal on Matrix Analysis and Applications 17 (1996) 851–868. · Zbl 0868.90123 · doi:10.1137/S0895479894273134 |
| [18] | M. Kojima, S. Mizuno, T. Noma, A new continuation method for complementarity problems with uniformP-functions, Mathematical Programming 43 (1989) 107–113. · Zbl 0673.90084 · doi:10.1007/BF01582283 |
| [19] | M. Kojima, S. Mizuno, T. Noma, Limiting behavior of trajectories generated by a continuation method for monotone complementarity problems, Mathematics of Operations Research 15 (1990) 662–675. · Zbl 0719.90085 · doi:10.1287/moor.15.4.662 |
| [20] | T. Larsson, M. Patriksson, A class of gap functions for variational inequalities, Mathematical Programming 64 (1994) 53–79. · Zbl 0819.65101 · doi:10.1007/BF01582565 |
| [21] | P. Marcotte, 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 |
| [22] | J.M. Martínez, Algorithms for solving nonlinear systems of equations, in: E. Spedicato (Ed.), Algorithms for Continuous Optimization. The State of the Art, Kluwer Academic Publishers, Dordrecht, 1994. |
| [23] | L. Mathiesen, An algorithm based on a sequence of linear complementarity problems applied to a Walrasian equilibrium model: An example, Mathematical Programming 37 (1987) 1–18. · Zbl 0613.90098 · doi:10.1007/BF02591680 |
| [24] | Y. Nesterov, A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming, in: SIAM Studies in Applied Mathematics, vol. 13, SIAM, Philadelphia, PA, 1994. · Zbl 0824.90112 |
| [25] | J.-S. Pang, Newton’s method for B-differentiable equations, Mathematics of Operations Research 15 (1990) 311–341. · Zbl 0716.90090 · doi:10.1287/moor.15.2.311 |
| [26] | J.-S. Pang, A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems, Mathematical Programming 51 (1991) 101–131. · Zbl 0733.90063 · doi:10.1007/BF01586928 |
| [27] | K. Taji, M. Fukushima, A new merit function and a successive quadratic programming algorithm for variational inequality problems, SIAM Journal on Optimization 6 (1996) 704–713. · Zbl 0853.49011 · doi:10.1137/S1052623494271199 |
| [28] | K. Taji, M. Fukushima, 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 |
| [29] | R.L. Tobin, Variable dimension spatial price equilibrium algorithm, Mathematical Programming 40 (1988) 33–51. · Zbl 0645.90095 · doi:10.1007/BF01580722 |
| [30] | P. Tseng, Global linear convergence of a path-following algorithm for some variational inequality problems, Journal of Optimization Theory and Applications 75 (1992) 265–279. · Zbl 0795.49008 · doi:10.1007/BF00941467 |
| [31] | Z. Wang, Continuation methods for solving the variational inequality and complementarity problems, Ph.D. Thesis, The Johns Hopkins University, Baltimore, Maryland, USA (1990). |
| [32] | L.T. Watson, Solving the nonlinear complementarity problem by a homotopy method, SIAM Journal on Control and Optimization 17 (1979) 36–46. · Zbl 0407.90083 · doi:10.1137/0317004 |
| [33] | M.H. Wright, Interior methods for constrained optimization, in: A. Iserles (Ed.), Acta Numerica 1992, Cambridge Univ. Press, New York, 1992, 341–407. · Zbl 0766.65053 |
| [34] | S.J. Wright, A path-following interior-point algorithm for linear and quadratic problems, Preprint MCS-P401-1293, Mathematics and Computer Science Department, Argonne National Laboratory, Argonne, IL, USA (1993). |
| [35] | J.H. Wu, M. Florian, P. Marcotte, A general descent framework for the monotone variational inequality problem, Mathematical Programming 61 (1993) 281–300. · Zbl 0813.90111 · doi:10.1007/BF01582152 |
| [36] | B. Xiao, P.T. Harker, A nonsmooth Newton method for variational inequalities. I: Theory, Mathematical Programming 65 (1994) 151–194. · Zbl 0812.65048 · doi:10.1007/BF01581695 |
| [37] | B. Xiao, P.T. Harker, A nonsmooth Newton method for variational inequalities. II: Numerical results, Mathematical Programming 65 (1994) 195–216. · Zbl 0812.65049 · doi:10.1007/BF01581696 |
| [38] | D.L. Zhu, P. Marcotte, Modified descent methods for solving the monotone variational inequality problem, Operations Research Letters 14 (1993) 111–120. · Zbl 0795.49011 · doi:10.1016/0167-6377(93)90103-N |
| [39] | D.L. Zhu, P. Marcotte, An extended descent framework for variational inequalities, Journal of Optimization Theory and Applications 80 (1994) 349–366. · Zbl 0798.49014 · doi:10.1007/BF02192941 |
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.
