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).

[2]

H. G. Chen, "Forward-Backward Splitting Techniques: Theory and Applications,", Ph.D. Thesis, (1994).

[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.

[4]

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

[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.

[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.

[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.

[8]

F. Facchinei and J. S. Pang, "Finite-Dimensional Variatiaonal Inequalities and Complementarity Problems,", Spring-Verlag, (2003).

[9]

D. Gabay, Applications of the method of multipliers to variational inequalities,, in, (1983), 299. doi: 10.1016/S0168-2024(08)70034-1.

[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.

[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.

[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.

[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.

[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.

[15]

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

[16]

B. Lemaire, Coupling optimization methods and variational convergence,, in, (1988), 163. doi: 10.1007/978-3-0348-9297-1_12.

[17]

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

[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.

[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.

[20]

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

[21]

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

[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.

[23]

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

[24]

R. R. Phelps, "Convex Functions, Monotone Operators and Differentiability,", Springer-Verlag, (1989). doi: 10.1007/BFb0089089.

[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.

[26]

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

[27]

R. T. Rockafellar and R. J. B. Wets, "Variational Analysis,", Springer-Verlag, (1997).

[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.

[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.

[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.

[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.

[32]

E. Zeidler, "Nonlinear Monotone Operators, Nonlinear Functional Analysis and its Applications,", II/B, (1990). doi: 10.1007/978-1-4612-0985-0.

show all references

References:
[1]

D. P. Bertsekas, "Constrained Optimization and Lagarange Multiplier Method,", Academic Press, (1982).

[2]

H. G. Chen, "Forward-Backward Splitting Techniques: Theory and Applications,", Ph.D. Thesis, (1994).

[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.

[4]

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

[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.

[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.

[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.

[8]

F. Facchinei and J. S. Pang, "Finite-Dimensional Variatiaonal Inequalities and Complementarity Problems,", Spring-Verlag, (2003).

[9]

D. Gabay, Applications of the method of multipliers to variational inequalities,, in, (1983), 299. doi: 10.1016/S0168-2024(08)70034-1.

[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.

[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.

[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.

[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.

[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.

[15]

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

[16]

B. Lemaire, Coupling optimization methods and variational convergence,, in, (1988), 163. doi: 10.1007/978-3-0348-9297-1_12.

[17]

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

[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.

[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.

[20]

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

[21]

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

[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.

[23]

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

[24]

R. R. Phelps, "Convex Functions, Monotone Operators and Differentiability,", Springer-Verlag, (1989). doi: 10.1007/BFb0089089.

[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.

[26]

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

[27]

R. T. Rockafellar and R. J. B. Wets, "Variational Analysis,", Springer-Verlag, (1997).

[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.

[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.

[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.

[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.

[32]

E. Zeidler, "Nonlinear Monotone Operators, Nonlinear Functional Analysis and its Applications,", II/B, (1990). doi: 10.1007/978-1-4612-0985-0.

[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]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

Haiyang Wang, Jianfeng Zhang. Forward backward SDEs in weak formulation. Mathematical Control & Related Fields, 2018, 8 (3&4) : 1021-1049. doi: 10.3934/mcrf.2018044

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

Yekini Shehu, Olaniyi Iyiola. On a modified extragradient method for variational inequality problem with application to industrial electricity production. Journal of Industrial & Management Optimization, 2019, 15 (1) : 319-342. doi: 10.3934/jimo.2018045

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]