Extragradient-projection method for solving constrained convex minimization problems

Previous Article
General parametric sufficient optimality conditions for multiple objective fractional subset programming relating to generalized $(\rho,\eta,A)$ -invexity
NACO Home
This Issue
Next Article
Optimality conditions and duality for minimax fractional programming involving nonsmooth generalized univexity

2011, 1(3): 341-359. doi: 10.3934/naco.2011.1.341

Extragradient-projection method for solving constrained convex minimization problems

Luchuan Ceng ^1, , Qamrul Hasan Ansari ^2, and Jen-Chih Yao ^3,

1.	Department of Mathematics, Shanghai Normal University, Scientific Computing Key Laboratory of Shanghai Universities, Shanghai 200234, China
2.	Department of Mathematics, Aligarh Muslim University, Aligarh 202 002, India
3.	Kaohsiung Medical University, Kaohsiung Medical University, Kaohsiung 80708, Taiwan

Received April 2011 Revised June 2011 Published September 2011

Abstract
Related Papers

In this paper, we introduce an iterative process for finding a common element of the set of fixed points of a nonexpansive mapping and the set of solutions of a constrained convex minimization problem for a Fr\'{e}chet differentiable function. The iterative process is based on the so-called extragradient-projection method. We derive several weak convergence results for two sequences generated by the proposed iterative process. On the other hand, by applying the viscosity approximation method and the additional projection method (namely, the CQ method) to the extragradient-projection method, respectively, we also provide two modifications of the extragradient-projection method to obtain two strong convergence theorems. The results of this paper represent the supplement, improvement, extension and development of some known results given in the literature.

Keywords: iterative processes., averaged mapping, Extragradient-projection method, constrained convex minimization, nonexpansive mapping, relaxed extragradient-projection method.

Mathematics Subject Classification: Primary: 90C25; Secondary: 65K05, 47H0.

Citation: Luchuan Ceng, Qamrul Hasan Ansari, Jen-Chih Yao. Extragradient-projection method for solving constrained convex minimization problems. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 341-359. doi: 10.3934/naco.2011.1.341

References:

