August  2013, 6(4): 1043-1063. doi: 10.3934/dcdss.2013.6.1043

Iterative methods for approximating fixed points of Bregman nonexpansive operators

1. 

Departamento de Análisis Matemático

2. 

Universidad de Sevilla

3. 

Apdo. 1160, 41080 Sevilla

4. 

Department of Mathematics

5. 

The Technion-Israel Institute of Technology

6. 

32000 Haifa

7. 

The Technion --- Israel Institute of Technology

Received  July 2011 Revised  March 2012 Published  December 2012

Diverse notions of nonexpansive type operators have been extended to the more general framework of Bregman distances in reflexive Banach spaces. We study these classes of operators, mainly with respect to the existence and approximation of their (asymptotic) fixed points. In particular, the asymptotic behavior of Picard and Mann type iterations is discussed for quasi-Bregman nonexpansive operators. We also present parallel algorithms for approximating common fixed points of a finite family of Bregman strongly nonexpansive operators by means of a block operator which preserves the Bregman strong nonexpansivity. All the results hold, in particular, for the smaller class of Bregman firmly nonexpansive operators, a class which contains the generalized resolvents of monotone mappings with respect to the Bregman distance.
Citation: Victoria Martín-Márquez, Simeon Reich, Shoham Sabach. Iterative methods for approximating fixed points of Bregman nonexpansive operators. Discrete & Continuous Dynamical Systems - S, 2013, 6 (4) : 1043-1063. doi: 10.3934/dcdss.2013.6.1043
References:
[1]

R. Aharoni and Y. Censor, Block-iterative projection methods for parallel computation of solutions to convex feasibility problems,, Linear Algebra Appl., 120 (1989), 165. doi: 10.1016/0024-3795(89)90375-3. Google Scholar

[2]

H. H. Bauschke, J. M. Borwein and P. L. Combettes, Essential smoothness, essential strict convexity, and Legendre functions in Banach spaces,, Comm. Contemp. Math., 3 (2001), 615. doi: 10.1142/S0219199701000524. Google Scholar

[3]

H. H. Bauschke, J. M. Borwein and P. L. Combettes, Bregman monotone optimization algorithms,, SIAM J. Control Optim., 42 (2003), 596. doi: 10.1137/S0363012902407120. Google Scholar

[4]

H. H. Bauschke and P. L. Combettes, "Convex Analysis and Monotone Operator Theory in Hilbert Spaces,", Springer, (2011). doi: 10.1007/978-1-4419-9467-7. Google Scholar

[5]

H. H. Bauschke, E. Matoušková and S. Reich, Projection and proximal point methods: convergence results and counterexamples,, Nonlinear Anal., 56 (2004), 715. doi: 10.1016/j.na.2003.10.010. Google Scholar

[6]

V. Berinde, "Iterative Approximation of Fixed Points,", $2^{nd}$, (1912). Google Scholar

[7]

J. M. Borwein, S. Reich and S. Sabach, A characterization of Bregman firmly nonexpansive operators using a new monotonicity concept,, J. Nonlinear Convex Anal., 12 (2011), 161. Google Scholar

[8]

J. F. Bonnans and A. Shapiro, "Perturbation Analysis of Optimization Problems,", Springer, (2000). Google Scholar

[9]

L. M. Bregman, The method of successive projection for finding a common point of convex sets,, Soviet Math. Dokl., 6 (1965), 688. Google Scholar

[10]

L. M. Bregman, The relaxation method for finding a common point of convex sets and its application to the solution of problems in convex programming,, USSR Comput. Math. Math. Phys., 7 (1967), 200. Google Scholar

[11]

R. E. Bruck and S. Reich, Nonexpansive projections and resolvents of accretive operators in Banach spaces,, Houston J. Math., 3 (1977), 459. Google Scholar

[12]

D. Butnariu and Y. Censor, Strong convergence of almost simultaneous block-iterative projection methods in Hilbert spaces,, J. Comput. Appl. Math., 53 (1994), 33. doi: 10.1016/0377-0427(92)00123-Q. Google Scholar

