Advanced Search
Article Contents
Article Contents
Early Access

Early Access articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Early Access publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Early Access articles via the “Early Access” tab for the selected journal.

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

  • *Corresponding author: Yasushi Narushima

    *Corresponding author: Yasushi Narushima 

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

Abstract Full Text(HTML) Figure(3) / Table(3) Related Papers Cited by
  • 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.

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


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Performance profiles for all tested problems

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

    Figure 3.  Performance profiles for the tested problems generated randomly

    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
  • [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. BeckerE. 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. BeckerJ. 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. LeeY. 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. NakayamaY. 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. NakayamaY. 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. NakayamaY. 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. OchsY. ChenT. 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. ThemelisL. 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 BergM. P. FriedlanderG. HennenfentF. J. HerrmannR. Saab and Ö. Yilmaz, Algorithm 890: Sparco: A testing framework for sparse reconstruction, ACM Trans. Math. Softw., 35 (2009), 1-16. 
    [36] B. WenX. 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. WrightR. 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.
  • 加载中




Article Metrics

HTML views(144) PDF downloads(151) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint