Academic Journal of Computing & Information Science, 2019, 2(1); doi: 10.25236/AJCIS.010022.
Mingchuan Li
College of Mathematics and Information, China West Normal University, Nanchong 637002, Sichuan, China
[email protected]
In this paper, we propose a modified Forward-Backward splitting method for finding a zero of the sum of two operators. A classical modification of Forward-Backward method was proposed by Tseng, which is known to converge when the forward and the backward operators are monotone and with Lipschitz continuity of the backward operator. The algorithm proposed here improves Tseng’s method in some instances. The first and main part of our approach, contains an explicit Armijo-type search in the spirit of the extragradient-like methods for variational inequalities. During the iteration process the search performs only one calculation of the forward-backward operator, in each tentative of the step. This achieves a considerable computational saving when the forward-backward operator is computationally expensive. The second part of the scheme consists in special projection steps. The convergence analysis of the proposed scheme is given assuming monotonicity on both operators, without Lipschitz continuity assumption on the backward operator.
Armijo-type search, Projection method, Half-space, Maximal monotone operators
Mingchuan Li, A Half-space Projection Method for Solving Sum of Two Maximal Monotone Operators. Academic Journal of Computing & Information Science (2019) Vol. 2: 92-101. https://doi.org/10.25236/AJCIS.010022.
[1] Bauschke, H. H., Burke, J. V., Deutsch, F. R., Hundal, H. S.: A new proximal point iter- ation that converges weakly but not in norm. Proceedings of the American Mathematical Society.133, 1829-1835 (2005)
[2] Bello Cruz, J.Y., Iusem, A.N.: A strongly convergent direct method for monotone varia- tional inequalities in Hilbert spaces. Numerical Functional Analysis and Optimization.30, 23-36 (2009)
[3] Eckstein, J.Splitting Methods for Monotone Operators, with Applications to Parallel Op- timization. PhD thesis, Massachusetts Institute of Techonology, Cambridge, MA, 1989. Report LIDS-TH-1877, Laboratory for Information and Decision Systems, M.I.T.
[4] Eckstein, J., Svaiter, B.F.: A family of projective splitting methods for the sum of two maximal monotone operators. Mathematical Programming. 111, 173-199 (2008)
[5] Facchinei, F., Pang, J.S.: Finite-dimensional Variational Inequalities and Complementar- ity Problems. Springer, Berlin. (2003)
[6] Bauschke, H.H.,Borwein, J.M. : On projection algorithms for solving convex feasibility problems. SIAM Review. 38, 367-426 (1996)
[7] Hartman, P., Stampacchia, G.: On some non-linear elliptic dierential-functional equations. Acta Ma-thematica. 115, 271-310 (1966)
[8] Iusem, A.N., Svaiter, B.F.: Entropy-like proximal methods in convex programming. Math- ematics of Operations Research .19,790-814 (1994).
[9] Minty, G.: On the maximal domain of a monotone function. Michigan Mathematical Journal. 8, 135-137 (1961)
[10] Minty, G.: Monotone (nonlinear) operators in Hilbert Space. Duke Mathetematical Journal. 29, 341-346 (1962)
[11] Kinderlehrer, D., Stampacchia, G.: An Introduction to Variational Inequalities and Their Applications. Academic Press, New York. (1980)
[12] Solodov, M.V., Svaiter, B.F.: A new projection method for variational inequality problems. SIAM Journal on Control and Optimization. 37, 765-776 (1999)
[13] Tseng, P.: A modified forward-backward splitting method for maximal monotone map-pings. SIAM on Journal Control Optimization. 38, 431-446 (2000).
[14] Lions, P.L., Mercier, B. : Splitting algorithms for the sum of two nonlinear operators. SIAM of Journal Numerical Analysis. 16, 964-979 (1979)
[15] Passty, G.B.: Ergodic convergence to a zero of the sum of monotone operators in Hilbert space. Journal of the Mathematical Analysis and Applications. 72, 383–390 (1979).
[16] Li, F.L., He, Y.R.: An algorithm for generalized variational inequality with pseudomono- tone mapping. J. Comput. Appl. Math. 228, 212–218 (2009)
[17] Browder, F.E.: Convergence theorems for sequences of nonlinear operators in Banach spaces. Mathema-tische Zeitschrift.100, 201–225 (1967)
[18] Zarantonello, E.H.: Projections on Convex Sets in Hilbert Space and Spectral Theory, Contributions to Nonlinear Functional Analysis. Academic Press, New York, NY, (1971)
[19] Bello Cruz, J.Y., Iusem, A.N.: Convergence of direct methods for paramonotone variational inequalities. Computation Optimization and Applications. 46, 247–263 (2010)
[20] Burachik, R.S., Iusem, A.N.: Set-Valued Mappings and Enlargements of Monotone Oper- ators. Springer, Berlin (2008)
[21] Bauschke HH.,Combettes PL.: Convex analysis and monotone operator theory in Hilbert spaces. New York (NY):Springer. (2011).