A nonmonotone ADMM-based diagonal quasi-Newton update with application to the compressive sensing problem
Abstract
Considering a minimization problem according to the Byrd-Nocedal measure function together with the secant equation, a diagonal quasi-Newton updating formula is suggested. To find the optimal elements of the updating matrix, the well-known algorithm of the alternating direction method of multipliers (ADMM) is employed. Moreover, convergence analysis is conducted based on a modified nonmonotone Armijo line search incorporating the simulated annealing strategy. Lastly, performance of the method is numerically tested on a set of CUTEr functions and on a smooth transcendental approximation of the compressive sensing problem. Across the computational spectrum, the given method turns out to be successful.
Keyword : large-scale optimization, quasi-Newton update, ADMM strategy, nonmonotone line search, simulated annealing, compressive sensing, smoothing technique
How to Cite
Aminifard, Z., & Babaie-Kafaki, S. (2023). A nonmonotone ADMM-based diagonal quasi-Newton update with application to the compressive sensing problem. Mathematical Modelling and Analysis, 28(4), 673–688. https://doi.org/10.3846/mma.2023.16993
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
K. Amini and A. Ghorbani Rizi. A new structured quasi-Newton algorithm using partial information on Hessian. J. Comput. Appl. Math., 234(3):805–811, 2010. https://doi.org/10.1016/j.cam.2010.01.044
Z. Aminifard and S. Babaie-Kafaki. A modified descent Polak–Ribi`ere–Polyak conjugate gradient method with global convergence property for nonconvex functions. Calcolo, 56(2):16, 2019. https://doi.org/10.1007/s10092-019-0312-9
Z. Aminifard and S. Babaie-Kafaki. Diagonally scaled memoryless quasi-Newton methods with application to compressed sensing. J. Ind. Manag. Optim., 19(1):437–455, 2023. https://doi.org/10.3934/jimo.2021191
Z. Aminifard, A. Hosseini and S. Babaie-Kafaki. Modified conjugate gradient method for solving sparse recovery problem with nonconvex penalty. Signal Process., 193:108424, 2022. https://doi.org/10.1016/j.sigpro.2021.108424
N. Andrei. Convex functions. Adv. Model. Optim., 9(2):257–267, 2007.
N. Andrei. A diagonal quasi-Newton updating method based on minimizing the measure function of Byrd and Nocedal for unconstrained optimization. Optimization, 67(9):1553–1568, 2018. https://doi.org/10.1080/02331934.2018.1482298
N. Andrei. Diagonal approximation of the Hessian by finite differences for unconstrained optimization. J. Optim. Theory Appl., 185(3):859–879, 2020. https://doi.org/10.1007/s10957-020-01676-z
S. Babaie-Kafaki. On optimality of the parameters of self-scaling memoryless quasi-Newton updating formulae. J. Optim. Theory Appl., 167(1):91–101, 2015. https://doi.org/10.1007/s10957-015-0724-x
S. Babaie-Kafaki. A monotone preconditioned gradient method based on a banded tridiagonal inverse Hessian approximation. Univ. Politechnica Bucharest Sci. Bull. Ser. A: Appl. Math. Phys., 80(1):55–62, 2018.
S. Babaie-Kafaki and Z. Aminifard. Two-parameter scaled memoryless BFGS methods with a nonmonotone choice for the initial step length. Numer. Algor., 82(4):1345–1357, 2019. https://doi.org/10.1007/s11075-019-00658-1
S. Babaie-Kafaki, Z. Aminifard and S. Ghafoori. Nonmonotone diagonally scaled limited-memory BFGS methods with application to compressive sensing based on a penalty model. Appl. Numer. Math., 181:618–629, 2022. https://doi.org/10.1016/j.apnum.2022.07.008
S. Babaie-Kafaki and R. Ghanbari. A linear hybridization of the Hestenes–Stiefel method and the memoryless BFGS technique. Mediterr. J. Math., 15:86, 2018. https://doi.org/10.1007/s00009-018-1132-x
Y.J. Bagul. A smooth transcendental approximation to |x|. Inter. J. Math. Sci. & Engg. Appls., 11(II):213–217, 2017.
J. Barzilai and J.M. Borwein. Two-point stepsize gradient methods. IMA J. Numer. Anal., 8(1):141–148, 1988. https://doi.org/10.1093/imanum/8.1.141
D. Bertsimas and J.N. Tsitsiklis. Introduction to Linear Optimization. Athena Scientific, Massachusetts, 1997.
A.M. Bruckstein, D.L. Donoho and M. Elad. From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev., 51(1):34–81, 2009. https://doi.org/10.1137/060657704
R.H. Byrd and J. Nocedal. A tool for the analysis of quasi-Newton methods with application to unconstrained minimization. SIAM J. Numer. Anal., 26(3):727– 739, 1989. https://doi.org/10.1137/0726042
X. Chen. Smoothing methods for nonsmooth, nonconvex minimization. Math. Programming, 134:71–99, 2012. https://doi.org/10.1007/s10107-012-0569-0
Y.H. Dai and L.Z. Liao. New conjugacy conditions and related nonlinear conjugate gradient methods. Appl. Math. Optim., 43(1):87–101, 2001. https://doi.org/10.1007/s002450010019
J.E. Dennis, Jr. and H. Wolkowicz. Sizing and least-change secant methods. SIAM J. Numer. Anal., 30(5):1291–1314, 1993. https://doi.org/10.1137/0730067
E.D. Dolan and J.J. Moré. Benchmarking optimization software with performance profiles. Math. Programming, 91(2, Ser. A):201–213, 2002. https://doi.org/10.1007/s101070100263
W.L. Dong, X. Li and Z. Peng. A simulated annealing-based Barzilai-Borwein gradient method for unconstrained optimization problems. Asia–Pac. J. Oper. Res., 36(4):1950017, 2019. https://doi.org/10.1142/S0217595919500179
N.I.M. Gould, D. Orban and Ph.L. Toint. CUTEr: a constrained and unconstrained testing environment, revisited. ACM Trans. Math. Software, 29(4):373– 394, 2003. https://doi.org/10.1145/962437.962439
L. Grippo, F. Lampariello and S. Lucidi. A nonmonotone line search technique for Newton’s method. SIAM J. Numer. Anal., 23(4):707–716, 1986. https://doi.org/10.1137/0723046
W.W. Hager and H. Zhang. Algorithm 851: CG−Descent, a conjugate gradient method with guaranteed descent. ACM Trans. Math. Software, 32(1):113–137, 2006. https://doi.org/10.1145/1132973.1132979
L. Han, G. Yu and L. Guan. Multivariate spectral gradient method for unconstrained optimization. Appl. Math. Comput., 201(1-2):621–630, 2008. https://doi.org/10.1016/j.amc.2007.12.054
M.A. Hassan, W.J. Leong and M. Farid. A new gradient method via quasiCauchy relation which guarantees descent. J. Comput. Appl. Math., 230(1):300– 305, 2009. https://doi.org/10.1016/j.cam.2008.11.013
P.J. Huber. Robust regression: asymptotics, conjectures and Monte Carlo. Ann. Stat., 1(5):799–821, 1973. https://doi.org/10.1214/aos/1176342503
W.J. Leong, M. Farid and M.A. Hassan. Scaling on diagonal quasi-Newton update for large-scale unconstrained optimization. B. Malays. Math. Sci. So., 35(2):247–256, 2012.
D.H. Li and M. Fukushima. On the global convergence of the BFGS method for nonconvex unconstrained optimization problems. SIAM J. Optim., 11(4):1054– 1064, 2001. https://doi.org/10.1137/S1052623499354242
Y. Nesterov. Smooth minimization of nonsmooth functions. Math. Programming, 103(1):127–152, 2005. https://doi.org/10.1007/s10107-004-0552-5
A.M. Nezhad, R.A. Shandiz and A.E. Jahromi. A particle swarm-BFGS algorithm for nonlinear programming problems. Comput. Oper. Res., 40(4):963–972, 2013. https://doi.org/10.1016/j.cor.2012.11.008
S.S. Oren and D.G. Luenberger. Self-scaling variable metric (SSVM) algorithms. I. Criteria and sufficient conditions for scaling a class of algorithms. Management Sci., 20(5):845–862, 1973. https://doi.org/10.1287/mnsc.20.5.845
S.S. Oren and E. Spedicato. Optimal conditioning of self-scaling variable metric algorithms. Math. Programming, 10(1):70–90, 1976. https://doi.org/10.1007/BF01580654
W. Sun and Y.X. Yuan. Optimization Theory and Methods: Nonlinear Programming. Springer, New York, 2006.
Z. Wei, G. Li and L. Qi. New quasi-Newton methods for unconstrained optimization problems. Appl. Math. Comput., 175(2):1156–1188, 2006. https://doi.org/10.1016/j.amc.2005.08.027
C. Xu and J.Z. Zhang. A survey of quasi-Newton equations and quasi-Newton methods for optimization. Ann. Oper. Res., 103(1–4):213–234, 2001.
Y. Xu, M. Liu, Q. Lin and T. Yang. ADMM without a fixed penalty parameter: faster convergence with new adaptive penalization. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan and R. Garnett (Eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
H. Zhang and W.W. Hager. A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optim., 14(4):1043–1056, 2004. https://doi.org/10.1137/S1052623403428208
M. Zhu, J.L. Nazareth and H. Wolkowicz. The quasi-Cauchy relation and diagonal updating. SIAM J. Optim., 9(4):1192–1204, 1999. https://doi.org/10.1137/S1052623498331793
Z. Aminifard and S. Babaie-Kafaki. A modified descent Polak–Ribi`ere–Polyak conjugate gradient method with global convergence property for nonconvex functions. Calcolo, 56(2):16, 2019. https://doi.org/10.1007/s10092-019-0312-9
Z. Aminifard and S. Babaie-Kafaki. Diagonally scaled memoryless quasi-Newton methods with application to compressed sensing. J. Ind. Manag. Optim., 19(1):437–455, 2023. https://doi.org/10.3934/jimo.2021191
Z. Aminifard, A. Hosseini and S. Babaie-Kafaki. Modified conjugate gradient method for solving sparse recovery problem with nonconvex penalty. Signal Process., 193:108424, 2022. https://doi.org/10.1016/j.sigpro.2021.108424
N. Andrei. Convex functions. Adv. Model. Optim., 9(2):257–267, 2007.
N. Andrei. A diagonal quasi-Newton updating method based on minimizing the measure function of Byrd and Nocedal for unconstrained optimization. Optimization, 67(9):1553–1568, 2018. https://doi.org/10.1080/02331934.2018.1482298
N. Andrei. Diagonal approximation of the Hessian by finite differences for unconstrained optimization. J. Optim. Theory Appl., 185(3):859–879, 2020. https://doi.org/10.1007/s10957-020-01676-z
S. Babaie-Kafaki. On optimality of the parameters of self-scaling memoryless quasi-Newton updating formulae. J. Optim. Theory Appl., 167(1):91–101, 2015. https://doi.org/10.1007/s10957-015-0724-x
S. Babaie-Kafaki. A monotone preconditioned gradient method based on a banded tridiagonal inverse Hessian approximation. Univ. Politechnica Bucharest Sci. Bull. Ser. A: Appl. Math. Phys., 80(1):55–62, 2018.
S. Babaie-Kafaki and Z. Aminifard. Two-parameter scaled memoryless BFGS methods with a nonmonotone choice for the initial step length. Numer. Algor., 82(4):1345–1357, 2019. https://doi.org/10.1007/s11075-019-00658-1
S. Babaie-Kafaki, Z. Aminifard and S. Ghafoori. Nonmonotone diagonally scaled limited-memory BFGS methods with application to compressive sensing based on a penalty model. Appl. Numer. Math., 181:618–629, 2022. https://doi.org/10.1016/j.apnum.2022.07.008
S. Babaie-Kafaki and R. Ghanbari. A linear hybridization of the Hestenes–Stiefel method and the memoryless BFGS technique. Mediterr. J. Math., 15:86, 2018. https://doi.org/10.1007/s00009-018-1132-x
Y.J. Bagul. A smooth transcendental approximation to |x|. Inter. J. Math. Sci. & Engg. Appls., 11(II):213–217, 2017.
J. Barzilai and J.M. Borwein. Two-point stepsize gradient methods. IMA J. Numer. Anal., 8(1):141–148, 1988. https://doi.org/10.1093/imanum/8.1.141
D. Bertsimas and J.N. Tsitsiklis. Introduction to Linear Optimization. Athena Scientific, Massachusetts, 1997.
A.M. Bruckstein, D.L. Donoho and M. Elad. From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev., 51(1):34–81, 2009. https://doi.org/10.1137/060657704
R.H. Byrd and J. Nocedal. A tool for the analysis of quasi-Newton methods with application to unconstrained minimization. SIAM J. Numer. Anal., 26(3):727– 739, 1989. https://doi.org/10.1137/0726042
X. Chen. Smoothing methods for nonsmooth, nonconvex minimization. Math. Programming, 134:71–99, 2012. https://doi.org/10.1007/s10107-012-0569-0
Y.H. Dai and L.Z. Liao. New conjugacy conditions and related nonlinear conjugate gradient methods. Appl. Math. Optim., 43(1):87–101, 2001. https://doi.org/10.1007/s002450010019
J.E. Dennis, Jr. and H. Wolkowicz. Sizing and least-change secant methods. SIAM J. Numer. Anal., 30(5):1291–1314, 1993. https://doi.org/10.1137/0730067
E.D. Dolan and J.J. Moré. Benchmarking optimization software with performance profiles. Math. Programming, 91(2, Ser. A):201–213, 2002. https://doi.org/10.1007/s101070100263
W.L. Dong, X. Li and Z. Peng. A simulated annealing-based Barzilai-Borwein gradient method for unconstrained optimization problems. Asia–Pac. J. Oper. Res., 36(4):1950017, 2019. https://doi.org/10.1142/S0217595919500179
N.I.M. Gould, D. Orban and Ph.L. Toint. CUTEr: a constrained and unconstrained testing environment, revisited. ACM Trans. Math. Software, 29(4):373– 394, 2003. https://doi.org/10.1145/962437.962439
L. Grippo, F. Lampariello and S. Lucidi. A nonmonotone line search technique for Newton’s method. SIAM J. Numer. Anal., 23(4):707–716, 1986. https://doi.org/10.1137/0723046
W.W. Hager and H. Zhang. Algorithm 851: CG−Descent, a conjugate gradient method with guaranteed descent. ACM Trans. Math. Software, 32(1):113–137, 2006. https://doi.org/10.1145/1132973.1132979
L. Han, G. Yu and L. Guan. Multivariate spectral gradient method for unconstrained optimization. Appl. Math. Comput., 201(1-2):621–630, 2008. https://doi.org/10.1016/j.amc.2007.12.054
M.A. Hassan, W.J. Leong and M. Farid. A new gradient method via quasiCauchy relation which guarantees descent. J. Comput. Appl. Math., 230(1):300– 305, 2009. https://doi.org/10.1016/j.cam.2008.11.013
P.J. Huber. Robust regression: asymptotics, conjectures and Monte Carlo. Ann. Stat., 1(5):799–821, 1973. https://doi.org/10.1214/aos/1176342503
W.J. Leong, M. Farid and M.A. Hassan. Scaling on diagonal quasi-Newton update for large-scale unconstrained optimization. B. Malays. Math. Sci. So., 35(2):247–256, 2012.
D.H. Li and M. Fukushima. On the global convergence of the BFGS method for nonconvex unconstrained optimization problems. SIAM J. Optim., 11(4):1054– 1064, 2001. https://doi.org/10.1137/S1052623499354242
Y. Nesterov. Smooth minimization of nonsmooth functions. Math. Programming, 103(1):127–152, 2005. https://doi.org/10.1007/s10107-004-0552-5
A.M. Nezhad, R.A. Shandiz and A.E. Jahromi. A particle swarm-BFGS algorithm for nonlinear programming problems. Comput. Oper. Res., 40(4):963–972, 2013. https://doi.org/10.1016/j.cor.2012.11.008
S.S. Oren and D.G. Luenberger. Self-scaling variable metric (SSVM) algorithms. I. Criteria and sufficient conditions for scaling a class of algorithms. Management Sci., 20(5):845–862, 1973. https://doi.org/10.1287/mnsc.20.5.845
S.S. Oren and E. Spedicato. Optimal conditioning of self-scaling variable metric algorithms. Math. Programming, 10(1):70–90, 1976. https://doi.org/10.1007/BF01580654
W. Sun and Y.X. Yuan. Optimization Theory and Methods: Nonlinear Programming. Springer, New York, 2006.
Z. Wei, G. Li and L. Qi. New quasi-Newton methods for unconstrained optimization problems. Appl. Math. Comput., 175(2):1156–1188, 2006. https://doi.org/10.1016/j.amc.2005.08.027
C. Xu and J.Z. Zhang. A survey of quasi-Newton equations and quasi-Newton methods for optimization. Ann. Oper. Res., 103(1–4):213–234, 2001.
Y. Xu, M. Liu, Q. Lin and T. Yang. ADMM without a fixed penalty parameter: faster convergence with new adaptive penalization. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan and R. Garnett (Eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
H. Zhang and W.W. Hager. A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optim., 14(4):1043–1056, 2004. https://doi.org/10.1137/S1052623403428208
M. Zhu, J.L. Nazareth and H. Wolkowicz. The quasi-Cauchy relation and diagonal updating. SIAM J. Optim., 9(4):1192–1204, 1999. https://doi.org/10.1137/S1052623498331793