[13]

D. Butnariu, Y. Censor and S. Reich, Iterative averaging of entropic projections for solving stochastic convex feasibility problems,, Comput. Optim. Appl., 8 (1997), 21. doi: 10.1023/A:1008654413997. Google Scholar

[14]

D. Butnariu and A. N. Iusem, "Totally Convex Functions for Fixed Points Computation and Infinite Dimensional Optimization,", Kluwer Academic Publishers, (2000). doi: 10.1007/978-94-011-4066-9. Google Scholar

[15]

D. Butnariu and E. Resmerita, Bregman distances, totally convex functions and a method for solving operator equations in Banach spaces,, Abstr. Appl. Anal., 2006 (2006), 1. doi: 10.1155/AAA/2006/84919. Google Scholar

[16]

Y. Censor, Row-action methods for huge and sparse systems and their applications,, SIAM Rev., 23 (1981), 444. doi: 10.1137/1023097. Google Scholar

[17]

Y. Censor and A. Lent, An iterative row-action method for interval convex programming,, J. Optim. Theory Appl., 34 (1981), 321. doi: 10.1007/BF00934676. Google Scholar

[18]

Y. Censor and S. Reich, Iterations of paracontractions and firmly nonexpansive operators with applications to feasibility and optimization,, Optimization, 37 (1996), 323. doi: 10.1080/02331939608844225. Google Scholar

[19]

C. Chidume, "Geometric Properties of Banach Spaces and Nonlinear Iterations,", Lecture Notes in Mathematics 1965, (1965). Google Scholar

[20]

G. Cimmino, Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari,, Ric. Sci. (Roma), 9 (1938), 326. Google Scholar

[21]

J. Dugundji and A. Granas, "Fixed Point Theory,", Springer, (2003). Google Scholar

[22]

A. Genel and J. Lindenstrauss, An example concerning fixed points,, Israel J. Math., 22 (1975), 81. Google Scholar

[23]

K. Goebel and S. Reich, "Uniform Convexity, Hyperbolic Ggeometry, and Nonexpansive Mappings,", Marcel Dekker, (1984). Google Scholar

[24]

S. Kaczmarz, Angenäherte Auflösung von Systemen linearer Gleichungen,, Bull. Internat. Acad. Polon. Sci. Lett. Sér. A Sci. Math., 35 (1937), 355. Google Scholar

[25]

G. Kassay, S. Reich and S. Sabach, Iterative methods for solving systems of variational inequalities in reflexive Banach spaces,, SIAM J. Optim., 21 (2011), 1319. doi: 10.1137/110820002. Google Scholar

[26]

M. Kikkawa and W. Takahashi, Approximating fixed points of nonexpansive mappings by the block iterative method in Banach spaces,, Int. J. Comput. Numer. Anal. Appl., 5 (2004), 59. Google Scholar

[27]

M. A. Krasnosel'ski, Two observations about the method of successive approximations,, Uspehi Math. Nauk., 10 (1955), 123. Google Scholar

[28]

M. A. Krasnosel'ski and P. P. Zabreiko, "Geometrical Methods of Nonlinear Analysis,", Springer, (1984). doi: 10.1007/978-3-642-69409-7. Google Scholar

[29]

W. R. Mann, Mean value methods in iteration,, Proc. Amer. Math. Soc., 4 (1953), 506. Google Scholar

[30]

S. Reich, Weak convergence theorems for nonexpansive mappings in Banach spaces,, J. Math. Anal. Appl., 67 (1979), 274. doi: 10.1016/0022-247X(79)90024-6. Google Scholar

[31]

S. Reich, A weak convergence theorem for the alternating method with Bregman distances,, in, (1996), 313. Google Scholar

[32]

S. Reich and S. Sabach, A strong convergence theorem for a proximal-type algorithm in reflexive Banach spaces,, J. Nonlinear Convex Anal., 10 (2009), 471. Google Scholar

[33]

