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

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

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.
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, (1982). Google Scholar

[2]

H. G. Chen, "Forward-Backward Splitting Techniques: Theory and Applications,", Ph.D. Thesis, (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. doi: 10.1137/S1052623495290179. Google Scholar

[4]

J. Eckstein, Approximate iterations in Bregman-function-based proximal algorithms,, Mathematical Programming, 83 (1998), 113. 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. 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. Google Scholar

[7]

J. Eckstein and M. Fukushima, Some reformulations and applications of the alternating direction method of multipliers,, in, (1994), 115. 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, (2003). Google Scholar

[9]

D. Gabay, Applications of the method of multipliers to variational inequalities,, in, (1983), 299. 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. 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. 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. 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. 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. 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. doi: 10.1137/S0363012995281742. Google Scholar

[16]

B. Lemaire, Coupling optimization methods and variational convergence,, in, (1988), 163. 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. 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. 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. 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. Google Scholar

[21]

G. Minty, Monotone (nonlinear) operators in Hilbert space,, Duke Mathematical Journal, 29 (1962), 341. 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. Google Scholar

[23]

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

[24]

R. R. Phelps, "Convex Functions, Monotone Operators and Differentiability,", Springer-Verlag, (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. doi: 10.1023/A:1022692114480. Google Scholar

[26]

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

[27]

R. T. Rockafellar and R. J. B. Wets, "Variational Analysis,", Springer-Verlag, (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. 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. 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. 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. doi: 10.1137/S0363012994268655. Google Scholar

[32]

E. Zeidler, "Nonlinear Monotone Operators, Nonlinear Functional Analysis and its Applications,", II/B, (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, (1982). Google Scholar

[2]

H. G. Chen, "Forward-Backward Splitting Techniques: Theory and Applications,", Ph.D. Thesis, (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. doi: 10.1137/S1052623495290179. Google Scholar

[4]

J. Eckstein, Approximate iterations in Bregman-function-based proximal algorithms,, Mathematical Programming, 83 (1998), 113. 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. 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. Google Scholar

[7]

J. Eckstein and M. Fukushima, Some reformulations and applications of the alternating direction method of multipliers,, in, (1994), 115. 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, (2003). Google Scholar

[9]

D. Gabay, Applications of the method of multipliers to variational inequalities,, in, (1983), 299. 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. 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. 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. 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. 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. 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. doi: 10.1137/S0363012995281742. Google Scholar

[16]

B. Lemaire, Coupling optimization methods and variational convergence,, in, (1988), 163. 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. 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. 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. 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. Google Scholar

[21]

G. Minty, Monotone (nonlinear) operators in Hilbert space,, Duke Mathematical Journal, 29 (1962), 341. 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. Google Scholar

[23]

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

[24]

R. R. Phelps, "Convex Functions, Monotone Operators and Differentiability,", Springer-Verlag, (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. doi: 10.1023/A:1022692114480. Google Scholar

[26]

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

[27]

R. T. Rockafellar and R. J. B. Wets, "Variational Analysis,", Springer-Verlag, (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. 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. 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. 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. doi: 10.1137/S0363012994268655. Google Scholar

[32]

E. Zeidler, "Nonlinear Monotone Operators, Nonlinear Functional Analysis and its Applications,", II/B, (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 - A, 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]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

Hassan Mohammad. A diagonal PRP-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019101

[16]

Li Wang, Yang Li, Liwei Zhang. A differential equation method for solving box constrained variational inequality problems. Journal of Industrial & Management Optimization, 2011, 7 (1) : 183-198. doi: 10.3934/jimo.2011.7.183

[17]

Hui-Qiang Ma, Nan-Jing Huang. Neural network smoothing approximation method for stochastic variational inequality problems. Journal of Industrial & Management Optimization, 2015, 11 (2) : 645-660. doi: 10.3934/jimo.2015.11.645

[18]

Walter Allegretto, Yanping Lin, Shuqing Ma. On the box method for a non-local parabolic variational inequality. Discrete & Continuous Dynamical Systems - B, 2001, 1 (1) : 71-88. doi: 10.3934/dcdsb.2001.1.71

[19]

Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733

[20]

Ming Chen, Chongchao Huang. A power penalty method for a class of linearly constrained variational inequality. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1381-1396. doi: 10.3934/jimo.2018012

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]