Inexact proximal memoryless quasi-Newton methods based on the Broyden family for minimizing composite functions | Computational Optimization and Applications Skip to main content
Springer Nature Link
Log in

Inexact proximal memoryless quasi-Newton methods based on the Broyden family for minimizing composite functions

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

This study considers a proximal Newton-type method to solve the minimization of a composite function that is the sum of a smooth nonconvex function and a nonsmooth convex function. In general, the method uses the Hessian matrix of the smooth portion of the objective function or its approximation. The uniformly positive definiteness of the matrix plays an important role in establishing the global convergence of the method. In this study, an inexact proximal memoryless quasi-Newton method is proposed based on the memoryless Broyden family with the modified spectral scaling secant condition. The proposed method inexactly solves the subproblems to calculate scaled proximal mappings. The approximation matrix is shown to retain the uniformly positive definiteness and the search direction is a descent direction. Using these properties, the proposed method is shown to have global convergence for nonconvex objective functions. Furthermore, the R-linear convergence for strongly convex objective functions is proved. Finally, some numerical results are provided.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Al-Baali, M.: On measure functions for the self-scaling updating formulae for quasi-Newton methods. Optimization 32, 59–69 (1995)

    Article  MathSciNet  Google Scholar 

  2. Beck, A.: First-Order Method in Optimization, MOS-SIAM Series on Optimization. SIAM, New Delhi (2017)

    Book  Google Scholar 

  3. Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imag. Sci. 2, 183–202 (2009)

    Article  MathSciNet  Google Scholar 

  4. Becker, S., Candés, E.J., Grant, M.C.: Templates for convex cone problems with applications to sparse signal recovery. Math. Program. Comput. 3, 165–218 (2011)

    Article  MathSciNet  Google Scholar 

  5. Becker, S., Candés, E.J., Grant M.C.: TFOCS website. http://cvxr.com/tfocs/download/ (latest access: Jun 5, 2020)

  6. Becker, S., Fadili, J., Ochs, P.: On quasi-newton forward-backward splitting: proximal calculus and convergence. SIAM J. Optim. 29, 2445–2481 (2019)

    Article  MathSciNet  Google Scholar 

  7. Bradley, P.S., Mangasarian, O.L.: Massive data discrimination via linear support vector machines. Optim. Methods Softw. 13, 1–10 (2000)

    Article  MathSciNet  Google Scholar 

  8. Chang, C.C., Lin, C.J.: LIBSVM: a library for support vector machines. ACM Trans. Intell. Syst. Technol. 2, 1–27 (2011)

    Article  Google Scholar 

  9. Chang, C.C., Lin, C.J.: LIBSVM data: classification, regression, and multi-label. https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/ (latest access: Jun 5, 2020)

  10. Cheng, W.Y., Li, D.H.: Spectral scaling BFGS method. J. Optim. Theory Appl. 146, 305–319 (2010)

    Article  MathSciNet  Google Scholar 

  11. Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)

    Article  MathSciNet  Google Scholar 

  12. Fukushima, M., Mine, H.: A generalized proximal point algorithm for certain non-convex minimization problems. Int. J. Syst. Sci. 12, 989–1000 (1981)

    Article  Google Scholar 

  13. Gibbons, L.E., Hearn, D.W., Pardalos, P.M., Ramana, M.V.: Continuous characterizations of the maximal clique problem. Math. Oper. Res. 22, 754–768 (1997)

    Article  MathSciNet  Google Scholar 

  14. Hoshino, S.: A formulation of variable metric methods. IMA J. Appl. Math. 10, 394–403 (1972)

    Article  MathSciNet  Google Scholar 

  15. Koh, K., Kim, S.J., Boyd, S.: An interior-point method for large-scale \(\ell _1\)-regularized logistic regression. J. Mach. Learn. Res. 8, 1519–1555 (2007)

    MathSciNet  MATH  Google Scholar 

  16. Kou, C.X., Dai, Y.H.: A modified self-scaling memoryless Broyden–Fletcher–Goldfarb–Shanno method for unconstrained optimization. J. Optim. Theory Appl. 165, 209–224 (2015)

    Article  MathSciNet  Google Scholar 

  17. Lee, J.D., Sun, Y., Saunders, M.: Proximal Newton-type methods for minimizing composite functions. SIAM J. Optim. 24, 1420–1443 (2014)

    Article  MathSciNet  Google Scholar 

  18. Lee, J.D., Sun, Y., Saunders, M.A.: PNOPT website. https://web.stanford.edu/group/SOL/software/pnopt/ (latest access: Jun 5, 2020)

  19. Li, J., Andersen, M.S., Vandenberghe, L.: Inexact proximal Newton methods for self-concordant functions. Math. Methods Oper. Res. 85, 19–41 (2017)

    Article  MathSciNet  Google Scholar 

  20. Li, D.H., Fukushima, M.: A modified BFGS method and its global convergence in nonconvex minimization. J. Comput. Appl. Math. 129, 15–35 (2001)

    Article  MathSciNet  Google Scholar 

  21. Liu, X., Hsieh, C.J., Lee, J.D., Sun, Y.: An inexact subsampled proximal Newton-type method for large-scale machine learning. arXiv:1708.08552 (2017)

  22. Markowitz, H.: Portfolio selection. J. Financ. 7, 77–91 (1952)

    Google Scholar 

  23. Modarres, F., Hassan, M.A., Leong, W.J.: Memoryless modified symmetric rank-one method for large-scale unconstrained optimization. Am. J. Appl. Sci. 6, 2054–2059 (2009)

    Article  Google Scholar 

  24. Moyi, A.U., Leong, W.J.: A sufficient descent three-term conjugate gradient method via symmetric rank-one update for large-scale optimization. Optimization 65, 121–143 (2016)

    Article  MathSciNet  Google Scholar 

  25. Nakayama, S.: A hybrid method of three-term conjugate gradient method and memoryless quasi-Newton method for unconstrained optimization. SUT J. Math. 54, 79–98 (2018)

    MathSciNet  MATH  Google Scholar 

  26. Nakayama, S., Narushima, Y., Yabe, H.: A memoryless symmetric rank-one method with sufficient descent property for unconstrained optimization. J. Oper. Res. Soc. Jpn. 61, 53–70 (2018)

    MathSciNet  MATH  Google Scholar 

  27. Nakayama, S., Narushima, Y., Yabe, H.: Memoryless quasi-Newton methods based on spectral-scaling Broyden family for unconstrained optimization. J. Ind. Manag. Optim. 15, 1773–1793 (2019)

    MathSciNet  MATH  Google Scholar 

  28. Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course, 87. Springer, Berlin (2003)

    Google Scholar 

  29. Scheinberg, K., Tang, X.: Practical inexact proximal quasi-Newton method with global complexity analysis. Math. Program. 160, 495–529 (2016)

    Article  MathSciNet  Google Scholar 

  30. Shanno, D.F.: Conjugate gradient methods with inexact searches. Math. Oper. Res. 3, 244–256 (1978)

    Article  MathSciNet  Google Scholar 

  31. Shevade, S.K., Keerthi, S.S.: A simple and efficient algorithm for gene selection using sparse logistic regression. Bioinformatics 19, 2246–2253 (2003)

    Article  Google Scholar 

  32. Stella, L., Themelis, A., Patrinos, P.: Forward-backward quasi-Newton methods for nonsmooth optimization problems. Comput. Optim. Appl. 67, 443–487 (2017)

    Article  MathSciNet  Google Scholar 

  33. Sun, W., Yuan, Y.: Optimization Theory and Methods: Nonlinear Programming. Springer, Berlin (2006)

    MATH  Google Scholar 

  34. Themelis, A., Stella, L., Patrinos, P.: Forward-backward envelope for the sum of two nonconvex functions: further properties and nonmonotone linesearch algorithms. SIAM J. Optim. 28, 2274–2303 (2018)

    Article  MathSciNet  Google Scholar 

  35. Themelis, A., Ahookhosh, M., Patrinos, P.: On the acceleration of forward-backward splitting via an inexact Newton method. In: Bauschke, H.H., Burachik, R.S., Luke, D.R. (eds.) Splitting Algorithms, Modern Operator Theory, and Applications, pp. 363–412. Springer, Cham (2019)

    Chapter  Google Scholar 

  36. Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. B 58, 267–288 (1996)

    MathSciNet  MATH  Google Scholar 

  37. Tibshirani, R.: Regression shrinkage and selection via the lasso: a retrospective. J. R. Stat. Soc. Ser. B 73, 273–282 (2011)

    Article  MathSciNet  Google Scholar 

  38. Wen, B., Chen, X., Pong, T.K.: Linear convergence of proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth minimization problems. SIAM J. Optim. 27, 124–145 (2017)

    Article  MathSciNet  Google Scholar 

  39. Wright, S.J., Nowak, R.D., Figueiredo, M.A.T.: Sparse reconstruction by separable approximation. IEEE Trans. Signal Process. 57, 2479–2493 (2009)

    Article  MathSciNet  Google Scholar 

  40. Yuan, M.M., Lin, Y.: Model selection and estimation in regression with grouped variables. J. R. Stat. Soc. Ser. B 68, 49–67 (2006)

    Article  MathSciNet  Google Scholar 

  41. Zhang, Y., Tewarson, P.: Quasi-Newton algorithms with updates from the preconvex part of Broyden’s family. IMA J. Numer. Anal. 8, 487–509 (1988)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This research was supported in part by JSPS KAKENHI (Grant Numbers 18K11179, 20K11698 and 20K14986) and the Research Institute for Mathematical Sciences in Kyoto University.

Author information

Authors and Affiliations

  1. Department of Industrial and Systems Engineering, Chuo University, Tokyo, Japan

    Shummin Nakayama

  2. Department of Industrial and Systems Engineering, Keio University, Yokohama, Japan

    Yasushi Narushima

  3. Department of Applied Mathematics, Tokyo University of Science, Tokyo, Japan

    Hiroshi Yabe

Authors
  1. Shummin Nakayama
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yasushi Narushima
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hiroshi Yabe
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shummin Nakayama.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Nakayama, S., Narushima, Y. & Yabe, H. Inexact proximal memoryless quasi-Newton methods based on the Broyden family for minimizing composite functions. Comput Optim Appl 79, 127–154 (2021). https://doi.org/10.1007/s10589-021-00264-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-021-00264-9

Keywords

Search

Navigation