American Institute of Mathematical Sciences

Advanced
2013, 3(2): 295-307. doi: 10.3934/naco.2013.3.295

A modification of the forward-backward splitting method for maximal monotone mappings

Xiao Ding 1, and  Deren Han 1,

1. 

School of Mathematical Sciences, Jiangsu Key Labratory for NSLSCS, Nanjing Normal University, Nanjing, 210023, China, China

Received  May 2012 Revised  January 2013 Published  April 2013

In this paper, we propose a modification of the forward-backward splitting method for maximal monotone mappings, where we adopt a new step-size scheme in generating the next iterate. This modification is motivated by the ingenious rule proposed by He and Liao in modified Korpelevich's extra-gradient method [13]. Under suitable conditions, we prove the global convergence of the new algorithm. We apply our method to solve some monotone variational inequalities and report its numerical results. Comparisons with modified Khobotov-Korpelevich's extragradient method [13,14] and Tseng's method [30] show the significance of our work.
Keywords: co-coercive, variational inequality, Forward-backward splitting method, maximal monotone, projection..
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C3.
Citation: Xiao Ding, Deren Han. A modification of the forward-backward splitting method for maximal monotone mappings. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 295-307. doi: 10.3934/naco.2013.3.295
References:
[1]

D. P. Bertsekas, "Constrained Optimization and Lagarange Multiplier Method," Academic Press, New York, 1982.  Google Scholar

[2]

H. G. Chen, "Forward-Backward Splitting Techniques: Theory and Applications," Ph.D. Thesis, Department of Applied Mathematics, University of Washington, Seattle, WA, 1994. Google Scholar

[3]

H. G. Chen and R. T. Rockafellar, Convergence rates in forward-backward splitting, SIAM Journal on Control and Optimization, 7 (1997), 421-444. doi: 10.1137/S1052623495290179.  Google Scholar

[4]

J. Eckstein, Approximate iterations in Bregman-function-based proximal algorithms, Mathematical Programming, 83 (1998), 113-123. doi: 10.1007/BF02680553.  Google Scholar

[5]

J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Mathematical Programming, 55 (1992), 293-318. doi: 10.1007/BF01581204.  Google Scholar

[6]

J. Eckstein and M. C. Ferris, Operator splitting methods for monotone affine variational inequalities, with a parallel application to optimal control, INFORMS Journal on Computing, 10 (1998), 218-235.  Google Scholar

[7]

J. Eckstein and M. Fukushima, Some reformulations and applications of the alternating direction method of multipliers, in "Large Scale Optimization: State of the Art", (eds. W. W. Hager, D. W. Hearn and P. M. Pardalos), Kluwer Academic Publishers, Dordrecht, The Netherlands, (1994), 115-134. doi: 10.1007/978-1-4613-3632-7_7.  Google Scholar

[8]

F. Facchinei and J. S. Pang, "Finite-Dimensional Variatiaonal Inequalities and Complementarity Problems," Spring-Verlag, New York, 2003. Google Scholar

[9]

D. Gabay, Applications of the method of multipliers to variational inequalities, in "Augemented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems" (eds. M. Fortin and R. Glowinski), North Holland, Amsterdam, (1983), 299-331. doi: 10.1016/S0168-2024(08)70034-1.  Google Scholar

[10]

A. A. Goldstein, Convex programming in Hilbert space, Bulletin of the American Mathematical Society, 70 (1964), 709-710. doi: 10.1090/S0002-9904-1964-11178-2.  Google Scholar

[11]

O. Güler, On the convergence of the proximal point algorithm for convex minimization, SIAM Journal on Control and Optimization, 29 (1991), 403-419. doi: 10.1137/0329022.  Google Scholar

[12]

B. S. He, A logarithmic-quadratic proximal prediction-correction method for structured monotone variational inequalities, Computational Optimization and Applications, 35 (2006), 19-46. doi: 10.1007/s10589-006-6442-4.  Google Scholar

[13]