S. Reich and S. Sabach, Two strong convergence theorems for Bregman strongly nonexpansive operators in reflexive Banach spaces,, Nonlinear Analysis, 73 (2010), 122. doi: 10.1016/j.na.2010.03.005. Google Scholar

[34]

S. Reich and S. Sabach, Existence and approximation of fixed points of Bregman firmly nonexpansive mappings in reflexive Banach spaces,, in, (2011), 299. doi: 10.1007/978-1-4419-9569-8_15. Google Scholar

[35]

E. Zeidler, "Nonlinear Functional Analysis and Its Applications, Vol. I, Fixed-Point Theorems,", Springer, (1986). doi: 10.1007/978-1-4612-4838-5. Google Scholar

show all references

References:
[1]

R. Aharoni and Y. Censor, Block-iterative projection methods for parallel computation of solutions to convex feasibility problems,, Linear Algebra Appl., 120 (1989), 165. doi: 10.1016/0024-3795(89)90375-3. Google Scholar

[2]

H. H. Bauschke, J. M. Borwein and P. L. Combettes, Essential smoothness, essential strict convexity, and Legendre functions in Banach spaces,, Comm. Contemp. Math., 3 (2001), 615. doi: 10.1142/S0219199701000524. Google Scholar

[3]

H. H. Bauschke, J. M. Borwein and P. L. Combettes, Bregman monotone optimization algorithms,, SIAM J. Control Optim., 42 (2003), 596. doi: 10.1137/S0363012902407120. Google Scholar

[4]

H. H. Bauschke and P. L. Combettes, "Convex Analysis and Monotone Operator Theory in Hilbert Spaces,", Springer, (2011). doi: 10.1007/978-1-4419-9467-7. Google Scholar

[5]

H. H. Bauschke, E. Matoušková and S. Reich, Projection and proximal point methods: convergence results and counterexamples,, Nonlinear Anal., 56 (2004), 715. doi: 10.1016/j.na.2003.10.010. Google Scholar

[6]

V. Berinde, "Iterative Approximation of Fixed Points,", $2^{nd}$, (1912). Google Scholar

[7]

J. M. Borwein, S. Reich and S. Sabach, A characterization of Bregman firmly nonexpansive operators using a new monotonicity concept,, J. Nonlinear Convex Anal., 12 (2011), 161. Google Scholar

[8]

J. F. Bonnans and A. Shapiro, "Perturbation Analysis of Optimization Problems,", Springer, (2000). Google Scholar

[9]

L. M. Bregman, The method of successive projection for finding a common point of convex sets,, Soviet Math. Dokl., 6 (1965), 688. Google Scholar

[10]

L. M. Bregman, The relaxation method for finding a common point of convex sets and its application to the solution of problems in convex programming,, USSR Comput. Math. Math. Phys., 7 (1967), 200. Google Scholar

[11]

R. E. Bruck and S. Reich, Nonexpansive projections and resolvents of accretive operators in Banach spaces,, Houston J. Math., 3 (1977), 459. Google Scholar

[12]

D. Butnariu and Y. Censor, Strong convergence of almost simultaneous block-iterative projection methods in Hilbert spaces,, J. Comput. Appl. Math., 53 (1994), 33. doi: 10.1016/0377-0427(92)00123-Q. Google Scholar

[13]

D. Butnariu, Y. Censor and S. Reich, Iterative averaging of entropic projections for solving stochastic convex feasibility problems,, Comput. Optim. Appl., 8 (1997), 21. doi: 10.1023/A:1008654413997. Google Scholar

[14]

D. Butnariu and A. N. Iusem, "Totally Convex Functions for Fixed Points Computation and Infinite Dimensional Optimization,", Kluwer Academic Publishers, (2000). doi: 10.1007/978-94-011-4066-9. Google Scholar

[15]

D. Butnariu and E. Resmerita, Bregman distances, totally convex functions and a method for solving operator equations in Banach spaces,, Abstr. Appl. Anal., 2006 (2006), 1. doi: 10.1155/AAA/2006/84919. Google Scholar

[16]

Y. Censor, Row-action methods for huge and sparse systems and their applications,, SIAM Rev., 23 (1981), 444. doi: 10.1137/1023097. Google Scholar

