Abstract
In this paper, we establish sufficient conditions for guaranteeing finite termination of an arbitrary algorithm for solving a variational inequality problem in a Banach space. Applying these conditions, it shows that sequences generated by the proximal point algorithm terminate at solutions in a finite number of iterations.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alber, Y.I.: Metric and generalized projection operators in Banach spaces:properties and applications. In: Kartsatos, A.G. (ed.) Theory and Applications of Nonlinear Operators of Accretive and Monotone Type Lecture Notes in Pure and Appl. Math., vol. 178, pp. 15–50. Marcel Dekker, New York (1996)
Aubin, J.-P., Ekeland, I.: Applied Nonlinear Analysis. Pure and Applied Mathematics. Wiley, New York (1984)
Barbu, V., Precupanu, T.: Convexity and Optimization in Banach Spaces, 2nd edn. Reidel, Dordrecht (1986)
Bauschke, H.H., Burke, J.V., Deutsch, F.R., Hundal, H.S., Vanderwerff, J.D.: A new proximal point iteration that converges weakly but not in norm. Proc. Am. Math. Soc. 133, 1829–1835 (2005)
Brézis, H., Lions, P.-L.: Produits infinis de résolvantes. Israel J. Math. 29, 329–345 (1978)
Burachik, R.S., Iusem, A.N.: Set-valued Mappings and Enlargements of Monotone Operators. Springer Optim. Appl., Springer, New York (2008)
Burachik, R.S., Scheimberg, S.: A proximal point method for the variational inequality problem in Banach spaces. SIAM J. Control Optim. 39, 1633–1649 (2001)
Burke, J.V., Deng, S.: Weak sharp minima revisited, part I: basic theory. Control Cybern. 31, 439–469 (2002)
Burke, J.V., Ferris, M.C.: Weak sharp minima in mathematical programming. SIAM J. Control Optim. 31, 1340–1359 (1993)
Butnariu, D., Iusem, A.I., Zălinescu, C.: On uniformly convexity, total convexity and convergence of the proximal point and outer Bregman projection algorithms in Banach spaces. J. Convex Anal. 10, 35–61 (2003)
Calamai, P.H., Moré, J.J.: Projected gradient methods for linearly constrained problems. Math. Program. 39, 93–116 (1987)
Censor, Y., Iusem, A.N., Zenios, S.A.: An interior point method with Bregman functions for the variational inequality problem with paramonotone operators. Math. Program. 31, 373–400 (1998)
Cioranescu, I.: Geometry of Banach spaces, Duality Mapping and Nonlinear Problems. Kluwer Academic Publishers, Amsterdam (1990)
Daniilidis, A., Hadjisavvas, N.: Coercivity conditions and variational inequalities. Math. Program. 86, 433–438 (1999)
Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems I. Springer, New York (2003)
Ferris, M.C.: Finite termination of the proximal point algorithm. Math. Program. 50, 359–366 (1991)
Güler, O.: On the convergence of the proximal point algorithm for convex minimization. SIAM J. Control Optim. 29, 403–419 (1991)
Hu, Y.H., Song, W.: Weak sharp solutions for variational inequalities in Banach spaces. J. Math. Anal. Appl. 374, 118–132 (2011)
Kamimura, S., Kohsaka, F., Takahashi, W.: Weak and strong convergence theorems for maximal monotone operators in a Banach space. Set-Valued Anal. 12, 417–429 (2004)
Kamimura, S., Takahashi, W.: Strong convergence of a proximal-type algorithm in a Banach space. SIAM J. Optim. 13, 938–945 (2002)
Kassay, G.: The proximal point algorithm for reflexive Banach spaces. Stud. Univ. Babeş-Bolyai Math. 30, 9–17 (1985)
Kinderlehrer, D., Stampacchia, G.: An Introduction to Variational Inequalities and Their Applications. Academic, New York (1980)
Kohsaka, F., Takahashi, W.: Strong convergence of an iterative sequence for maximal monotone operators in a Banach space. Abstr. Appl. Anal. 2004, 239–249 (2004)
Luque, F.J.: Asymptotic convergence analysis of the proximal point algorithm. SIAM J. Control Optim. 22, 277–293 (1984)
Mangasarian, O.L.: Error bounds for nondegenerate monotone linear complementarity problems. Math. Program. 48, 437–445 (1990)
Marcotte, P., Zhu, D.L.: Weak sharp solutions of variational inequalities. SIAM J. Optim. 9, 179–189 (1999)
Martinet, B.: Régularisation d’inéquations variationnelles par approximations successives. Rev. Fr. Inform. Rech. Opér. 4, 154–158 (1970)
Matsushita, S., Takahashi, W.: Weak and strong convergence theorems for relatively nonexpansive mappings in Banach spaces. Fixed Point Theory Appl. 2004, 37–47 (2004)
Matsushita, S., Takahashi, W.: A strong convergence theorem for relatively nonexpansive mappings in a Banach space. J. Approx. Theory 134, 257–266 (2005)
Patriksson, M.: Unified framework of descent algorithms for nonlinear programs and variational inequalities. Ph.D. Thesis, Linköping Institute of Technology (1993)
Reich, S.: Constructive techniques for accretive and monotone operators. In: Lakshmikantham, V. (ed.) Applied Nonlinear Analysis, pp. 335–345. Academic Press, New York (1979)
Rockafellar, R.T.: On the maximality of sums of nonlinear monotone operators. Trans. Am. Math. Soc. 149, 75–88 (1970)
Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877–898 (1976)
Takahashi, W.: Nonlinear Functional Analysis. Yokohama Publishers, Yokohama (2000)
Takahashi, W.: Convex Analysis and Approximation of Fixed Points. Yokahama Publishers, Yokahama, (2000) (Japanese)
Wu, Z.L., Wu, S.Y.: Weak sharp solutions of variational inequalities in Hilbert spaces. SIAM J. Optim. 14, 1011–1027 (2004)
Xiu, N., Zhang, J.: On finite convergence of proximal point algorithms for variational inequalities. J. Math. Anal. Appl. 312, 148–158 (2005)
Zălinescu, C.: Convex Analysis in General Vector Spaces. World Scientific, Singapore (2002)
Zhou, J., Wang, C.: A note on finite termination of iterative algorithms in mathematical programming. Oper. Res. Lett. 36, 715–717 (2008)
Author information
Authors and Affiliations
Corresponding author
Additional information
The first author was partially supported by Grant-in-Aid for Young Scientists (B) No. 20740084, the Ministry of Education, Culture, Sports, Science and Technology, Japan.
Rights and permissions
About this article
Cite this article
Matsushita, Sy., Xu, L. Finite Convergence of the Proximal Point Algorithm for Variational Inequality Problems. Set-Valued Var. Anal 21, 297–309 (2013). https://doi.org/10.1007/s11228-012-0225-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11228-012-0225-0
Keywords
- Variational inequality problem
- Weak sharp minima
- Finite termination
- Proximal point algorithm
- Banach space
- Metric projection
- Generalized projection