Diagonally scaled memoryless quasi–Newton methods with application to compressed sensing

Zohre Aminifard; Saman Babaie-Kafaki

doi:10.3934/jimo.2021191

Article Contents

2023, Volume 19, Issue 1: 437-455. Doi: 10.3934/jimo.2021191

This issue Previous Article Bi-objective unrelated parallel machines scheduling problem with worker allocation and sequence dependent setup times considering machine eligibility and precedence constraints Next Article Single-machine Pareto-scheduling with multiple weighting vectors for minimizing the total weighted late works

Diagonally scaled memoryless quasi–Newton methods with application to compressed sensing

Zohre Aminifard^†, and
Saman Babaie-Kafaki^†, ,

†.
Department of Mathematics, Semnan University, P.O. Box: 35195–363, Semnan, Iran

^* Corresponding author: Saman Babaie-Kafaki
^* Corresponding author: Saman Babaie-Kafaki

Received: February 2021

Revised: July 2021

Early access: November 2021

Published: January 2023

Abstract / Introduction Full Text(HTML) Figure(10) Related Papers Cited by

Abstract

Memoryless quasi–Newton updating formulas of BFGS (Broyden–Fletcher–Goldfarb–Shanno) and DFP (Davidon–Fletcher–Powell) are scaled using well-structured diagonal matrices. In the scaling approach, diagonal elements as well as eigenvalues of the scaled memoryless quasi–Newton updating formulas play significant roles. Convergence analysis of the given diagonally scaled quasi–Newton methods is discussed. At last, performance of the methods is numerically tested on a set of CUTEr problems as well as the compressed sensing problem.

Keywords:

Mathematics Subject Classification: Primary: 90C53, 49M37; Secondary: 94A08.

Citation:

Full Text(HTML)

Figure 1. DM performance profile outputs for DSSD1, DSSD2, DSSD3, DSSD4 and SSD

Download: Full-size image PowerPoint slide

Figure 2. DM performance profile outputs for NMDSSD1, NMDSSD2, NMDSSD3, NMDSSD4 and NMSSD

Download: Full-size image PowerPoint slide

Figure 3. DM performance profile outputs for DSMBFGS1, DSMBFGS2 and SMBFGS

Download: Full-size image PowerPoint slide

Figure 4. DM performance profile outputs for DSMDFP1, DSMDFP2 and SMDFP

Download: Full-size image PowerPoint slide

Figure 5. DM performance profile outputs for DSMBFGS1, LMBFGS, TPSMBFGS, MLBFGSCG1 and MLBFGSCG2

Download: Full-size image PowerPoint slide

Figure 6. Compressed sensing outputs for the Gaussian matrix

Download: Full-size image PowerPoint slide

Figure 7. Compressed sensing outputs for the scaled Gaussian matrix

Download: Full-size image PowerPoint slide

Figure 8. Compressed sensing outputs for the orthogonalized Gaussian matrix

Download: Full-size image PowerPoint slide

Figure 9. Compressed sensing outputs for the Bernoulli matrix

Download: Full-size image PowerPoint slide