[17]

Y. Censor and A. Lent, An iterative row-action method for interval convex programming,, J. Optim. Theory Appl., 34 (1981), 321. doi: 10.1007/BF00934676. Google Scholar

[18]

Y. Censor and S. Reich, Iterations of paracontractions and firmly nonexpansive operators with applications to feasibility and optimization,, Optimization, 37 (1996), 323. doi: 10.1080/02331939608844225. Google Scholar

[19]

C. Chidume, "Geometric Properties of Banach Spaces and Nonlinear Iterations,", Lecture Notes in Mathematics 1965, (1965). Google Scholar

[20]

G. Cimmino, Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari,, Ric. Sci. (Roma), 9 (1938), 326. Google Scholar

[21]

J. Dugundji and A. Granas, "Fixed Point Theory,", Springer, (2003). Google Scholar

[22]

A. Genel and J. Lindenstrauss, An example concerning fixed points,, Israel J. Math., 22 (1975), 81. Google Scholar

[23]

K. Goebel and S. Reich, "Uniform Convexity, Hyperbolic Ggeometry, and Nonexpansive Mappings,", Marcel Dekker, (1984). Google Scholar

[24]

S. Kaczmarz, Angenäherte Auflösung von Systemen linearer Gleichungen,, Bull. Internat. Acad. Polon. Sci. Lett. Sér. A Sci. Math., 35 (1937), 355. Google Scholar

[25]

G. Kassay, S. Reich and S. Sabach, Iterative methods for solving systems of variational inequalities in reflexive Banach spaces,, SIAM J. Optim., 21 (2011), 1319. doi: 10.1137/110820002. Google Scholar

[26]

M. Kikkawa and W. Takahashi, Approximating fixed points of nonexpansive mappings by the block iterative method in Banach spaces,, Int. J. Comput. Numer. Anal. Appl., 5 (2004), 59. Google Scholar

[27]

M. A. Krasnosel'ski, Two observations about the method of successive approximations,, Uspehi Math. Nauk., 10 (1955), 123. Google Scholar

[28]

M. A. Krasnosel'ski and P. P. Zabreiko, "Geometrical Methods of Nonlinear Analysis,", Springer, (1984). doi: 10.1007/978-3-642-69409-7. Google Scholar

[29]

W. R. Mann, Mean value methods in iteration,, Proc. Amer. Math. Soc., 4 (1953), 506. Google Scholar

[30]

S. Reich, Weak convergence theorems for nonexpansive mappings in Banach spaces,, J. Math. Anal. Appl., 67 (1979), 274. doi: 10.1016/0022-247X(79)90024-6. Google Scholar

[31]

S. Reich, A weak convergence theorem for the alternating method with Bregman distances,, in, (1996), 313. Google Scholar

[32]

S. Reich and S. Sabach, A strong convergence theorem for a proximal-type algorithm in reflexive Banach spaces,, J. Nonlinear Convex Anal., 10 (2009), 471. Google Scholar

[33]

S. Reich and S. Sabach, Two strong convergence theorems for Bregman strongly nonexpansive operators in reflexive Banach spaces,, Nonlinear Analysis, 73 (2010), 122. doi: 10.1016/j.na.2010.03.005. Google Scholar

[34]

S. Reich and S. Sabach, Existence and approximation of fixed points of Bregman firmly nonexpansive mappings in reflexive Banach spaces,, in, (2011), 299. doi: 10.1007/978-1-4419-9569-8_15. Google Scholar

[35]

E. Zeidler, "Nonlinear Functional Analysis and Its Applications, Vol. I, Fixed-Point Theorems,", Springer, (1986). doi: 10.1007/978-1-4612-4838-5. Google Scholar

[1]

Victoria Martín-Márquez, Simeon Reich, Shoham Sabach. Iterative methods for approximating fixed points of Bregman nonexpansive operators. Discrete & Continuous Dynamical Systems - S, 2013, 6 (4) : 1043-1063. doi: 10.3934/dcdss.2013.6.1043

