Skip to main content
SpringerLink
Log in

Global convergence of a proximal linearized algorithm for difference of convex functions

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

A proximal linearized algorithm for minimizing difference of two convex functions is proposed. If the sequence generated by the algorithm is bounded it is proved that every cluster point is a critical point of the function under consideration, even if the auxiliary minimizations are performed inexactly at each iteration. Linear convergence of the sequence is established under suitable additional assumptions.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Martinet, B.: Regularisation d’inéquations variationelles par approximations succesives. Rev. Française d’Inform. Recherche Oper. 4, 154–159 (1970)

    MathSciNet  MATH  Google Scholar 

  2. Moreau, J.J.: Proximité et dualité dans un espace Hilbertien. Bull. Soc. Math. France 93, 273–299 (1965)

    MathSciNet  MATH  Google Scholar 

  3. Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. control. optim. 14, 877–898 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  4. Kaplan, A., Tichatschke, R.: Proximal point methods and nonconvex optimization. J. Glob. Optim. 13, 389–406 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  5. Hare, W., Sagastizábal, C.: Computing proximal points of nonconvex functions. Math. Program. 116(1), 221–258 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  6. Otero, R.G., Iusem, A.N.: Proximal methods in reflexive Banach spaces without monotonicity. J. Math. Anal. Appl. 330(1), 433–450 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  7. Iusem, A.N., Pennanen, T., Svaiter, B.F.: Inexact variants of the proximal point algorithm without monotonicity. SIAM J. Optim. 13(4), 1080–1097 (2003)

  8. Bento, G.C., Soubeyran, A.: A generalized inexact proximal point method for nonsmooth functions that satisfies Kurdyka-Lojasiewicz inequality. Set-Valued Var. Anal. 23(3), 501–517 (2015)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  10. Burachik, R.S., Svaiter, B.F.: A relative error tolerance for a family of generalized proximal point methods. Math. Oper. Res. 26(4), 816–831 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  11. Solodov, M.V., Svaiter, B.F.: Error bounds for proximal point subproblems and associated inexact proximal point algorithms. Math. Program 88(2), 371–389 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  12. Solodov, M.V., Svaiter, B.F.: A unified framework for some inexact proximal point algorithms. Numer. Funct. Anal. Optim. 22(7–8), 1013–1035 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  13. Zaslavski, A.: Convergence of a proximal point method in the presence of computational errors in Hilbert spaces. SIAM J. Optim. 20(5), 2413–2421 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  14. Bento, G.C., Soubeyran, A.: Generalized inexact proximal algorithms: Routine’s formation with resistance to change, following worthwhile changes. J. Optim. Theory Appl. 172(1), 1–16 (2015)

    MathSciNet  MATH  Google Scholar 

  15. Sun, W., Sampaio, R.J.B., Candido, M.A.B.: Proximal point algorithm for minimization of DC Functions. J. Comput. Math. 21, 451–462 (2003)

    MathSciNet  MATH  Google Scholar 

  16. Moudafi, A., Maingé, P.-E.: On the convergence of an approximate proximal method for d.c. functions. J. Comput. Math. 24, 475–480 (2006)

    MathSciNet  MATH  Google Scholar 

  17. Souza, J.C.O., Oliveira, P.R.: A proximal point algorithm for DC functions on Hadamard manifolds. J. Glob. Optim. (2015). doi:10.1007/s10898-015-0282-7

  18. Hartman, P.: On functions representable as a difference of convex functions. Pac. J. Math. 9, 707–713 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  19. Bomze, I., Lemaréchal, C.: Necessary conditions for local optimality in difference-of-convex programming. J. Convex Anal. 17, 673–680 (2010)

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  21. Hiriart-Urruty, J.B.: Generalized differentiabity, duality and optimization for problems dealing with difference of convex functions, Convexity and Duality in Optimization. Lectur. Notes Econ. Math. Syst 256, 37–70 (1986)

    Article  MathSciNet  Google Scholar 

  22. Pham, D.T., Souad, E.B.: Algorithms for solving a class of nonconvex optimization problems: methods of subgradient. Fermat Days 85: Math. Optim. 129, 249–271 (1986)

    Article  Google Scholar 

  23. Ferrer, A., Bagirov, A., Beliakov, G.: Solving DC programs using the cutting angle method. J. Glob. Optim. 61(1), 71–89 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  24. Pham, D.T., An, L.T.H., Akoa, F.: The DC (Difference of Convex Functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann. Oper. Res. 133, 23–46 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  25. Holmberg, K., Tuy, H.: A production-transportation problem with stochastic demand and concave production costs. Math. Program. 85, 157–179 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  26. Chen, P.C., Hansen, P., Jaumard, B., Tuy, H.: Solution of the multisource weber and conditional weber problems by d.c. programming. Oper. Res. 46(4), 548–562 (1998)

  27. Hiriart-Urruty, J.B., Lemaréchal, C.: Convex analysis and minimization algorithms. Springer, Berlin (1993)

    MATH  Google Scholar 

  28. Rockafellar, R.T.: Convex analysis. Princeton University Press, Princeton, New Jersey (1970)

    Book  MATH  Google Scholar 

  29. Ginchev, I., Gintcheva, D.: Characterization and recognition of dc functions. J. Glob. Optim. 57, 633–647 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  30. Burachik, R., Graña Drummond, L.M., Iusem, A.N., Svaiter, B.F.: Full convergence of the steepest descent method with inexact line searches. Optimization 32(2), 137–146 (1995)

  31. Soubeyran, A: Variational rationality. Human behaviors as worthwhile stay and change transitions, possibly ending in traps, before reaching desires. Preprint at GREQAM-AMSE (2015)

  32. Polyak, B.T.: Sharp Minima Institute of Control Sciences Lecture Notes, Moscow, USSR, 1979. Presented at the IIASA workshop on generalized Lagrangians and their applications, IIASA, Laxenburg, Austria (1979)

  33. Ferris, M.C.: Weak sharp minima and penalty functions in mathematical programming. Ph.D. Thesis. University of Cambridge, UK (1988)

  34. Li, G., Mordukhovich, B.S.: Holder metric subregularity with applications to proximal point method. SIAM J. Optim. 22, 1655–1684 (2012)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The authors wish to express their gratitude to the anonymous referees for them helpful comments.

Author information

Authors and Affiliations

  1. COPPE-PESC, Federal University of Rio de Janeiro, Postal Code 21945-970, Rio de Janeiro, RJ, Brazil

    João Carlos O. Souza & Paulo Roberto Oliveira

  2. CEAD, Federal University of Piauí, Teresina, PI, Brazil

    João Carlos O. Souza

  3. Aix-Marseille University (Aix-Marseille School of Economics), CNRS and EHESS, Marseille, France

    Antoine Soubeyran

Authors
  1. João Carlos O. Souza
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paulo Roberto Oliveira
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Antoine Soubeyran
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to João Carlos O. Souza.

Additional information

The research of the J. C. Souza was supported in part by CNPq-Ciências sem Fronteiras Grant 203360/2014-1. The P. R. Oliveira was partially supported by CNPq, Brazil.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Souza, J.C.O., Oliveira, P.R. & Soubeyran, A. Global convergence of a proximal linearized algorithm for difference of convex functions. Optim Lett 10, 1529–1539 (2016). https://doi.org/10.1007/s11590-015-0969-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-015-0969-1

Keywords

Search

Navigation