[1]	H. H. Bauschke, J. V. Burke, F. R. Deutsch, H. S. Hundal and J. D. Vanderwerff, A new proximal point iteration that converges weakly but not in norm,, Proc. Amer. Math. Soc., 133 (2005), 1829. doi: 10.1090/S0002-9939-05-07719-1. Google Scholar
[2]	H. H. Bauschke and P. L. Combettes, A weak-to-strong convergence principle for Fejer-monotone methods in Hilbert spaces,, Math. Operations Research, 26 (2001), 248. doi: 10.1287/moor.26.2.248.10558. Google Scholar
[3]	D. P. Bertsekas and E. M. Gafni, Projection methods for variational inequalities with applications to the traffic assignment problem,, Math. Program. Study, 17 (1982), 139. Google Scholar
[4]	C. Byrne, A unified treatment of some iterative algorithms in signal processing and image reconstruction,, Inverse Problems, 20 (2004), 103. doi: 10.1088/0266-5611/20/1/006. Google Scholar
[5]	L. C. Ceng, Q. H. Ansari and J. C. Yao, Relaxed extragradient iterative methods for variational inequalities,, Appl. Math. Computation, 218 (2011), 1112. Google Scholar
[6]	L. C. Ceng and S. Huang, Modified extragradient methods for strict pseudo-contractions and monotone mappings,, Taiwanese J. Math., 13 (2009), 1197. Google Scholar
[7]	L. C. Ceng, S. Huang and A. Petrusel, Weak convergence theorem by a modified extragradient method for nonexpansive mappings and monotone mappings,, Taiwanese J. Math., 13 (2009), 225. Google Scholar
[8]	L. C. Ceng, A. Petrusel, C. Lee and M. M. Wong, Two extragradient approximation methods for variational inequalities and fixed point problems of strict pseudo-contractions,, Taiwanese J. Math., 13 (2009), 607. Google Scholar
[9]	L. C. Ceng, H. K. Xu and J. C. Yao, The viscosity approximation method for asymptotically nonexpansive mappings in Banach spaces,, Nonlinear Anal., 69 (2008), 1402. doi: 10.1016/j.na.2007.06.040. Google Scholar
[10]	L. C. Ceng and J. C. Yao, Relaxed viscosity approximation methods for fixed point problems and variational inequality problems,, Nonlinear Anal., 69 (2008), 3299. doi: 10.1016/j.na.2007.09.019. Google Scholar
[11]	P. L. Combettes, Solving monotone inclusions via compositions of nonexpansive averaged operators,, Optimization, 53 (2004), 475. doi: 10.1080/02331930412331327157. Google Scholar
[12]	K. Geobel and W. A. Kirk, "Topics in Metric Fixed Point Theory,", Cambridge Studies in Advanced Mathematics, (1990). doi: 10.1017/CBO9780511526152. Google Scholar
[13]	O. Güler, On the convergence of the proximal point algorithm for convex optimization,, SIAM J. Control Optim., 29 (1991), 403. doi: 10.1137/0329022. Google Scholar
[14]	D. Han and H. K. Lo, Solving non-additive traffic assignment problems: A descent method for co-coercive variational inequalities,, European J. Operational Research, 159 (2004), 529. doi: 10.1016/S0377-2217(03)00423-5. Google Scholar
[15]	G. M. Korpelevich, An extragradient method for finding saddle points and for other problems,, Ekonomika i Matematicheskie Metody, 12 (1976), 747. Google Scholar
[16]	E. S. Levitin and B. T. Polyak, Constrained minimization methods,, Zh. vychisl. Mat. mat. Fiz., 6 (1966), 787. Google Scholar
[17]	G. Marino and H. K. Xu, Convergence of generalized proximal point algorithm,, Comm. Pure Appl. Anal., 3 (2004), 791. doi: 10.3934/cpaa.2004.3.791. Google Scholar
[18]	C. Martinez-Yanes and H. K. Xu, Strong convergence of the CQ method for fixed point iteration processes,, Nonlinear Anal., 64 (2006), 2400. doi: 10.1016/j.na.2005.08.018. Google Scholar
[19]	N. Nadezhkina and W. Takahashi, Weak convergence theorem by an extragradient method for nonexpansive mappings and monotone mappings,, J. Optim. Theory Appl., 128 (2006), 191. doi: 10.1007/s10957-005-7564-z. Google Scholar
[20]	Z. Opial, Weak convergence of the sequence of successive approximations of nonexpansive mappings,, Bull. Amer. Math. Soc., 73 (1967), 595. doi: 10.1090/S0002-9904-1967-11761-0. Google Scholar
[21]	R. T. Rockafellar, Monotone operators and the proximal point algorithm,, SIAM J. Control Optim., 14 (1976), 877. doi: 10.1137/0314056. Google Scholar
[22]	M. V. Solodov and B. F. Svaiter, Forcing strong convergence of proximal point iterations in a Hilbert space,, Math. Program. Ser. A, 87 (2000), 189. Google Scholar
[23]	T. Suzuki, Strong convergence of Krasnoselskii and Mann's type sequences for one-parameter nonexpansive semigroups without Bochner integrals,, J. Math. Anal. Appl., 305 (2005), 227. doi: 10.1016/j.jmaa.2004.11.017. Google Scholar
[24]	W. Takahashi and M. Toyoda, Weak convergence theorems for nonexpansive mappings and monotone mappings,, J. Optim. Theory Appl., 118 (2003), 417. doi: 10.1023/A:1025407607560. Google Scholar
[25]	H. K. Xu, Iterative algorithms for nonlinear operators,, J. London Math. Soc., 66 (2002), 240. doi: 10.1112/S0024610702003332. Google Scholar
[26]	H. K. Xu, Viscosity approximation methods for nonexpansive mappings,, J. Math. Anal. Appl., 298 (2004), 279. doi: 10.1016/j.jmaa.2004.04.059. Google Scholar
[27]	H. K. Xu, A regularization method for the proximal point algorithm,, J. Global Optim., 36 (2006), 115. doi: 10.1007/s10898-006-9002-7. Google Scholar
[28]	H. K. Xu, Averaged mappings and the gradient-projection algorithm,, Taiwanese J. Math., (). Google Scholar
[29]	H. K. Xu and T. H. Kim, Convergence of hybrid steepest-descent methods for variational inequalities,, J. Optim. Theory Appl., 119 (2003), 185. doi: 10.1023/B:JOTA.0000005048.79379.b6. Google Scholar
[30]	L. C. Zeng, S. Al-Homidan and Q. H. Ansari, Relaxed extragradient-like method for general system of generalized nonlinear mixed equilibrium problems and fixed point problems,, Fixed Point Theory Appl., (). Google Scholar

show all references

References:

[1]	H. H. Bauschke, J. V. Burke, F. R. Deutsch, H. S. Hundal and J. D. Vanderwerff, A new proximal point iteration that converges weakly but not in norm,, Proc. Amer. Math. Soc., 133 (2005), 1829. doi: 10.1090/S0002-9939-05-07719-1. Google Scholar
[2]	H. H. Bauschke and P. L. Combettes, A weak-to-strong convergence principle for Fejer-monotone methods in Hilbert spaces,, Math. Operations Research, 26 (2001), 248. doi: 10.1287/moor.26.2.248.10558. Google Scholar
[3]	D. P. Bertsekas and E. M. Gafni, Projection methods for variational inequalities with applications to the traffic assignment problem,, Math. Program. Study, 17 (1982), 139. Google Scholar
[4]	C. Byrne, A unified treatment of some iterative algorithms in signal processing and image reconstruction,, Inverse Problems, 20 (2004), 103. doi: 10.1088/0266-5611/20/1/006. Google Scholar
[5]	L. C. Ceng, Q. H. Ansari and J. C. Yao, Relaxed extragradient iterative methods for variational inequalities,, Appl. Math. Computation, 218 (2011), 1112. Google Scholar
[6]	L. C. Ceng and S. Huang, Modified extragradient methods for strict pseudo-contractions and monotone mappings,, Taiwanese J. Math., 13 (2009), 1197. Google Scholar
[7]	L. C. Ceng, S. Huang and A. Petrusel, Weak convergence theorem by a modified extragradient method for nonexpansive mappings and monotone mappings,, Taiwanese J. Math., 13 (2009), 225. Google Scholar
[8]	L. C. Ceng, A. Petrusel, C. Lee and M. M. Wong, Two extragradient approximation methods for variational inequalities and fixed point problems of strict pseudo-contractions,, Taiwanese J. Math., 13 (2009), 607. Google Scholar
[9]	L. C. Ceng, H. K. Xu and J. C. Yao, The viscosity approximation method for asymptotically nonexpansive mappings in Banach spaces,, Nonlinear Anal., 69 (2008), 1402. doi: 10.1016/j.na.2007.06.040. Google Scholar
[10]	L. C. Ceng and J. C. Yao, Relaxed viscosity approximation methods for fixed point problems and variational inequality problems,, Nonlinear Anal., 69 (2008), 3299. doi: 10.1016/j.na.2007.09.019. Google Scholar
[11]	P. L. Combettes, Solving monotone inclusions via compositions of nonexpansive averaged operators,, Optimization, 53 (2004), 475. doi: 10.1080/02331930412331327157. Google Scholar
[12]	K. Geobel and W. A. Kirk, "Topics in Metric Fixed Point Theory,", Cambridge Studies in Advanced Mathematics, (1990). doi: 10.1017/CBO9780511526152. Google Scholar
[13]	O. Güler, On the convergence of the proximal point algorithm for convex optimization,, SIAM J. Control Optim., 29 (1991), 403. doi: 10.1137/0329022. Google Scholar
[14]	D. Han and H. K. Lo, Solving non-additive traffic assignment problems: A descent method for co-coercive variational inequalities,, European J. Operational Research, 159 (2004), 529. doi: 10.1016/S0377-2217(03)00423-5. Google Scholar
[15]	G. M. Korpelevich, An extragradient method for finding saddle points and for other problems,, Ekonomika i Matematicheskie Metody, 12 (1976), 747. Google Scholar
[16]	E. S. Levitin and B. T. Polyak, Constrained minimization methods,, Zh. vychisl. Mat. mat. Fiz., 6 (1966), 787. Google Scholar
[17]	G. Marino and H. K. Xu, Convergence of generalized proximal point algorithm,, Comm. Pure Appl. Anal., 3 (2004), 791. doi: 10.3934/cpaa.2004.3.791. Google Scholar
[18]	C. Martinez-Yanes and H. K. Xu, Strong convergence of the CQ method for fixed point iteration processes,, Nonlinear Anal., 64 (2006), 2400. doi: 10.1016/j.na.2005.08.018. Google Scholar
[19]	N. Nadezhkina and W. Takahashi, Weak convergence theorem by an extragradient method for nonexpansive mappings and monotone mappings,, J. Optim. Theory Appl., 128 (2006), 191. doi: 10.1007/s10957-005-7564-z. Google Scholar
[20]	Z. Opial, Weak convergence of the sequence of successive approximations of nonexpansive mappings,, Bull. Amer. Math. Soc., 73 (1967), 595. doi: 10.1090/S0002-9904-1967-11761-0. Google Scholar
[21]	R. T. Rockafellar, Monotone operators and the proximal point algorithm,, SIAM J. Control Optim., 14 (1976), 877. doi: 10.1137/0314056. Google Scholar
[22]	M. V. Solodov and B. F. Svaiter, Forcing strong convergence of proximal point iterations in a Hilbert space,, Math. Program. Ser. A, 87 (2000), 189. Google Scholar
[23]	T. Suzuki, Strong convergence of Krasnoselskii and Mann's type sequences for one-parameter nonexpansive semigroups without Bochner integrals,, J. Math. Anal. Appl., 305 (2005), 227. doi: 10.1016/j.jmaa.2004.11.017. Google Scholar
[24]	W. Takahashi and M. Toyoda, Weak convergence theorems for nonexpansive mappings and monotone mappings,, J. Optim. Theory Appl., 118 (2003), 417. doi: 10.1023/A:1025407607560. Google Scholar
[25]	H. K. Xu, Iterative algorithms for nonlinear operators,, J. London Math. Soc., 66 (2002), 240. doi: 10.1112/S0024610702003332. Google Scholar
[26]	H. K. Xu, Viscosity approximation methods for nonexpansive mappings,, J. Math. Anal. Appl., 298 (2004), 279. doi: 10.1016/j.jmaa.2004.04.059. Google Scholar
[27]	H. K. Xu, A regularization method for the proximal point algorithm,, J. Global Optim., 36 (2006), 115. doi: 10.1007/s10898-006-9002-7. Google Scholar
[28]	H. K. Xu, Averaged mappings and the gradient-projection algorithm,, Taiwanese J. Math., (). Google Scholar
[29]	H. K. Xu and T. H. Kim, Convergence of hybrid steepest-descent methods for variational inequalities,, J. Optim. Theory Appl., 119 (2003), 185. doi: 10.1023/B:JOTA.0000005048.79379.b6. Google Scholar
[30]	L. C. Zeng, S. Al-Homidan and Q. H. Ansari, Relaxed extragradient-like method for general system of generalized nonlinear mixed equilibrium problems and fixed point problems,, Fixed Point Theory Appl., (). Google Scholar

