An accelerated forward-backward algorithm with a new linesearch for convex minimization problems and its applications

Adisak Hanjing; Pachara Jailoka; Suthep Suantai; Adisak Hanjing; Pachara Jailoka; Suthep Suantai

doi:10.3934/math.2021363

AIMS Mathematics

2021, Volume 6, Issue 6: 6180-6200. doi: 10.3934/math.2021363

Previous Article Next Article

Research article

An accelerated forward-backward algorithm with a new linesearch for convex minimization problems and its applications

Research Center in Mathematics and Applied Mathematics, Department of Mathematics, Faculty of Science, Chiang Mai University, Chiang Mai 50200, Thailand

Received: 21 January 2021 Accepted: 01 April 2021 Published: 07 April 2021
MSC : 65K05, 90C25, 90C30

We study and investigate a convex minimization problem of the sum of two convex functions in the setting of a Hilbert space. By assuming the Lipschitz continuity of the gradient of the function, many optimization methods have been invented, where the stepsizes of those algorithms depend on the Lipschitz constant. However, finding such a Lipschitz constant is not an easy task in general practice. In this work, by using a new modification of the linesearches of Cruz and Nghia ^[7] and Kankam et al. ^[14] and an inertial technique, we introduce an accelerated algorithm without any Lipschitz continuity assumption on the gradient. Subsequently, a weak convergence result of the proposed method is established. As applications, we apply and analyze our method for solving an image restoration problem and a regression problem. Numerical experiments show that our method has a higher efficiency than the well-known methods in the literature.
- convex minimization problems,
- forward-backward methods,
- linesearches,
- inertial techniques,
- image restoration problems,
- regression problems
Citation: Adisak Hanjing, Pachara Jailoka, Suthep Suantai. An accelerated forward-backward algorithm with a new linesearch for convex minimization problems and its applications[J]. AIMS Mathematics, 2021, 6(6): 6180-6200. doi: 10.3934/math.2021363

Related Papers:

Abstract

We study and investigate a convex minimization problem of the sum of two convex functions in the setting of a Hilbert space. By assuming the Lipschitz continuity of the gradient of the function, many optimization methods have been invented, where the stepsizes of those algorithms depend on the Lipschitz constant. However, finding such a Lipschitz constant is not an easy task in general practice. In this work, by using a new modification of the linesearches of Cruz and Nghia ^[7] and Kankam et al. ^[14] and an inertial technique, we introduce an accelerated algorithm without any Lipschitz continuity assumption on the gradient. Subsequently, a weak convergence result of the proposed method is established. As applications, we apply and analyze our method for solving an image restoration problem and a regression problem. Numerical experiments show that our method has a higher efficiency than the well-known methods in the literature.

References