B. S. He and L. Z. Liao, Improvements of some projection methods for monotone nonlinear variational inequalities, Journal of Optimization Theory and Applications, 112 (2002), 111-128. doi: 10.1023/A:1013096613105.  Google Scholar

[14]

B. S. He, H. Yang, Q. Meng and D. R. Han, Modified Goldstein-Levitin-Polyak projection method for asymmetric strongly monotone variational inequalities, Journal of Optimization Theory and Applications, 112 (2002), 129-143. doi: 10.1023/A:1013048729944.  Google Scholar

[15]

K. C. Kiwiel, Proximal minimization methods with generalized Bregman functions, Journal on Control and Optimization, 35 (1997), 1142-1168. doi: 10.1137/S0363012995281742.  Google Scholar

[16]

B. Lemaire, Coupling optimization methods and variational convergence, in "Trends inMathematical Optimization" (eds. K. H. Hoffman, J. B. Hiriart-Urruty and J. Zowe, C. Lemarechal), Birkhauser-Verlage, Basel, (1988), 163-179. doi: 10.1007/978-3-0348-9297-1_12.  Google Scholar

[17]

B. Lemaire, The proximal algorithm, International Series of Numerical Mathematics, 87 (1989), 73-87  Google Scholar

[18]

P. L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM Journal on Control and Optimization, 16 (1979), 964-979.  Google Scholar

[19]

Z. Q. Luo and P. Tseng, Error bounds and convergence analysis of feasible descent methods: a general approach, Annals of Operations Research, 46 (1993), 157-178. doi: 10.1007/BF02096261.  Google Scholar

[20]

B. Martinet, Regularisation d'inéquations variationelles par approximations successives, Rev. Francaise Informat Recherche Opérationnelle (French), 4 (1970), 154-159.  Google Scholar

[21]

G. Minty, Monotone (nonlinear) operators in Hilbert space, Duke Mathematical Journal, 29 (1962), 341-346. doi: 10.1215/S0012-7094-62-02933-2.  Google Scholar

[22]

B. Martinet, Determination approchée d'un point fixe d'une application pseudocontractante, Comptes rendus de l'Académie des sciences Paris (French), 274 (1972), 163-165.  Google Scholar

[23]

D. Pascali and S. Sburlan, "Nonlinear Mappings of Monotone Type," Editura Academiei, Bucharest, 1978.  Google Scholar

[24]

R. R. Phelps, "Convex Functions, Monotone Operators and Differentiability," Springer-Verlag, New York, 1989. doi: 10.1007/BFb0089089.  Google Scholar

[25]

A. Renaud and G. Cohen, Conditioning and regularization of nonsymmetric operators, Journal of Optimization Theory and Applications, 92 (1997), 127-148. doi: 10.1023/A:1022692114480.  Google Scholar

[26]

R. T. Rockafellar, "Convex Analysis," Princeton University Press, Princeton, 1970.  Google Scholar

[27]

R. T. Rockafellar and R. J. B. Wets, "Variational Analysis," Springer-Verlag, New York, 1997. Google Scholar

[28]

P. Tseng, Applications of a splitting algorithm to decomposition in convex programming and variational inequalities, SIAM Journal on Control and Optimization, 29 (1991), 119-138. doi: 10.1137/0329006.  Google Scholar

[29]

P. Tseng, On linear convergence of iterative methods for the variational inequality problem, Journal of Computational and Applied Mathematics, 60 (1995), 237-252. doi: 10.1016/0377-0427(94)00094-H.  Google Scholar

[30]

P. Tseng, A modified forward-backward splitting method for maximal monotone mappings, SIAM Journal on Control and Optimization, 38 (1998), 431-446. doi: 10.1137/S0363012998338806.  Google Scholar

[31]

P. Tseng and M. V. Solodov, Modified projection-type methods for monotone variational inequalities, SIAM Journal on Control and Optimization, 34 (1996), 1814-1830. doi: 10.1137/S0363012994268655.  Google Scholar

[32]

