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

[2]

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

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

[4]

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

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

[8]

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

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

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

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

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

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

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

[15]

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

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

[17]

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

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

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

[20]

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

[21]

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

[23]

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

[24]

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

[26]

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

[27]

R. T. Rockafellar and R. J. B. Wets, "Variational Analysis," Springer-Verlag, New York, 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-138. 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-252. 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-446. 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-1830. doi: 10.1137/S0363012994268655.

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

show all references

References:
[1]

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

[2]

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

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

[4]

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

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

[8]

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

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

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

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

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

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

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

[15]

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

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

[17]

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

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

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

[20]

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

[21]

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

[23]

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

[24]

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

[26]

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

[27]

R. T. Rockafellar and R. J. B. Wets, "Variational Analysis," Springer-Verlag, New York, 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-138. 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-252. 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-446. 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-1830. doi: 10.1137/S0363012994268655.

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

[1]

Fabio Paronetto. A Harnack type inequality and a maximum principle for an elliptic-parabolic and forward-backward parabolic De Giorgi class. Discrete and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Applied Analysis, 2021, 20 (5) : 1893-1906. doi: 10.3934/cpaa.2021051

[10]

Kaitong Hu, Zhenjie Ren, Nizar Touzi. On path-dependent multidimensional forward-backward SDEs. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022010

[11]

Jiongmin Yong. Forward-backward stochastic differential equations: initiation, development and beyond. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022011

[12]

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 and Management Optimization, 2021  doi: 10.3934/jimo.2021095

[13]

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

[14]

Shaotao Hu, Yuanheng Wang, Bing Tan, Fenghui Wang. Inertial iterative method for solving variational inequality problems of pseudo-monotone operators and fixed point problems of nonexpansive mappings in Hilbert spaces. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022060

[15]

Ouafa Belguidoum, Hassina Grar. An improved projection algorithm for variational inequality problem with multivalued mapping. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022002

[16]

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

[17]

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

[18]

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 and Related Fields, 2019, 9 (2) : 257-276. doi: 10.3934/mcrf.2019013

[19]

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 and Control Theory, 2020, 9 (3) : 817-843. doi: 10.3934/eect.2020035

[20]

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 and Optimization, 2022, 12 (2) : 255-278. doi: 10.3934/naco.2021004

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]