Global convergence of proximal iteratively reweighted algorithm | Journal of Global Optimization Skip to main content
Springer Nature Link
Log in

Global convergence of proximal iteratively reweighted algorithm

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

In this paper, we investigate the convergence of the proximal iteratively reweighted algorithm for a class of nonconvex and nonsmooth problems. Such problems actually include numerous models in the area of signal processing and machine learning research. Two extensions of the algorithm are also studied. We provide a unified scheme for these three algorithms. With the Kurdyka–Łojasiewicz property, we prove that the unified algorithm globally converges to a critical point of the objective function.

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

Similar content being viewed by others

References

  1. Chen, X., Ge, D., Wang, Z., et al.: Complexity of unconstrained \(L_2\)-\(L_p\) minimization. Math. Program. 143(1–2), 371–383 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  2. Lai, M.J., Xu, Y., Yin, W.: Improved iteratively reweighted least squares for unconstrained smoothed \(\ell _q\) minimization. SIAM J. Numer. Anal. 51(2), 927–957 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  3. Lu, C., Wei, Y., Lin, Z., Yan, S.: Proximal iteratively reweighted algorithm with multiple splitting for nonconvex sparsity optimization. In: Proceedings of the AAAI Conference on Artificial Intelligence (2014)

  4. Ochs, P., Dosovitskiy, A., Brox, T., et al.: On iteratively reweighted algorithms for nonsmooth nonconvex optimization in computer vision. SIAM J. Imaging Sci. 8(1), 331–372 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  5. Ochs, P., Chen, Y., Brox, T., et al.: iPiano: inertial proximal algorithm for nonconvex optimization. SIAM J. Imaging Sci. 7(2), 1388–1419 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  6. Horst, R., Thoai, N.V.: DC programming: overview. J. Optim. Theory Appl. 103(1), 1–43 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  7. Tao, P.D., Le Thi Hoai, A.: A DC optimization algorithm for solving the trust-region subproblem. SIAM J. Optim. 8(2), 476–505 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  8. Tao, P.D., Le Thi Hoai, A.: Solving a class of linearly constrained indefinite quadratic problems by DC algorithms. J. Glob. Optim. 11(3), 253–285 (1997)

    Article  MATH  Google Scholar 

  9. Chen, X., Ng, M.K., Zhang, C.: Non-Lipschitz-regularization and box constrained model for image restoration. IEEE Trans. Image Process. 21(12), 4709–4721 (2012)

    Article  MathSciNet  Google Scholar 

  10. Chen, X., Zhou, W.: Convergence of the reweighted \(\ell _1\) minimization algorithm for \(\ell _2\)-\(\ell _p\) minimization. Comput. Optim. Appl. 59(1–2), 47–61 (2014)

    Article  MathSciNet  Google Scholar 

  11. Chartrand, R., Yin, W.: Iteratively reweighted algorithms for compressive sensing. In: IEEE International Conference on Acoustics, Speech and Signal Processing, 2008. ICASSP 2008. IEEE (2008)

  12. Gasso, G., Rakotomamonjy, A., Canu, S.: Recovering sparse signals with a certain family of nonconvex penalties and DC programming. IEEE Trans. Signal Process. 57(12), 4686–4698 (2009)

    Article  MathSciNet  Google Scholar 

  13. Weston, J., Elisseeff, A., Schölkopf, B., et al.: The use of zero-norm with linear models and kernel methods. J. Mach. Learn. Res. 3, 1439–1461 (2003)

    MathSciNet  MATH  Google Scholar 

  14. Zhang, T.: Multi-stage convex relaxation for learning with sparse regularization. In: Proceedings of the 22nd Annual Conference on Neural Information Processing Systems. 8–13 December, 2008; Vancouver, British, pp 1929–1936 (2008)

  15. Combettes, P.L., Va, A., Wajs, E.R.: Signal recovery by proximal forward–backward splitting. Multiscale Model. Simul. 4(4), 1168–1200 (2005)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  17. Wen, Z., Yin, W., Goldfarb, D., et al.: A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization and continuation. SIAM J. Sci. Comput. 32(4), 1832–1857 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  18. Parikh, N., Boyd, S.: Proximal algorithms. Found. Trends Optim. 1(3), 123–231 (2013)

    Google Scholar 

  19. Lu, C., Tang, J., Yan, S., Lin, Z.: Generalized nonconvex nonsmooth low-rank minimization. In: IEEE International Conference on Computer Vision and Pattern Recognition (2014)

  20. Lu, C., Zhu, C., Xu, C., Yan, S., Lin, Z.: Generalized singular value thresholding. In: Proceedings of the AAAI Conference on Artificial Intelligence (2015)

  21. Mordukhovich, B.S.: Variational analysis and generalized differentiation. I: Basic theory, Cs.nmu.edu (2006)

  22. Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. Springer, New York (2009)

    MATH  Google Scholar 

  23. Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (2015)

    MATH  Google Scholar 

  24. Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, Dordrecht (2004)

    Book  MATH  Google Scholar 

  25. Lojasiewicz, S.: Une propriété topologique des sous-ensembles analytiques réls[J]. Les équations aux dérivées partielles 117, 87–89 (1963)

    Google Scholar 

  26. Kurdyka, K.: On gradients of functions definable in o-minimal structures. Annales de l’institut Fourier 48(3), 769–783 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  27. Attouch, H., Bolte, J.: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. 116(1–2), 5–16 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  28. Attouch, H., Bolte, J., Redont, P., et al.: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Lojasiewicz inequality. Math. Oper. Res. 35(2), 438–457 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  29. Bolte, J., Daniilidis, A., Lewis, A.: The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17(4), 1205–1223 (2007)

    Article  MATH  Google Scholar 

  30. Bolte, J., Daniilidis, A., Lewis, A., et al.: Clarke subgradients of stratifiable functions. SIAM J. Optim. 18(2), 556–572 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  31. Attouch, H., Bolte, J., Svaiter, B.F.: Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forwardCbackward splitting, and regularized gauss-seidel methods. Math. Program. 137(1–2), 91–129 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  32. Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program. 146(1–2), 459–494 (2014)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors are indebted to the editors and anonymous referees for their useful suggestions. We are grateful for the support from the National Natural Science Foundation of Hunan Province, China (13JJ2001), the Science Project of National University of Defense Technology (JC120201), and the National Science Foundation of China (61402495).

Author information

Authors and Affiliations

  1. College of Science, National University of Defense Technology, Changsha, 410073, Hunan, People’s Republic of China

    Tao Sun & Lizhi Cheng

  2. College of Computer, National University of Defense Technology, Changsha, 410073, Hunan, People’s Republic of China

    Hao Jiang

  3. The State Key Laboratory for High Performance Computation, National University of Defense Technology, Changsha, 410073, Hunan, People’s Republic of China

    Lizhi Cheng

Authors
  1. Tao Sun
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hao Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Lizhi Cheng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tao Sun.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sun, T., Jiang, H. & Cheng, L. Global convergence of proximal iteratively reweighted algorithm. J Glob Optim 68, 815–826 (2017). https://doi.org/10.1007/s10898-017-0507-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-017-0507-z

Keywords

Mathematics Subject Classification

Search

Navigation