E. Zeidler, "Nonlinear Monotone Operators, Nonlinear Functional Analysis and its Applications," II/B, Springer-Verlag, New York, 1990. doi: 10.1007/978-1-4612-0985-0.  Google Scholar

show all references

References:
[1]

D. P. Bertsekas, "Constrained Optimization and Lagarange Multiplier Method," Academic Press, New York, 1982.  Google Scholar

[2]

H. G. Chen, "Forward-Backward Splitting Techniques: Theory and Applications," Ph.D. Thesis, Department of Applied Mathematics, University of Washington, Seattle, WA, 1994. Google Scholar

[3]

H. G. Chen and R. T. Rockafellar, Convergence rates in forward-backward splitting, SIAM Journal on Control and Optimization, 7 (1997), 421-444. doi: 10.1137/S1052623495290179.  Google Scholar

[4]

J. Eckstein, Approximate iterations in Bregman-function-based proximal algorithms, Mathematical Programming, 83 (1998), 113-123. doi: 10.1007/BF02680553.  Google Scholar

[5]

J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Mathematical Programming, 55 (1992), 293-318. doi: 10.1007/BF01581204.  Google Scholar

[6]

J. Eckstein and M. C. Ferris, Operator splitting methods for monotone affine variational inequalities, with a parallel application to optimal control, INFORMS Journal on Computing, 10 (1998), 218-235.  Google Scholar

[7]

J. Eckstein and M. Fukushima, Some reformulations and applications of the alternating direction method of multipliers, in "Large Scale Optimization: State of the Art", (eds. W. W. Hager, D. W. Hearn and P. M. Pardalos), Kluwer Academic Publishers, Dordrecht, The Netherlands, (1994), 115-134. doi: 10.1007/978-1-4613-3632-7_7.  Google Scholar

[8]

F. Facchinei and J. S. Pang, "Finite-Dimensional Variatiaonal Inequalities and Complementarity Problems," Spring-Verlag, New York, 2003. Google Scholar

[9]

D. Gabay, Applications of the method of multipliers to variational inequalities, in "Augemented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems" (eds. M. Fortin and R. Glowinski), North Holland, Amsterdam, (1983), 299-331. doi: 10.1016/S0168-2024(08)70034-1.  Google Scholar

[10]

A. A. Goldstein, Convex programming in Hilbert space, Bulletin of the American Mathematical Society, 70 (1964), 709-710. doi: 10.1090/S0002-9904-1964-11178-2.  Google Scholar

[11]

O. Güler, On the convergence of the proximal point algorithm for convex minimization, SIAM Journal on Control and Optimization, 29 (1991), 403-419. doi: 10.1137/0329022.  Google Scholar

[12]

B. S. He, A logarithmic-quadratic proximal prediction-correction method for structured monotone variational inequalities, Computational Optimization and Applications, 35 (2006), 19-46. doi: 10.1007/s10589-006-6442-4.  Google Scholar

[13]

B. S. He and L. Z. Liao, Improvements of some projection methods for monotone nonlinear variational inequalities, Journal of Optimization Theory and Applications, 112 (2002), 111-128. doi: 10.1023/A:1013096613105.  Google Scholar

[14]

B. S. He, H. Yang, Q. Meng and D. R. Han, Modified Goldstein-Levitin-Polyak projection method for asymmetric strongly monotone variational inequalities, Journal of Optimization Theory and Applications, 112 (2002), 129-143. doi: 10.1023/A:1013048729944.  Google Scholar

[15]

K. C. Kiwiel, Proximal minimization methods with generalized Bregman functions, Journal on Control and Optimization, 35 (1997), 1142-1168. doi: 10.1137/S0363012995281742.  Google Scholar

[16]

B. Lemaire, Coupling optimization methods and variational convergence, in "Trends inMathematical Optimization" (eds. K. H. Hoffman, J. B. Hiriart-Urruty and J. Zowe, C. Lemarechal), Birkhauser-Verlage, Basel, (1988), 163-179. doi: 10.1007/978-3-0348-9297-1_12.  Google Scholar

[17]

