A proximal quasi-Newton method based on memoryless modified symmetric rank-one formula

Yasushi Narushima; Shummin Nakayama

doi:10.3934/jimo.2022123

Article Contents

2023, Volume 19, Issue 6: 4095-4111. Doi: 10.3934/jimo.2022123

This issue Previous Article Differential decision of low-carbon supply chain based on market preferences with fairness concerns Next Article A new model to design the suppliers portfolio in newsvendor problem based on product reliability

A proximal quasi-Newton method based on memoryless modified symmetric rank-one formula

Yasushi Narushima^1, , and
Shummin Nakayama^2,

1.
Department of Industrial and Systems Engineering, Keio University, 3-14-1 Hiyoshi, Kouhoku-ku, Yokohama 223-8522, Japan
2.
Department of Data Science for Business Innovation, Chuo University, 1-13-27 Kasuga, Bunkyo-ku, Tokyo 112-8551, Japan

^*Corresponding author: Yasushi Narushima
^*Corresponding author: Yasushi Narushima

Received: May 2021

Revised: April 2022

Early access: July 28, 2022

Published online: July 28, 2022

This research was supported by JSPS KAKENHI (grant numbers JP18K11179, JP20K11698, and JP20K14986).

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

Abstract

We consider proximal gradient methods for minimizing a composite function of a differentiable function and a convex function. To accelerate the general proximal gradient methods, we focus on proximal quasi-Newton type methods based on proximal mappings scaled by quasi-Newton matrices. Although it is usually difficult to compute the scaled proximal mappings, applying the memoryless symmetric rank-one (SR1) formula makes this easier. Since the scaled (quasi-Newton) matrices must be positive definite, we develop an algorithm using the memoryless SR1 formula based on a modified spectral scaling secant condition. We give the subsequential convergence property of the proposed method for general objective functions. In addition, we show the R-linear convergence property of the method under a strong convexity assumption. Finally, some numerical results are reported.

Keywords:

Mathematics Subject Classification: Primary: 90C30, 90C53, 90C06; Secondary: 65K05.

Citation:

Full Text(HTML)

Figure 1. Performance profiles for all tested problems

Download: Full-size image PowerPoint slide

Figure 2. Performance profiles for the tested problems from Sparco library

Download: Full-size image PowerPoint slide

Figure 3. Performance profiles for the tested problems generated randomly

Download: Full-size image PowerPoint slide

Table 1. Information for tested problems from the Sparco library

ID	#sample ($ m $)	dim. ($ n $)
3	1024	2048
5	300	2048
7	600	2560
9	128	128
11	256	1024
902	200	1000
903	1024	1024

| Show Table

DownLoad: CSV

Table 2. Detail of data-sets form [8]

Data name	${\tt gisette\_scale}$	${\tt a9a}$	${\tt leukemia}$
Number of data $ m $	1000	32561	38
Dimension $ n $	5000	123	7129

| Show Table

DownLoad: CSV

Table 3. Numerical results

Data name	${\tt{gisette\_scale}}$		${\tt{a9a}}$		${\tt{leukemia}}$
	Iter	Time	Iter	Time	Iter	Time
PNOPT	262	105.9	26	1.637	1448	166.8
TFOCS	955	81.86	264	2.116	269	1.404
iPiano	180727	10859	2733	11.21	211184	448.1
InMless-BFGS	806	85.36	221	1.195	484	26.57
InMless-SR1	609	87.24	137	0.9600	2388	749.1
ZeroSR1	1186	317.6	170	3.990	660	7.253
Algorithm 1	508	67.32	133	0.5564	474	3.560
Algorithm 1$ {}^\prime $	519	67.93	199	0.8874	713	5.407

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	J. Barzilai and J. M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal., 8 (1988), 141-148. doi: 10.1093/imanum/8.1.141.
[2]	A. Beck, First-Order Method in Optimization, MOS-SIAM Series on Optimization, SIAM, 2017. doi: 10.1137/1.9781611974997.ch1.
[3]	A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), 183-202. doi: 10.1137/080716542.
[4]	S. Becker, E. J. Candés and M. C. Grant, Templates for convex cone problems with applications to sparse signal recovery, Math. Program. Comput., 3 (2011), 165-218. doi: 10.1007/s12532-011-0029-5.
[5]	S. Becker, J. Fadili and P. Ochs, On quasi-Newton forward-backward splitting: Proximal calculus and convergence, SIAM J. Optim., 29 (2019), 2445-2481. doi: 10.1137/18M1167152.
[6]	S. Becker, J. Fadili and P. Ochs, ZeroSR1 Toolbox Website, https://github.com/stephenbeckr/zeroSR1, (last access, May 30, 2022).
[7]	R. I. Boţ, E. R. Csetnek and S. C László, An inertial forward-backward algorithm for the minimization of the sum of two nonconvex functions, EURO J. Comput. Optim., 4 (2016), 3-25. doi: 10.1007/s13675-015-0045-8.
[8]	C. C. Chang and C. J. Lin, LIBSVM: A library for support vector machines, ACM Trans. Intell. Syst. Technol., 2 (2011), 1-27.
[9]	W. Y. Cheng and D. H. Li, Spectral scaling BFGS method, J. Optim. Theory Appl., 146 (2010), 305-319. doi: 10.1007/s10957-010-9652-y.
[10]	P. L. Combettes and J.-C. Pesquet, Proximal splitting methods in signal processing, in Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer Optimization and Its Applications, 49 (eds. H.H. Bauschke, R.S. Burachik, P.L. Combetters, V. Elser, D.R. Luke and H. Wolkowicz), Springer, New York, NY, 2011,185-212. doi: 10.1007/978-1-4419-9569-8_10.
[11]	E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), 201-213. doi: 10.1007/s101070100263.
[12]	W. W. Hager and H. Zhang, A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM J. Optim., 16 (2005), 170-192. doi: 10.1137/030601880.
[13]	W. W. Hager and H. Zhang, Algorithm 851: CG_DESCENT, A conjugate gradient method with guaranteed descent, ACM Trans. Math. Softw., 32 (2006), 113-137. doi: 10.1145/1132973.1132979.
[14]	J. D. Lee, Y. Sun and M. A. Saunders, Proximal Newton-type methods for minimizing composite functions, SIAM J. Optim., 24 (2014), 1420-1443. doi: 10.1137/130921428.
[15]	J. D Lee, Y. Sun and M. A. Saunders, PNOPT website, https://web.stanford.edu/group/SOL/software/pnopt/ (latest access, May 30, 2022).
[16]	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.
[17]	X. Liu, C.-J. Hsieh, J. D. Lee and Y. Sun, An inexact subsampled proximal Newton-type method for large-scale machine learning, preprint, arXiv: 1708.08552, 2017.
[18]	H. Li and Z. Lin, Accelerated proximal gradient methods for nonconvex programming, in Advances in Neural Information Processing Systems, 28 (eds. C. Cortes, N. Lawrence, D.D. Lee, M. Sugiyama and R. Garnett), Neural Information Processing Systems, 2015,379-387.
[19]	A. U. Moyi and W. J. Leong, A sufficient descent three-term conjugate gradient method via symmetric rank-one update for large-scale optimization, Optimization, 65 (2016), 121-143. doi: 10.1080/02331934.2014.994625.
[20]	S. Nakayama, A hybrid method of three-term conjugate gradient method and memoryless quasi-Newton method for unconstrained optimization, SUT J. of Math., 54 (2018), 79-98.
[21]	S. Nakayama and Y. Narushima, Global convergence of a proximal memoryless symmetric rank one method for minimizing composite functions, in Proceedings of the International Conference on Nonlinear Analysis and Convex Analysis & International Conference on Optimization: Techniques and Applications -II-, (eds. Y. Kimura, M. Muramatsu, W. Takahashi, and A. Yoshise), Yokohama Publishers, 2021, 99–108.
[22]	S. Nakayama, Y. Narushima and H. Yabe, A memoryless symmetric rank-one method with sufficient descent property for unconstrained optimization, J. Oper. Res. Soc. Japan., 61 (2018), 53-70. doi: 10.15807/jorsj.61.53.
[23]	S. Nakayama, Y. Narushima and H. Yabe, Memoryless quasi-Newton methods based on spectral-scaling Broyden family for unconstrained optimization, J. Ind. Manag. Optim., 15 (2019), 1773-1793. doi: 10.3934/jimo.2018122.
[24]	S. Nakayama, Y. Narushima and H. Yabe, Inexact proximal memoryless quasi-Newton methods based on the Broyden family for minimizing composite functions, Comput. Optim. Appl., 79 (2021), 127-154. doi: 10.1007/s10589-021-00264-9.
[25]	Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Springer New York, NY, 2003. doi: 10.1007/978-1-4419-8853-9.
[26]	J. Nocedal and S. J. Wright, Numerical optimization, 2$^{nd}$ edition, Springer Series in Operations Research, Springer New York, NY, 2006.
[27]	P. Ochs, Y. Chen, T. Brox and T. Pock, iPiano: Inertial proximal algorithm for nonconvex optimization, SIAM J. Imaging Sci., 7 (2014), 1388-1419. doi: 10.1137/130942954.
[28]	M. R. Osborne and L. Sun, A new approach to the symmetric rank-one updating, IMA J. Numer. Anal., 19 (1999), 497-507. doi: 10.1093/imanum/19.4.497.
[29]	K. Scheinberg and X. Tang, Practical inexact proximal quasi-Newton method with global complexity analysis, Math. Program., 160 (2016), 495-529. doi: 10.1007/s10107-016-0997-3.
[30]	D. F. Shanno, Conjugate gradient methods with inexact searches, Math. Oper. Res., 3 (1978), 244-256. doi: 10.1287/moor.3.3.244.
[31]	L. Stella, A. Themelis and P. Patrinos, Forward-backward quasi-Newton methods for nonsmooth optimization problems, Comput. Optim. Appl., 67 (2017) 443-487. doi: 10.1007/s10589-017-9912-y.
[32]	W. Sun and Y. Yuan, Optimization Theory and Methods: Nonlinear Programming, Springer New York, NY, (2006).
[33]	A. Themelis, L. Stella and P. Patrinos, Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone linesearch algorithms, SIAM J. Optim., 28 (2018), 2274-2303. doi: 10.1137/16M1080240.
[34]	A. Themelis, M. Ahookhosh and P. Patrinos, On the acceleration of forward-backward splitting via an inexact Newton method, in Splitting Algorithms, Modern Operator Theory, and Applications (eds. H. Bauschke, R. S. Burachik and D. R. Luke), Springer, Cham, 2019,363-412.
[35]	E. van den Berg, M. P. Friedlander, G. Hennenfent, F. J. Herrmann, R. Saab and Ö. Yilmaz, Algorithm 890: Sparco: A testing framework for sparse reconstruction, ACM Trans. Math. Softw., 35 (2009), 1-16.
[36]	B. Wen, X. Chen and T. K. Pong, A proximal difference-of-convex algorithm with extrapolation, Comput. Optim. Appl., 69 (2018), 297-324. doi: 10.1007/s10589-017-9954-1.
[37]	S. J. Wright, R. D. Nowak and M. A. T. Figueiredo, Sparse reconstruction by separable approximation, IEEE Trans. Signal Process., 57 (2009), 2479-2493. doi: 10.1109/TSP.2009.2016892.