Accelerated augmented Lagrangian method for total variation minimization. (English) Zbl 1438.90259
Summary: The augmented Lagrangian method (TVAL3) [C. Li et al., Comput. Optim. Appl. 56, No. 3, 507–530 (2013; Zbl 1287.90066)], which combines an alternating direction technique with a nonmonotone line search to minimize the augmented Lagrangian function at each iteration, is a very efficient method for total variation image restoration. In this paper we present an accelerated augmented Lagrangian based on TVAL3 for total variation image restoration. It is widely accepted that the stepsize, is very crucial to the performance of numerical algorithms, especially for gradient-based methods. We design a new quadratic approximation model to generate an efficient approximately optimal stepsize, truncate it by the two well-known BB stepsizes and use the resulted approximately optimal stepsize to accelerate the augmented Lagrangian method. We establish the convergence of the proposed method under weaker condition. Numerical experiments show that the proposed method is very promising.
MSC:
| 90C25 | Convex programming |
| 90C06 | Large-scale problems in mathematical programming |
| 65F22 | Ill-posedness and regularization problems in numerical linear algebra |
Keywords:
image denoising; total variation; approximately optimal stepsize; BFGS update formula; augmented Lagrangian methodCitations:
Zbl 1287.90066References:
| [1] | Barzilai J, Borwein JM (1988) Two-point step size gradient methods. IMA J Numer Anal 8:141-148 · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141 |
| [2] | Beck A, Teboulle M (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J Imaging Sci 2(1):183-202 · Zbl 1175.94009 · doi:10.1137/080716542 |
| [3] | Becker S, Bobin J, Cands EJ (2009) NESTA: a fast and accurate first-order method for sparse recovery. SIAM J Imaging Sci 4(1):1-39 · Zbl 1209.90265 · doi:10.1137/090756855 |
| [4] | Bioucas-Dias JM, Figueiredo MAT (2007) A new TwIST: two-step iterative shrinkage/thresholding algorithms for image restoration. IEEE Trans Image Process 16(12):2992-3004 · doi:10.1109/TIP.2007.909319 |
| [5] | Bioucas-Dias JM, Figueiredo MAT (2007) Two-step algorithms for linear inverse problems with non-quadratic regularization. In: IEEE international conference on image processing, San Antonio, pp I-105-I-108 |
| [6] | Dai YH, Liao LZ (2002) R-linear convergence of the Barzilai and Borwein gradient method. IMA J Numer Anal 22(1):1-10 · Zbl 1002.65069 · doi:10.1093/imanum/22.1.1 |
| [7] | Figueiredo MAT, Nowak RD, Wright SJ (2007) Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems. IEEE J Sel Top Signal Process 1(4):586-597 · doi:10.1109/JSTSP.2007.910281 |
| [8] | Ford J, Moghrabi I (1993) Alternative parameter choices for multi-step quasi-Newton methods. Optim Methods Softw 2(3):357-370 · doi:10.1080/10556789308805550 |
| [9] | Ford J, Moghrabi I (1994) Multi-step quasi-Newton methods for optimization. J Comput Appl Math 50(93):305-323 · Zbl 0807.65062 · doi:10.1016/0377-0427(94)90309-3 |
| [10] | Hale ET, Yin WT, Zhang Y (2008) Fixed-point continuation for \[l_1\] l1-minimization: methodology and convergence. SIAM J Optim 19(3):1107-1130 · Zbl 1180.65076 |
| [11] | Han BS, Yang YH (2019) An integro-PDE model with variable motility. Nonlinear Anal. Real World Appl. 45:186-199 · Zbl 1411.35016 · doi:10.1016/j.nonrwa.2018.07.004 |
| [12] | Huang YK, Liu HW (2015) A Barzilai-Borwein type method for minimizing composite functions. Numer Algorithms 69(4):819-838 · Zbl 1321.65099 · doi:10.1007/s11075-014-9927-8 |
| [13] | Huang YK, Liu HW (2016) Smoothing projected Barzilai-Borwein method for constrained non-Lipschitz optimization. Comput Optim Appl 65(3):671-698 · Zbl 1357.90117 · doi:10.1007/s10589-016-9854-9 |
| [14] | Huang YK, Liu HW, Zhou S (2014) A Barzilai-Borwein type method for stochastic linear complementarity problem. Numer Algorithms 67(3):477-489 · Zbl 1327.90312 · doi:10.1007/s11075-013-9803-y |
| [15] | Huang YK, Liu HW, Zhou S (2015) An efficient monotone projected Barzilai-Borwein method for nonnegative matrix factorization. Appl Math Lett 45:12-17 · Zbl 1325.15007 · doi:10.1016/j.aml.2015.01.003 |
| [16] | Krejic N, Jerinkic NK, Rapajic S (2015) Barzilai-Borwein method with variable sample size for stochastic linear complementarity problems. Optimization 65(2):479-499 · Zbl 1332.90304 · doi:10.1080/02331934.2015.1062008 |
| [17] | Li CB, Yin W, Jiang H, Zhang Y (2013) An efficient augmented Lagrangian method with applications to total variation minimization. Comput Optim Appl 56(3):507-530 · Zbl 1287.90066 · doi:10.1007/s10589-013-9576-1 |
| [18] | Li C, Zhang Y, Yin W http://www.caam.rice.edu/ optimization/L1/TVAL3/ |
| [19] | Liu ZX, Liu HW (2018a) An efficient gradient method with approximate optimal stepsize for large-scale unconstrained optimization. Numer Algorithms. 78(1):21-39 · Zbl 1397.90270 · doi:10.1007/s11075-017-0365-2 |
| [20] | Liu ZX, Liu HW (2018b) Several efficient gradient methods with approximate optimal stepsizes for large scale unconstrained optimization. J Comput Appl Math. 328:400-413 · Zbl 1380.90256 · doi:10.1016/j.cam.2017.07.035 |
| [21] | Liu ZX, Liu HW, Dong XL (2018) An efficient gradient method with approximate optimal stepsize for the strictly convex quadratic minimization problem. Optimization 67(3):427-440 · Zbl 1398.90117 · doi:10.1080/02331934.2017.1399392 |
| [22] | Molina B, Raydan M (1996) Preconditioned Barzilai-Borwein method for the numerical solution of partial differential equations. Numer. Algorithms 13(1):45-60 · Zbl 0861.65025 · doi:10.1007/BF02143126 |
| [23] | Nesterov Y (2005) Smooth minimization of non-smooth functions. Math Program 103(1):127-152 · Zbl 1079.90102 · doi:10.1007/s10107-004-0552-5 |
| [24] | Osher S, Burger M, Goldfarb D, Xu JJ, Yin WT (2005) An iterative regularization method for total variation based image restoration. SIAM J Multiscale Model Simul 4(2):460-489 · Zbl 1090.94003 · doi:10.1137/040605412 |
| [25] | Raydan M (1993) On the Barzilai and Borwein choice of steplength for the gradient method. IMA J Numer Anal 13(3):321-326 · Zbl 0778.65045 · doi:10.1093/imanum/13.3.321 |
| [26] | Raydan M (1997) The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J Optim 7(1):26-33 · Zbl 0898.90119 · doi:10.1137/S1052623494266365 |
| [27] | Rudin L, Osher S, Fatemi E (1992) Nonlinear total variation based noise removal algorithms. Phys D Nonlinear Phenom 60(1-4):259-268 · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F |
| [28] | Sopyla K, Drozda P (2015) Stochastic gradient descent with Barzilai-Borwein update step for SVM. Inf Sci 316:218-233 · Zbl 1390.68555 · doi:10.1016/j.ins.2015.03.073 |
| [29] | Wang YL, Yang JF, Yin WT, Zhang Y (2008) A new alternating minimization algorithm for total variation image reconstruction. SIAM J Imaging Sci 1(3):248-272 · Zbl 1187.68665 · doi:10.1137/080724265 |
| [30] | Wright SJ, Nowak RD, Figueiredo MAT (2009) Sparse reconstruction by separable approximation. IEEE Trans Signal Process 57(7):3373-3376 · Zbl 1391.94442 · doi:10.1109/TSP.2009.2016892 |
| [31] | Yuan YX, Sun WY (1999) Theory and methods of optimization. Science Press of China, Beijing |
| [32] | Zhang HC, Hager WW (2004) A nonmonotone line search technique and its application to unconstrained optimization. SIAM J Optim 14:1043-1056 · Zbl 1073.90024 · doi:10.1137/S1052623403428208 |
| [33] | Zheng YT, Zheng B (2017) A new modified Barzilai-Borwein gradient method for the quadratic minimization problem. J Optim Theory Appl 172(1):179-186 · Zbl 1358.65039 · doi:10.1007/s10957-016-1008-9 |
| [34] | Zhou B, Gao L, Dai YH (2006) Gradient methods with adaptive stepsizes. Comput Optim Appl 35(1):69-86 · Zbl 1121.90099 · doi:10.1007/s10589-006-6446-0 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