B. Lemaire, The proximal algorithm, International Series of Numerical Mathematics, 87 (1989), 73-87  Google Scholar

[18]

P. L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM Journal on Control and Optimization, 16 (1979), 964-979.  Google Scholar

[19]

Z. Q. Luo and P. Tseng, Error bounds and convergence analysis of feasible descent methods: a general approach, Annals of Operations Research, 46 (1993), 157-178. doi: 10.1007/BF02096261.  Google Scholar

[20]

B. Martinet, Regularisation d'inéquations variationelles par approximations successives, Rev. Francaise Informat Recherche Opérationnelle (French), 4 (1970), 154-159.  Google Scholar

[21]

G. Minty, Monotone (nonlinear) operators in Hilbert space, Duke Mathematical Journal, 29 (1962), 341-346. doi: 10.1215/S0012-7094-62-02933-2.  Google Scholar

[22]

B. Martinet, Determination approchée d'un point fixe d'une application pseudocontractante, Comptes rendus de l'Académie des sciences Paris (French), 274 (1972), 163-165.  Google Scholar

[23]

D. Pascali and S. Sburlan, "Nonlinear Mappings of Monotone Type," Editura Academiei, Bucharest, 1978.  Google Scholar

[24]

R. R. Phelps, "Convex Functions, Monotone Operators and Differentiability," Springer-Verlag, New York, 1989. doi: 10.1007/BFb0089089.  Google Scholar

[25]

A. Renaud and G. Cohen, Conditioning and regularization of nonsymmetric operators, Journal of Optimization Theory and Applications, 92 (1997), 127-148. doi: 10.1023/A:1022692114480.  Google Scholar

[26]

R. T. Rockafellar, "Convex Analysis," Princeton University Press, Princeton, 1970.  Google Scholar

[27]

R. T. Rockafellar and R. J. B. Wets, "Variational Analysis," Springer-Verlag, New York, 1997. Google Scholar

[28]

P. Tseng, Applications of a splitting algorithm to decomposition in convex programming and variational inequalities, SIAM Journal on Control and Optimization, 29 (1991), 119-138. doi: 10.1137/0329006.  Google Scholar

[29]

P. Tseng, On linear convergence of iterative methods for the variational inequality problem, Journal of Computational and Applied Mathematics, 60 (1995), 237-252. doi: 10.1016/0377-0427(94)00094-H.  Google Scholar

[30]

P. Tseng, A modified forward-backward splitting method for maximal monotone mappings, SIAM Journal on Control and Optimization, 38 (1998), 431-446. doi: 10.1137/S0363012998338806.  Google Scholar

[31]

P. Tseng and M. V. Solodov, Modified projection-type methods for monotone variational inequalities, SIAM Journal on Control and Optimization, 34 (1996), 1814-1830. doi: 10.1137/S0363012994268655.  Google Scholar

[32]

E. Zeidler, "Nonlinear Monotone Operators, Nonlinear Functional Analysis and its Applications," II/B, Springer-Verlag, New York, 1990. doi: 10.1007/978-1-4612-0985-0.  Google Scholar

[1]

Fabio Paronetto. A Harnack type inequality and a maximum principle for an elliptic-parabolic and forward-backward parabolic De Giorgi class. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 853-866. doi: 10.3934/dcdss.2017043
[2]

Jiongmin Yong. Forward-backward evolution equations and applications. Mathematical Control & Related Fields, 2016, 6 (4) : 653-704. doi: 10.3934/mcrf.2016019
[3]

Fabio Paronetto. Elliptic approximation of forward-backward parabolic equations. Communications on Pure & Applied Analysis, 2020, 19 (2) : 1017-1036. doi: 10.3934/cpaa.2020047
[4]

Zhili Ge, Gang Qian, Deren Han. Global convergence of an inexact operator splitting method for monotone variational inequalities. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1013-1026. doi: 10.3934/jimo.2011.7.1013
[5]