[1]	C. Byrne, Iterative oblique projection onto convex sets and the split feasibility problem, Inverse Probl., 18 (2002), 441-453. doi: 10.1088/0266-5611/18/2/310
[2]	H. H. Bauschke, P. L. Combettes, Convex analysis and monotone operator theory in Hilbert spaces, New York: Springer, 2011.
[3]	L. Bussaban, S. Suantai, A. Kaewkhao, A parallel inertial S-iteration forward-backward algorithm for regression and classification problems, Carpathian J. Math., 36 (2020), 35-44. doi: 10.37193/CJM.2020.01.04
[4]	D. P. Bertsekas, J. N. Tsitsiklis, Parallel and distributed computation numerical methods, Belmont: Athena Scientific, 1997.
[5]	A. Beck, M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), 183-202. doi: 10.1137/080716542
[6]	P. L. Combettes, J. C. Pesquet, A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery, IEEE J. STSP, 1 (2007), 564-574.
[7]	J. Y. B. Cruz, T. T. A. Nghia, On the convergence of the forward-backward splitting method with linesearchs, Optim. Method. Softw., 31 (2016), 1209-1238. doi: 10.1080/10556788.2016.1214959
[8]	P. L. Combettes, V. R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4 (2005), 1168-1200. doi: 10.1137/050626090
[9]	J. C. Dunn, Convexity, monotonicity, and gradient processes in Hilbert space, J. Math. Anal. Appl., 53 (1976), 145-158. doi: 10.1016/0022-247X(76)90152-9
[10]	I. Daubechies, M. Defrise, C. D. Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Commun. Pure Appl. Math., 57 (2004), 1413-1457. doi: 10.1002/cpa.20042
[11]	M. Figueiredo, R. Nowak, An EM algorithm for wavelet-based image restoration, IEEE T. Image Process, 12 (2003), 906-916. doi: 10.1109/TIP.2003.814255
[12]	A. Hanjing, S. Suantai, A fast image restoration algorithm based on a fixed point and optimization, Mathematics, 8, (2020), 378.
[13]	E. Hale, W. Yin, Y. Zhang, A fixed-point continuation method for $l_{1}$-regularized minimization with applications to compressed sensing, Rice University: Department of Computational and Applied Mathematics, 2007.
[14]	K. Kankam, N. Pholasa, P. Cholamjiak, On convergence and complexity of the modified forward-backward method involving new linesearches for convex minimization, Math. Meth. Appl. Sci., 42 (2019), 1352-1362. doi: 10.1002/mma.5420
[15]	P. L. Lions, B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16 (1979), 964-979. doi: 10.1137/0716071
[16]	L. J. Lin, W. Takahashi, A general iterative method for hierarchical variational inequality problems in Hilbert spaces and applications, Positivity, 16 (2012), 429-453. doi: 10.1007/s11117-012-0161-0
[17]	B. Martinet, Régularisation d'inéquations variationnelles par approximations successives, Rev. Française Informat. Rech. Opér., 4 (1970), 154-158.
[18]	J. J. Moreau, Fonctions convexes duales et points proximaux dans un espace hilbertien, C. R. Acad. Sci. Paris Sér. A Math., 255 (1962), 2897-2899.
[19]	A. Moudafi, E. Al-Shemas, Simultaneous iterative methods for split equality problem, Trans. Math. Program. Appl., 1 (2013), 1-11.
[20]	Y. Nesterov, A method for solving the convex programming problem with convergence rate $O(1/k^{2})$, Dokl. Akad. Nauk SSSR., 269 (1983), 543-547.
[21]	Y. Nesterov, Gradient Methods for Minimizing Composite Objective Function, CORE Report, 2007. Available from: http://www.ecore.be/DPs/dp 1191313936.pdf.
[22]	B. T. Polyak, Some methods of speeding up the convergence of iteration methods, USSR Comput. Math. Math. Phys., 4 (1964), 1-17.
[23]	R. T. Rockafellar, On the maximal monotonicity of subdifferential mappings, Pac. J. Math., 33 (1970), 209-216. doi: 10.2140/pjm.1970.33.209
[24]	R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 17 (1976), 877-898.
[25]	K. Scheinberg, D. Goldfarb, X. Bai. Fast first order methods for composite convex optimization with backtracking, Found. Comput. Math., 14 (2014), 389-417. doi: 10.1007/s10208-014-9189-9
[26]	S. Suantai, K. Kankam, P. Cholamjiak, A novel forward-backward algorithm for solving convex minimization problem in Hilbert spaces, Mathematics, 8 (2020), 42. doi: 10.3390/math8010042
[27]	S. Suantai, P. Jailoka, A. Hanjing, An accelerated viscosity forward-backward splitting algorithm with the linesearch process for convex minimization problems, J. Inequal. Appl., 2021 (2021), 42. doi: 10.1186/s13660-021-02571-5
[28]	R. Tibshirani, Regression shrinkage and selection via the lasso, J. R. Stat. Soc. B Methodol., 58 (1996), 267-288.
[29]	P. Tseng, A modified forward-backward splitting method for maximal monotone mappings, SIAM J. Control Optim., 38 (2000), 431-446. doi: 10.1137/S0363012998338806
[30]	K. Thung, P. Raveendran, A survey of image quality measures, In: Proceedings of the International Conference for Technical Postgraduates (TECHPOS), Kuala Lumpur, Malaysia, 14-15 December 2009, 1-4.
[31]	K. Tan, H. K. Xu, Approximating fixed points of nonexpansive mappings by the ishikawa iteration process, J. Math. Anal. Appl., 178 (1993), 301-308. doi: 10.1006/jmaa.1993.1309
[32]	K. Toh, S. Yun. An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems, Pac. J. Optim., 6 (2010), 615-640.
[33]	Z. Wang, A. C. Bovik, H. R. Sheikh, E. P. Simoncelli, Image quality assessment: from error visibility to structural similarity, IEEE T. Image Process., 13 (2004), 600-612. doi: 10.1109/TIP.2003.819861

Reader Comments

Your name:*

Email:*
© 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)