[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A Gradient Sampling Method Based on Ideal Direction for Solving Nonsmooth Optimization Problems

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

In this paper, a modification to the original gradient sampling method for minimizing nonsmooth nonconvex functions is presented. One computational component in the gradient sampling method is the need to solve a quadratic optimization problem at each iteration, which may result in a time-consuming process, especially for large-scale objectives. To resolve this difficulty, this study proposes a new descent direction, for which there is no need to consider any quadratic or linear subproblem. It is shown that this direction satisfies the Armijo step size condition. We also prove that under proposed modifications, the global convergence of the gradient sampling method is preserved. Moreover, under some moderate assumptions, an upper bound for the number of serious iterations is presented. Using this upper bound, we develop a different strategy to study the convergence of the method. We also demonstrate the efficiency of the proposed method using small-, medium- and large-scale problems in our numerical experiments.

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
£29.99 /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 (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

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

Similar content being viewed by others

References

  1. Burke, J.V., Lewis, A.S., Overton, M.L.: A robust gradient sampling algorithm for nonsmooth, nonconvex optimization. SIAM J. Optim. 15(3), 751–779 (2005)

    Article  MathSciNet  Google Scholar 

  2. Kiwiel, K.C.: Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM J. Optim. 18(2), 379–388 (2007)

    Article  MathSciNet  Google Scholar 

  3. Kiwiel, K.C.: A nonderivative version of the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM J. Optim. 20(4), 1983–1994 (2010)

    Article  MathSciNet  Google Scholar 

  4. Curtis, F.E., Que, X.: An adaptive gradient sampling algorithm for nonconvex nonsmooth optimization. Optim. Methods Softw. 28(6), 1302–1324 (2013)

    Article  MathSciNet  Google Scholar 

  5. Curtis, F.E., Overton, M.L.: A sequential quadratic programming algorithm for nonconvex, nonsmooth constrained optimization. SIAM J. Optim. 22(2), 474–500 (2012)

    Article  MathSciNet  Google Scholar 

  6. Helou, E.S., Santos, A.S., Simões, L.E.A.: On the local convergence analysis of the gradient sampling method for finite max-functions. J. Optim. Theory Appl. 175(1), 137–157 (2017)

    Article  MathSciNet  Google Scholar 

  7. Helou, E.S., Santos, A.S., Simões, L.E.A.: A fast gradient and function sampling method for finite-max functions. Comput. Optim. Appl. 71(3), 673–717 (2018)

    Article  MathSciNet  Google Scholar 

  8. Evans, L.C., Gariepy, R.F.: Measure Theory and Fine Properties of Functions, Revised edn. CRC Press, Boca Raton (1992)

    MATH  Google Scholar 

  9. Clarke, F.H.: Optimization and Nonsmooth Analysis. SIAM, Montreal (1990)

    Book  Google Scholar 

  10. Bagirov, A.M., Karmitsa, N., Mäkelä, M.M.: Introduction to Nonsmooth Optimization. Springer, Berlin (2014)

    Book  Google Scholar 

  11. Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. Springer, Berlin (2004)

    MATH  Google Scholar 

  12. Burke, J.V., Curtis, F.E., Lewis, A.S., Overton, M.L., Simões, L.E.A.: Gradient sampling methods for nonsmooth optimization. In: Bagirov, A.M., et al. (eds.) Numerical Nonsmooth Optimization: State of the Art Algorithms, pp. 201–225. Springer, Cham (2020)

    Chapter  Google Scholar 

  13. Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)

    Book  Google Scholar 

  14. Ehrgott, M.: Multicriteria Optimization. Springer, Berlin (2005)

    MATH  Google Scholar 

  15. Mäkelä, M.M., Neittaanmäki, P.: Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control. World Scientific, Singapore (1992)

    Book  Google Scholar 

  16. Lukšan, L., Vlček, J.: Test problems for nonsmooth unconstrained and linearly constrained optimization. Technical report, Institute of Computer Science, Academy of Sciences of the Czech Republic (2000)

  17. Skaaja, M.: Limited memory BFGS for nonsmooth optimization. Master’s Thesis, New York University (2010)

  18. Kiwiel, K.C.: Methods of Descent for Nondifferentiable Optimization. Springer, Berlin (1985)

    Book  Google Scholar 

  19. Lukšan, L., Tcma, M., Siska, M., Vlček, J., Ramesova, N.: Ufo 2002. Interactive system for universal functional optimization. Technical report, Institute of Computer Science, Academy of Sciences of the Czech Republic (2002)

  20. Haarala, M., Miettinen, K., Mäkelä, M.M.: New limited memory bundle method for large-scale nonsmooth optimization. Optim. Methods Softw. 19(6), 673–692 (2004)

    Article  MathSciNet  Google Scholar 

  21. Grothey, A.: Decomposition methods for nonlinear nonconvex optimization problems. Ph.D. Thesis, University of Edinburgh (2001)

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

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors are very grateful to two anonymous referees and Editor-in-Chief for carefully reading this paper and for their comments and suggestions that improved the quality of the paper. We also would like to thank Dr. L. E. A. Simões for his valuable comments on an initial version of the paper.

Author information

Authors and Affiliations

  1. Amirkabir University of Technology, Tehran, Iran

    Morteza Maleknia & Mostafa Shamsi

Authors
  1. Morteza Maleknia
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mostafa Shamsi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mostafa Shamsi.

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

Maleknia, M., Shamsi, M. A Gradient Sampling Method Based on Ideal Direction for Solving Nonsmooth Optimization Problems. J Optim Theory Appl 187, 181–204 (2020). https://doi.org/10.1007/s10957-020-01740-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-020-01740-8

Keywords

Mathematics Subject Classification

Search

Navigation