Abstract
We introduce a relaxed-projection splitting algorithm for solving variational inequalities in Hilbert spaces for the sum of nonsmooth maximal monotone operators, where the feasible set is defined by a nonlinear and nonsmooth continuous convex function inequality. In our scheme, the orthogonal projections onto the feasible set are replaced by projections onto separating hyperplanes. Furthermore, each iteration of the proposed method consists of simple subgradient-like steps, which does not demand the solution of a nontrivial subproblem, using only individual operators, which exploits the structure of the problem. Assuming monotonicity of the individual operators and the existence of solutions, we prove that the generated sequence converges weakly to a solution.
Similar content being viewed by others
References
Alber, YaI, Iusem, A.N., Solodov, M.V.: On the projected subgradient method for nonsmooth convex optimization in a Hilbert space. Math. Program. 81, 23–37 (1998)
Attouch, H., Czarnecki, M.-O., Peypouquet, J.: Coupling forward–backward with penalty schemes and parallel splitting for constrained variational inequalities. SIAM J. Optim. 21, 1251–1274 (2011)
Bao, T.Q., Khanh, P.Q.: A projection-type algorithm for pseudomonotone nonlipschitzian multivalued variational inequalities. Nonconvex Opt. Appl. 77, 113–129 (2005)
Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011)
Bello Cruz, J.Y., Díaz Millán, R.: A direct splitting method for nonsmooth variational inequalities. J. Optim. Theory Appl. 161, 728–737 (2014)
Bello Cruz, J.Y., de Oliveira, W.: Level bundle-like algorithms for convex optimization. J. Global Optim. 59, 787–809 (2014)
Bello Cruz, J.Y., Iusem, A.N.: An explicit algorithm for monotone variational inequalities. Optimization 61, 855–871 (2012)
Bello Cruz, J.Y., Iusem, A.N.: A strongly convergent method for nonsmooth convex minimization in Hilbert spaces. Numer. Funct. Anal. Opt. 32, 1009–1018 (2011)
Bello Cruz, J.Y., Iusem, A.N.: Full convergence of an approximate projection method for nonsmooth variational inequalities. Math. Comput. Simul. 114, 2–13 (2015)
Bello Cruz, J.Y., Iusem, A.N.: Convergence of direct methods for paramonotone variational inequalities. Comput. Opt. Appl. 46, 247–263 (2010)
Bello Cruz, J.Y., Iusem, A.N.: A strongly convergent direct method for monotone variational inequalities in Hilbert spaces. Numer. Funct. Anal. Opt. 30, 23–36 (2009)
Boţ, R.I., Hendrich, C.: A Douglas-Rachford type primal-dual method for solving inclusions with mixtures of composite and parallel-sum type monotone operators. SIAM J. Optim. 23, 2541–2565 (2013)
Bruck, R.E.: On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert space. J. Math. Anal. Appl. 61, 159–164 (1977)
Burachik, R.S., Iusem, A.N.: Set-Valued Mappings and Enlargements of Monotone Operators. Springer, Berlin (2008)
Burachik, R.S., Lopes, J.O., Svaiter, B.F.: An outer approximation method for the variational inequality problem. SIAM J. Control Opt. 43, 2071–2088 (2005)
Censor, Y., Gibali, A., Reich, S.: The subgradient extragradient method for solving variational inequalities in Hilbert space. J. Optim. Theory Appl. 148, 318–335 (2011)
Combettes, P.L.: Quasi-Fejérian analysis of some optimization algorithms. In: Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications. Studies in Computational Mathematics 8, North-Holland, Amsterdam, pp. 115–152 (2001)
Combettes, P.L., Pesquet, J.-C.: Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators. Set-Valued Var. Anal. 20, 307–330 (2012)
Eckstein, J., Svaiter, B.F.: General projective splitting methods for sums of maximal monotone operators. SIAM J. Control Opt. 48, 787–811 (2009)
Ermoliev, YuM: On the method of generalized stochastic gradients and quasi-Fejér sequences. Cybernetics 5, 208–220 (1969)
Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, Berlin (2003)
Fang, S.C., Petersen, E.L.: Generalized variational inequalities. J. Optim. Theory Appl. 38, 363–383 (1982)
Fukushima, M.: A Relaxed projection for variational inequalities. Math. Program. 35, 58–70 (1986)
Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2, 17–40 (1976)
He, B.S.: A new method for a class of variational inequalities. Math. Program. 66, 137–144 (1994)
Iusem, A.N., Lucambio Pérez, L.R.: An extragradient-type method for non-smooth variational inequalities. Optimization 48, 309–332 (2000)
Iusem, A.N., Svaiter, B.F.: A variant of Korpelevich’s method for variational inequalities with a new search strategy. Optimization 42, 309–321 (1997) (Addendum Optimization 43, 85 (1998))
Iusem, A.N., Svaiter, B.F., Teboulle, M.: Entropy-like proximal methods in convex programming. Math. Oper. Res. 19, 790–814 (1994)
Kinderlehrer, D., Stampacchia, G.: An Introduction to Variational Inequalities and Their Applications. Academic Press, New York (1980)
Konnov, I.V.: A combined relaxation method for variational inequalities with nonlinear constraints. Math. Program. 80, 239–252 (1998)
Konnov, I.V.: Combined Relaxation Methods for Variational Inequalities. Springer, Berlin (2001)
Korpelevich, G.M.: The extragradient method for finding saddle points and other problems. Ekonomika I Matematcheskie Metody 12, 747–756 (1976)
Lewis, A.S., Pang, J.-S.: Error Bounds for Convex Inequality Systems. Generalized Convexity, Generalized Monotonicity: Recent Results: Nonconvex Optimization and Its Applications, Vol. 27, pp. 75–110. Kluwer Academic Publications, Dordrecht (1998)
Lions, P.L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16, 964–979 (1979)
Moudafi, A.: On the convergence of splitting proximal methods for equilibrium problems in Hilbert spaces. J. Math. Anal. Appl. 359, 508–513 (2009)
Nedic, A., Bertsekas, D.: Incremental subgradient methods for nondifferentiable optimization. SIAM J. Optim. 12, 109–138 (2001)
Nesterov, Yu.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, Norwel (2004)
Nesterov, Yu.: A method of solving a convex programming problem with convergence rate O(\(1/k^2\)). Soviet Math. Doklady 27, 372–376 (1983)
Passty, G.B.: Ergodic convergence to a zero of the sum of monotone operators in Hilbert space. J. Math. Anal. Appl. 72, 383–390 (1979)
Polyak, B.T.: Minimization of unsmooth functionals. USSR Comput. Math. Math. Phys. 9, 14–29 (1969)
Rockafellar, R.T.: On the maximality of sums of nonlinear monotone operators. Trans. Am. Math. Soc. 149, 75–88 (1970)
Rockafellar, R.T.: On the maximal monotonicity of subdifferential mapping. Pac. J. Math. 33, 209–216 (1970)
Sien, D.: Computable error bounds for convex inequality systems in reflexive Banach spaces. SIAM J. Optim. 1, 274–279 (1997)
Shih, M.H., Tan, K.K.: Browder–Hartmann–Stampacchia variational inequalities for multi-valued monotone operators. J. Math. Anal. Appl. 134, 431–440 (1988)
Solodov, M.V., Svaiter, B.F.: A new projection method for monotone variational inequality problems. SIAM J. Control Opt. 37, 765–776 (1999)
Solodov, M.V., Tseng, P.: Modified projection-type methods for monotone variational inequalities. SIAM J. Control Opt. 34, 1814–1830 (1996)
Todd, M.J.: The Computations of Fixed Points and Applications. Springer, Berlin (1976)
Tseng, P.: A modified forward–backward splitting method for maximal monotone mappings. SIAM J. Control Opt. 38, 431–446 (2000)
Zarantonello, E.H.: Projections on convex sets in Hilbert space and spectral theory. In: Zarantonello, E. (ed.) Contributions to Nonlinear Functional Analysis, pp. 237–424. Academic Press, New York (1971)
Zhang, H., Cheng, L.: Projective splitting methods for sums of maximal monotone operators with applications. J. Math. Anal. Appl. 406, 323–334 (2013)
Acknowledgments
JYBC and RDM were partially supported by project CAPES-MES-CUBA 226/2012. JYBC was partially supported by CNPq grants 303492/2013-9, 474160/2013-0 and 202677/2013-3 and by project UNIVERSAL FAPEG/CNPq. RDM was supported by his scholarship for his doctoral studies, granted by CAPES. This work was completed while the first author was visiting the University of British Columbia. The author is very grateful for the warm hospitality. The authors would like to thank to Professor Dr. Heinz H. Bauschke, Professor Dr. Ole Peter Smith and anonymous referees whose suggestions helped us to improve the presentation of this paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Cruz, J.Y.B., Millán, R.D. A relaxed-projection splitting algorithm for variational inequalities in Hilbert spaces. J Glob Optim 65, 597–614 (2016). https://doi.org/10.1007/s10898-015-0397-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-015-0397-x
Keywords
- Point-to-set operator
- Projection methods
- Relaxed method
- Splitting methods
- Variational inequality problem
- Weak convergence