[1]	Biao Qu, Naihua Xiu. A relaxed extragradient-like method for a class of constrained optimization problem. Journal of Industrial & Management Optimization, 2007, 3 (4) : 645-654. doi: 10.3934/jimo.2007.3.645
[2]	Chunming Tang, Jinbao Jian, Guoyin Li. A proximal-projection partial bundle method for convex constrained minimax problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 757-774. doi: 10.3934/jimo.2018069
[3]	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
[4]	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
[5]	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
[6]	Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018
[7]	Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[8]	Leonardi Filippo. A projection method for the computation of admissible measure valued solutions of the incompressible Euler equations. Discrete & Continuous Dynamical Systems - S, 2018, 11 (5) : 941-961. doi: 10.3934/dcdss.2018056
[9]	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
[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]	Sohana Jahan. Supervised distance preserving projection using alternating direction method of multipliers. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-17. doi: 10.3934/jimo.2019029
[12]	Lin Du, Yun Zhang. $\mathcal{H}_∞$ filtering for switched nonlinear systems: A state projection method. Journal of Industrial & Management Optimization, 2018, 14 (1) : 19-33. doi: 10.3934/jimo.2017035
[13]	Gang Qian, Deren Han, Lingling Xu, Hai Yang. Solving nonadditive traffic assignment problems: A self-adaptive projection-auxiliary problem method for variational inequalities. Journal of Industrial & Management Optimization, 2013, 9 (1) : 255-274. doi: 10.3934/jimo.2013.9.255
[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]	Fabrizio Colombo, Irene Sabadini, Frank Sommen. The inverse Fueter mapping theorem. Communications on Pure & Applied Analysis, 2011, 10 (4) : 1165-1181. doi: 10.3934/cpaa.2011.10.1165
[16]	Thi Phuong Dong Nguyen, Jean Jacques Strodiot, Thi Thu Van Nguyen, Van Hien Nguyen. A family of extragradient methods for solving equilibrium problems. Journal of Industrial & Management Optimization, 2015, 11 (2) : 619-630. doi: 10.3934/jimo.2015.11.619
[17]	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
[18]	Hongxia Yin. An iterative method for general variational inequalities. Journal of Industrial & Management Optimization, 2005, 1 (2) : 201-209. doi: 10.3934/jimo.2005.1.201
[19]	John Banks. Topological mapping properties defined by digraphs. Discrete & Continuous Dynamical Systems - A, 1999, 5 (1) : 83-92. doi: 10.3934/dcds.1999.5.83
[20]	Mads Kyed. On a mapping property of the Oseen operator with rotation. Discrete & Continuous Dynamical Systems - S, 2013, 6 (5) : 1315-1322. doi: 10.3934/dcdss.2013.6.1315

Impact Factor:

American Institute of Mathematical Sciences