[2]

Yunmei Chen, Xianqi Li, Yuyuan Ouyang, Eduardo Pasiliao. Accelerated bregman operator splitting with backtracking. Inverse Problems & Imaging, 2017, 11 (6) : 1047-1070. doi: 10.3934/ipi.2017048

[3]

Wenye Ma, Stanley Osher. A TV Bregman iterative model of Retinex theory. Inverse Problems & Imaging, 2012, 6 (4) : 697-708. doi: 10.3934/ipi.2012.6.697

[4]

Peter Giesl. Construction of a global Lyapunov function using radial basis functions with a single operator. Discrete & Continuous Dynamical Systems - B, 2007, 7 (1) : 101-124. doi: 10.3934/dcdsb.2007.7.101

[5]

Y. Goto, K. Ishii, T. Ogawa. Method of the distance function to the Bence-Merriman-Osher algorithm for motion by mean curvature. Communications on Pure & Applied Analysis, 2005, 4 (2) : 311-339. doi: 10.3934/cpaa.2005.4.311

[6]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247

[7]

Yu-Lin Chang, Jein-Shan Chen, Jia Wu. Proximal point algorithm for nonlinear complementarity problem based on the generalized Fischer-Burmeister merit function. Journal of Industrial & Management Optimization, 2013, 9 (1) : 153-169. doi: 10.3934/jimo.2013.9.153

[8]

Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601

[9]

Marta García-Huidobro, Raul Manásevich. A three point boundary value problem containing the operator. Conference Publications, 2003, 2003 (Special) : 313-319. doi: 10.3934/proc.2003.2003.313

[10]

Peter Frolkovič, Karol Mikula, Jozef Urbán. Distance function and extension in normal direction for implicitly defined interfaces. Discrete & Continuous Dynamical Systems - S, 2015, 8 (5) : 871-880. doi: 10.3934/dcdss.2015.8.871

[11]

Qinghua Ma, Zuoliang Xu, Liping Wang. Recovery of the local volatility function using regularization and a gradient projection method. Journal of Industrial & Management Optimization, 2015, 11 (2) : 421-437. doi: 10.3934/jimo.2015.11.421

[12]

Jean-Bernard Baillon, Patrick L. Combettes, Roberto Cominetti. Asymptotic behavior of compositions of under-relaxed nonexpansive operators. Journal of Dynamics & Games, 2014, 1 (3) : 331-346. doi: 10.3934/jdg.2014.1.331

[13]

Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018142

[14]

Yazheng Dang, Fanwen Meng, Jie Sun. Convergence analysis of a parallel projection algorithm for solving convex feasibility problems. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 505-519. doi: 10.3934/naco.2016023

[15]

Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 79-89. doi: 10.3934/naco.2015.5.79

[16]

Sophie Guillaume. Evolution equations governed by the subdifferential of a convex composite function in finite dimensional spaces. Discrete & Continuous Dynamical Systems - A, 1996, 2 (1) : 23-52. doi: 10.3934/dcds.1996.2.23

[17]

Valter Pohjola. An inverse problem for the magnetic Schrödinger operator on a half space with partial data. Inverse Problems & Imaging, 2014, 8 (4) : 1169-1189. doi: 10.3934/ipi.2014.8.1169

[18]

Mickaël D. Chekroun, Jean Roux. Homeomorphisms group of normed vector space: Conjugacy problems and the Koopman operator. Discrete & Continuous Dynamical Systems - A, 2013, 33 (9) : 3957-3980. doi: 10.3934/dcds.2013.33.3957

[19]

Zhiqing Meng, Qiying Hu, Chuangyin Dang. A penalty function algorithm with objective parameters for nonlinear mathematical programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 585-601. doi: 10.3934/jimo.2009.5.585

[20]

Maolin Cheng, Mingyin Xiang. Application of a modified CES production function model based on improved firefly algorithm. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2019018

2018 Impact Factor: 0.545

Metrics

  • PDF downloads (5)
  • HTML views (0)
  • Cited by (0)

[Back to Top]