Figure 10. Compressed sensing outputs for the Hadamard matrix

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	M. Al-Baali, Numerical experience with a class of self-scaling quasi–Newton algorithms, J. Optim. Theory Appl., 96 (1998), 533-553. doi: 10.1023/A:1022608410710.
[2]	M. Al-Baali and H. Khalfan, A combined class of self-scaling and modified quasi–Newton methods, Comput. Optim. Appl., 52 (2012), 393-408. doi: 10.1007/s10589-011-9415-1.
[3]	M. Al-Baali, E. Spedicato and F. Maggioni, Broyden's quasi–Newton methods for a nonlinear system of equations and unconstrained optimization: A review and open problems, Optim. Methods Softw., 29 (2014), 937-954. doi: 10.1080/10556788.2013.856909.
[4]	S. B. Albert and T. Martin, A robust multi-batch L–BFGS method for machine learning, Optim. Methods Softw., 35 (2020), 191-219. doi: 10.1080/10556788.2019.1658107.
[5]	K. Amini and A. Ghorbani Rizi, A new structured quasi–Newton algorithm using partial information on Hessian, J. Comput. Appl. Math., 234 (2010), 805-811. doi: 10.1016/j.cam.2010.01.044.
[6]	Z. Aminifard and S. Babaie-Kafaki, A modified descent Polak–Ribiére–Polyak conjugate gradient method with global convergence property for nonconvex functions, Calcolo, 56 (2019), 16. doi: 10.1007/s10092-019-0312-9.
[7]	Z. Aminifard, S. Babaie-Kafaki and S. Ghafoori, An augmented memoryless BFGS method based on a modified secant equation with application to compressed sensing, Appl. Numer. Math., 167 (2021), 187-201. doi: 10.1016/j.apnum.2021.05.002.
[8]	N. Andrei, Accelerated scaled memoryless BFGS preconditioned conjugate gradient algorithm for unconstrained optimization, European J. Oper. Res., 204 (2010), 410-420. doi: 10.1016/j.ejor.2009.11.030.
[9]	N. Andrei, A double-parameter scaling Broyden–Fletcher–Goldfarb–Shanno method based on minimizing the measure function of Byrd and Nocedal for unconstrained optimization, J. Optim. Theory Appl., 178 (2018), 191-218. doi: 10.1007/s10957-018-1288-3.
[10]	M. R. Arazm, S. Babaie-Kafaki and R. Ghanbari, An extended Dai–Liao conjugate gradient method with global convergence for nonconvex functions, Glas. Mat. Ser., 52 (2017), 361-375. doi: 10.3336/gm.52.2.12.
[11]	S. Babaie-Kafaki, On optimality of the parameters of self-scaling memoryless quasi–Newton updating formulae, J. Optim. Theory Appl., 167 (2015), 91-101. doi: 10.1007/s10957-015-0724-x.
[12]	S. Babaie-Kafaki, A modified scaling parameter for the memoryless BFGS updating formula, Numer. Algorithms, 72 (2016), 425-433. doi: 10.1007/s11075-015-0053-z.
[13]	S. Babaie-Kafaki, A hybrid scaling parameter for the scaled memoryless BFGS method based on the $\ell_{\infty}$ matrix norm, Int. J. Comput. Math., 96 (2019), 1595-1602. doi: 10.1080/00207160.2018.1465940.
[14]	S. Babaie-Kafaki and Z. Aminifard, Two-parameter scaled memoryless BFGS methods with a nonmonotone choice for the initial step length, Numer. Algorithms, 82 (2019), 1345-1357. doi: 10.1007/s11075-019-00658-1.
[15]	S. Babaie-Kafaki and R. Ghanbari, A modified scaled conjugate gradient method with global convergence for nonconvex functions, Bull. Belg. Math. Soc. Simon Stevin, 21 (2014), 465-477.
[16]	S. Babaie-Kafaki and R. Ghanbari, A linear hybridization of the Hestenes–Stiefel method and the memoryless BFGS technique, Mediterr. J. Math., 15 (2018), 86. doi: 10.1007/s00009-018-1132-x.
[17]	H. Badem, A. Basturk, A. Caliskan and M. E. Yuksel, A new efficient training strategy for deep neural networks by hybridization of artificial bee colony and limited-memory BFGS optimization algorithms, Neurocomputing, 266 (2017), 506-526. doi: 10.1016/j.neucom.2017.05.061.
[18]	M. Bai, J. Zhao and Z. Zhang, A descent cautious BFGS method for computing US-eigenvalues of symmetric complex tensors, J. Global Optim., 76 (2020), 889-911. doi: 10.1007/s10898-019-00843-5.
[19]	J. Barzilai and J. M. Borwein, Two-point stepsize gradient methods, IMA J. Numer. Anal., 8 (1988), 141-148. doi: 10.1093/imanum/8.1.141.
[20]	F. Biglari and A. Ebadian, Limited memory BFGS method based on a high-order tensor model, Comput. Optim. Appl., 60 (2015), 413-422. doi: 10.1007/s10589-014-9678-4.
[21]	M. Borhani, Multi-label Log-Loss function using L–BFGS for document categorization, Eng. Appl. Artif. Intell., 91 (2020), 103623. doi: 10.1016/j.engappai.2020.103623.
[22]	Y. H. Dai and L. Z. Liao, New conjugacy conditions and related nonlinear conjugate gradient methods, Appl. Math. Optim., 43 (2001), 87-101. doi: 10.1007/s002450010019.
[23]	R. Dehghani, N. Bidabadi and M. M. Hosseini, A new modified BFGS method for solving systems of nonlinear equations, J. Interdiscip. Math., 22 (2019), 75-89. doi: 10.1080/09720502.2019.1574065.
[24]	J. E. Dennis, H. J. Martínez and R. A. Tapia, Convergence theory for the structured BFGS secant method with an application to nonlinear least squares, J. Optim. Theory Appl., 61 (1989), 161-178. doi: 10.1007/BF00962795.
[25]	E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Programming, 91 (2002), 201-213. doi: 10.1007/s101070100263.
[26]	A. Ebrahimi and G. B. Loghmani, Shape modeling based on specifying the initial B-spline curve and scaled BFGS optimization method, Multimed. Tools Appl., 77 (2018), 30331-30351. doi: 10.1007/s11042-018-6109-z.
[27]	I. E. Ebrahimi, An advanced active set L–BFGS algorithm for training weight-constrained neural networks, Neural. Comput. Applic., 32 (2020), 6669-6684. doi: 10.1007/s00521-019-04689-6.
[28]	H. Esmaeili, S. Shabani and M. Kimiaei, A new generalized shrinkage conjugate gradient method for sparse recovery, Calcolo, 56 (2019), 38 pp. doi: 10.1007/s10092-018-0296-x.
[29]	J. A. Ford and I. A. Moghrabi, Multi-step quasi–Newton methods for optimization, J. Comput. Appl. Math., 50 (1994), 305-323. doi: 10.1016/0377-0427(94)90309-3.
[30]	N. I. M. Gould, D. Orban and P. L. Toint, CUTEr: A constrained and unconstrained testing environment, revisited, ACM Trans. Math. Software, 29 (2003), 373-394. doi: 10.1145/962437.962439.
[31]	L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique for Newton's method, SIAM J. Numer. Anal., 23 (1986), 707-716. doi: 10.1137/0723046.
[32]	W. W. Hager and H. Zhang, Algorithm 851: CG_Descent, a conjugate gradient method with guaranteed descent, ACM Trans. Math. Software, 32 (2006), 113-137.
[33]	D. H. Li and M. Fukushima, A modified BFGS method and its global convergence in nonconvex minimization, J. Comput. Appl. Math., 129 (2001), 15-35. doi: 10.1016/S0377-0427(00)00540-9.
[34]	D. H. Li and M. Fukushima, On the global convergence of the BFGS method for nonconvex unconstrained optimization problems, SIAM J. Optim., 11 (2001), 1054-1064. doi: 10.1137/S1052623499354242.
[35]	M. Li, A modified Hestense–Stiefel conjugate gradient method close to the memoryless BFGS quasi–Newton method, Optim. Methods Softw., 33 (2018), 336-353. doi: 10.1080/10556788.2017.1325885.
[36]	I. E. Livieris, V. Tampakas and P. Pintelas, A descent hybrid conjugate gradient method based on the memoryless BFGS update, Numer. Algor., 79 (2018), 1169-1185. doi: 10.1007/s11075-018-0479-1.
[37]	L. Z. Lu, M. K. Ng and F. R. Lin, Approximation BFGS methods for nonlinear image restoration, J. Comput. Appl. Math., 226 (2009), 84-91. doi: 10.1016/j.cam.2008.05.056.
[38]	A. Mohammad Nezhad, R. Aliakbari Shandiz and A. Eshraghniaye Jahromi, A particle swarm-BFGS algorithm for nonlinear programming problems, Comput. Oper. Res., 40 (2013), 963-972. doi: 10.1016/j.cor.2012.11.008.
[39]	J. Nocedal and S. J. Wright, Numerical Optimization, 2$^{nd}$ edition, Series in Operations Research and Financial Engineering. Springer, New York, 2006.
[40]	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 (1973/74), 845-862. doi: 10.1287/mnsc.20.5.845.
[41]	S. S. Oren and E. Spedicato, Optimal conditioning of self-scaling variable metric algorithms, Math. Programming, 10 (1976), 70-90. doi: 10.1007/BF01580654.
[42]	C. Shen, C. Fan, Y. Wang and W. Xue, Limited memory BFGS algorithm for the matrix approximation problem in Frobenius norm, Comput. Appl. Math., 39 (2020), 43. doi: 10.1007/s40314-020-1089-9.
[43]	K. Sugiki, Y. Narushima and H. Yabe, Globally convergent three–term conjugate gradient methods that use secant conditions and generate descent search directions for unconstrained optimization, J. Optim. Theory Appl., 153 (2012), 733-757. doi: 10.1007/s10957-011-9960-x.
[44]	W. Sun and Y. X. Yuan, Optimization Theory and Methods: Nonlinear Programming, , Springer Optimization and Its Applications, 1. Springer, New York, 2006.
[45]	Z. Wei, G. Li and L. Qi, New quasi–Newton methods for unconstrained optimization problems, Appl. Math. Comput., 175 (2006), 1156-1188. doi: 10.1016/j.amc.2005.08.027.
[46]	Z. Wei, G. Yu, G. Yuan and Z. Lian, The superlinear convergence of a modified BFGS-type method for unconstrained optimization, Comput. Optim. Appl., 29 (2004), 315-332. doi: 10.1023/B:COAP.0000044184.25410.39.
[47]	C. Xu and J. Z. Zhang, A survey of quasi–Newton equations and quasi–Newton methods for optimization, Ann. Oper. Res., 103 (2001), 213-234. doi: 10.1023/A:1012959223138.
[48]	F. Yang, M. Ding, X. Zhang, W. Hou and C. Zhong, Non-rigid multi-modal medical image registration by combining L–BFGS–B with cat swarm optimization, Inform. Sciences, 316 (2015), 440-456. doi: 10.1016/j.ins.2014.10.051.
[49]	X. Yao and Z. Wang, Broad echo state network for multivariate time series prediction, J. Franklin Inst., 356 (2019), 4888-4906. doi: 10.1016/j.jfranklin.2019.01.027.
[50]	F. Yin, Y. N. Wang and S. N. Wei, Inverse kinematic solution for robot manipulator based on electromagnetism-like and modified DFP algorithms, Acta Automatica Sinica, 37 (2011), 74-82. doi: 10.3724/SP.J.1004.2011.00074.
[51]	X. Yuan, W. Huang, P.-A. Absil and K. A. Gallivan, A Riemannian limited-memory BFGS algorithm for computing the matrix geometric mean, Procedia Comput. Sci., 80 (2016), 2147-2157. doi: 10.1016/j.procs.2016.05.534.
[52]	Y. X. Yuan, A modified BFGS algorithm for unconstrained optimization, IMA J. Numer. Anal., 11 (1991), 325-332. doi: 10.1093/imanum/11.3.325.
[53]	H. Zhang, K. Wang, X. Zhou and W. Wang, Using DFP algorithm for nodal demand estimation of water distribution networks, KSCE J. Civ. Eng., 22 (2018), 2747-2754. doi: 10.1007/s12205-018-0176-6.
[54]	J. Z. Zhang, N. Y. Deng and L. H. Chen, New quasi–Newton equation and related methods for unconstrained optimization, J. Optim. Theory Appl., 102 (1999), 147-167. doi: 10.1023/A:1021898630001.
[55]	W. Zhou, A modified BFGS type quasi–Newton method with line search for symmetric nonlinear equations problems, J. Comput. Appl. Math., 367 (2020), 112454. doi: 10.1016/j.cam.2019.112454.
[56]	W. Zhou and L. Zhang, A nonlinear conjugate gradient method based on the MBFGS secant condition, Optim. Methods Softw., 21 (2006), 707-714. doi: 10.1080/10556780500137041.