G. Bellettini, Giorgio Fusco, Nicola Guglielmi. A concept of solution and numerical experiments for forward-backward diffusion equations. Discrete & Continuous Dynamical Systems, 2006, 16 (4) : 783-842. doi: 10.3934/dcds.2006.16.783
[6]

Xin Chen, Ana Bela Cruzeiro. Stochastic geodesics and forward-backward stochastic differential equations on Lie groups. Conference Publications, 2013, 2013 (special) : 115-121. doi: 10.3934/proc.2013.2013.115
[7]

Yufeng Shi, Tianxiao Wang, Jiongmin Yong. Optimal control problems of forward-backward stochastic Volterra integral equations. Mathematical Control & Related Fields, 2015, 5 (3) : 613-649. doi: 10.3934/mcrf.2015.5.613
[8]

Flavia Smarrazzo, Alberto Tesei. Entropy solutions of forward-backward parabolic equations with Devonshire free energy. Networks & Heterogeneous Media, 2012, 7 (4) : 941-966. doi: 10.3934/nhm.2012.7.941
[9]

Andrés Contreras, Juan Peypouquet. Forward-backward approximation of nonlinear semigroups in finite and infinite horizon. Communications on Pure & Applied Analysis, 2021, 20 (5) : 1893-1906. doi: 10.3934/cpaa.2021051
[10]

Gang Cai, Yekini Shehu, Olaniyi S. Iyiola. Inertial Tseng's extragradient method for solving variational inequality problems of pseudo-monotone and non-Lipschitz operators. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021095
[11]

Flavia Smarrazzo, Andrea Terracina. Sobolev approximation for two-phase solutions of forward-backward parabolic problems. Discrete & Continuous Dynamical Systems, 2013, 33 (4) : 1657-1697. doi: 10.3934/dcds.2013.33.1657
[12]

Hao Chen, Kaitai Li, Yuchuan Chu, Zhiqiang Chen, Yiren Yang. A dimension splitting and characteristic projection method for three-dimensional incompressible flow. Discrete & Continuous Dynamical Systems - B, 2019, 24 (1) : 127-147. doi: 10.3934/dcdsb.2018111
[13]

Gaohang Yu, Shanzhou Niu, Jianhua Ma. Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints. Journal of Industrial & Management Optimization, 2013, 9 (1) : 117-129. doi: 10.3934/jimo.2013.9.117
[14]

Jie Xiong, Shuaiqi Zhang, Yi Zhuang. A partially observed non-zero sum differential game of forward-backward stochastic differential equations and its application in finance. Mathematical Control & Related Fields, 2019, 9 (2) : 257-276. doi: 10.3934/mcrf.2019013
[15]

Adel Chala, Dahbia Hafayed. On stochastic maximum principle for risk-sensitive of fully coupled forward-backward stochastic control of mean-field type with application. Evolution Equations & Control Theory, 2020, 9 (3) : 817-843. doi: 10.3934/eect.2020035
[16]

Abd-semii Oluwatosin-Enitan Owolabi, Timilehin Opeyemi Alakoya, Adeolu Taiwo, Oluwatosin Temitope Mewomo. A new inertial-projection algorithm for approximating common solution of variational inequality and fixed point problems of multivalued mappings. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021004
[17]

Kai Wang, Lingling Xu, Deren Han. A new parallel splitting descent method for structured variational inequalities. Journal of Industrial & Management Optimization, 2014, 10 (2) : 461-476. doi: 10.3934/jimo.2014.10.461
[18]

Hassan Mohammad. A diagonal PRP-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2021, 17 (1) : 101-116. doi: 10.3934/jimo.2019101
[19]

Jinkui Liu, Shengjie Li. Multivariate spectral DY-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2017, 13 (1) : 283-295. doi: 10.3934/jimo.2016017
[20]

Grace Nnennaya Ogwo, Chinedu Izuchukwu, Oluwatosin Temitope Mewomo. A modified extragradient algorithm for a certain class of split pseudo-monotone variational inequality problem. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021011

 Impact Factor: 

Tools

Metrics

  • PDF downloads (92)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences