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

Xiao Ding; Deren Han

doi:10.3934/naco.2013.3.295

Article Contents

2013, Volume 3, Issue 2: 295-307. Doi: 10.3934/naco.2013.3.295

This issue Previous Article A structured trust region method for nonconvex programming with separable structure Next Article Nonmonotone retrospective conic trust region method for unconstrained optimization

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

Received: May 2012

Revised: January 2013

Published: April 2013

Abstract / Introduction Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Related Papers

Cited by

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.