Abstract
We study the Clarke–Rockafellar directional derivatives of the regularized gap functions (and of some modified ones) for the variational inequality problem (VIP) defined by a locally Lipschitz but not necessarily differentiable function on a closed convex set in an Euclidean space. As applications we show that, under the strong monotonicity assumption, the regularized gap functions have fractional exponent error bounds and consequently that the sequences provided by an algorithm of Armijo type converge to the solution of the (VIP).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Clarke F.H. (1983) Optimization and Nonsmooth Analysis. Wiley, New York
Cottle R.W. (1966) Nolinear programs with positively bounded Jacobians. SIAM J. Appl. Math. 14, 147–158
Facchinei F., Pang J.S. (2003) Finte-Dimensional Variational Inequalities and Complementarity Problems. Springer, Berlin Helidelberg New York
Fadell A.G. (1973) A generalization of Rademacher’s theorem on complete differential. Colloq. Math. 27, 126–131
Fukushima M. (1992) Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Math. Program. 53, 99–110
Harker P.T., Pang J.S. (1990) Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications. Math. Program. 48, 161–220
Harrington J.E., Hobbs B.F., Pang J.S., Liu A., Roch G.(2005) Collusive game solutions via optimization. Math. Program. 104, 407–435
Huang L.R., Ng K.F. (2005) Equivalent Optimization Formulations and Error Bounds for Variational Inequality Problems. J. Optim. Theory Appl. 125, 299–314
Jiang H., Qi L. (1995) Local uniqueness and convergence of iterative methods for nonsmooth variational inequalities. J. Math. Anal. Appl. 196, 314–331
King A.J., Rockafellar R.T. (1992) Sensitivity analysis for nonsmooth generalized equations. Math. Program. 55, 193–202
Kyparisis J. (1986) Uniqueness and differentiability of solutions of parametric nonlinear complementarity problems. Math. Program. 36, 105–113
Luc D.T. (2001) Existence results for densely pseudomonotone variational inequalities. J. Math. Anal. Appl. 254, 291–308
Luc D.T. (2002) The Frechet approximate jacobian and local uniqueness in variational inequalities. J. Math. Anal. Appl. 268, 629–646
Mordukhovich B.S. (1994) Stability theory for parametric generalized equations and variational inequalities via nonsmooth analysis. Trans. Am. Math. Soc. 343, 609–658
Ng K.F., Zheng X.Y. (2001) Error bound for lower semicontinuous functions in normed space. SIAM J. Optim. 12, 1–17
Pang J.S. (1994) Complementarity problems. In: Horst R., Pardalos P. (eds) Handbook on Global Optimization. Kluwer, Boston
Pang J.S., Fukushima M. (2005) Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games. Comput. Manag. Sci. 1, 21–56
Robinson S.M. (1983) Generalized equations. In: Bachem A., Grötschel M., Korte B. (eds) Mathematical Programming: The State of the Art. Springer, Berlin Helidelberg, New York, pp 346–367
Rockafellar R.T (1979) Directionally Lipschitzian functions and subdifferential calculus. Proc. Lond Math. Soc. 39, 331–355
Rockafellar R.T (1980) Generalized directional derivatives and subgradients of nonconvex functions. Can. J. Math. 32, 257–280
Rockafellar R.T., Wets R.J-B. (1998) Variational Analysis. Springer, Berlin Helidelberg, New York
Solodov M.V., Tseng P. (1996) Modified projection-type methods for monotone variational inequalities. SIAM J. Control Optim. 34, 1814–1830
Solodov M.V., Svaiter B.F.(1999) A new projection method for variational inequlity problems. SIAM J. Control Optim. 37, 765–776
Stampacchia G. (1964) Formes bilinaires coercitives sur les ensembles convexes. C. R. Acad. Sci. Paris 258, 4413–4416
Ward D.E., Borwein J.M. (1987) Nonsmooth calculus in finite dimensions. SIAM J. Control Optim. 25, 1312–1340
Wu J.H., Florian M., Marcotte P. (1993) A general descent framework for the monotone variational inequality problem. Math. Program. 61, 281–300
Yamashita N., Taji K., Fukushima M. (1997) Unconstrained optimization reformulations of variational inequality problems. J. Optim. Theory Appl. 92, 439–456
Zagrodny D. (1988) Approximate mean value theorem for upper subderivatives. Nonlinear Anal. 12, 1413–1428
Zalinescu C. (2002) Convex Analysis in General Vector Spaces. World Scientific, Singapore
Author information
Authors and Affiliations
Corresponding author
Additional information
The research of this author was supported by an Earmarked Grant from the Research Council of Hong Kong.
Rights and permissions
About this article
Cite this article
Ng, K.F., Tan, L.L. Error Bounds of Regularized Gap Functions for Nonsmooth Variational Inequality Problems. Math. Program. 110, 405–429 (2007). https://doi.org/10.1007/s10107-006-0007-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-006-0007-2