IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v71y2018i3d10.1007_s10589-018-0030-2.html
   My bibliography  Save this article

A fast gradient and function sampling method for finite-max functions

Author

Listed:
  • Elias S. Helou

    (University of São Paulo)

  • Sandra A. Santos

    (University of Campinas)

  • Lucas E. A. Simões

    (University of Campinas)

Abstract

This paper proposes an algorithm for the unconstrained minimization of a class of nonsmooth and nonconvex functions that can be written as finite-max functions. A gradient and function-based sampling method is proposed which, under special circumstances, either moves superlinearly to a minimizer of the problem of interest or improves the optimality certificate. Global and local convergence analysis are presented, as well as examples that illustrate the obtained theoretical results.

Suggested Citation

  • Elias S. Helou & Sandra A. Santos & Lucas E. A. Simões, 2018. "A fast gradient and function sampling method for finite-max functions," Computational Optimization and Applications, Springer, vol. 71(3), pages 673-717, December.
    • Handle: RePEc:spr:coopap:v:71:y:2018:i:3:d:10.1007_s10589-018-0030-2
    DOI: 10.1007/s10589-018-0030-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-018-0030-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10589-018-0030-2?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Elias Salomão Helou & Sandra A. Santos & Lucas E. A. Simões, 2017. "On the Local Convergence Analysis of the Gradient Sampling Method for Finite Max-Functions," Journal of Optimization Theory and Applications, Springer, vol. 175(1), pages 137-157, October.
    2. Milagros Loreto & Hugo Aponte & Debora Cores & Marcos Raydan, 2017. "Nonsmooth spectral gradient methods for unconstrained optimization," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(4), pages 529-553, December.
    3. Peng, Chengbin & Jin, Xiaogang & Shi, Meixia, 2010. "Epidemic threshold and immunization on generalized networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(3), pages 549-560.
    4. J. V. Burke & A. S. Lewis & M. L. Overton, 2002. "Approximating Subdifferentials by Random Sampling of Gradients," Mathematics of Operations Research, INFORMS, vol. 27(3), pages 567-584, August.
    5. Jianzhong Zhang & Nae-Heon Kim & L. Lasdon, 1985. "An Improved Successive Linear Programming Algorithm," Management Science, INFORMS, vol. 31(10), pages 1312-1331, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. M. Maleknia & M. Shamsi, 2020. "A new method based on the proximal bundle idea and gradient sampling technique for minimizing nonsmooth convex functions," Computational Optimization and Applications, Springer, vol. 77(2), pages 379-409, November.
    2. Morteza Maleknia & Mostafa Shamsi, 2020. "A Gradient Sampling Method Based on Ideal Direction for Solving Nonsmooth Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 187(1), pages 181-204, October.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jenny Carolina Saldana Cortés, 2011. "Programación semidefinida aplicada a problemas de cantidad económica de pedido," Documentos CEDE 8735, Universidad de los Andes, Facultad de Economía, CEDE.
    2. Ted Kutz & Mark Davis & Robert Creek & Nick Kenaston & Craig Stenstrom & Margery Connor, 2014. "Optimizing Chevron’s Refineries," Interfaces, INFORMS, vol. 44(1), pages 39-54, February.
    3. W. Hare & J. Nutini, 2013. "A derivative-free approximate gradient sampling algorithm for finite minimax problems," Computational Optimization and Applications, Springer, vol. 56(1), pages 1-38, September.
    4. Volker Maag & Martin Berger & Anton Winterfeld & Karl-Heinz Küfer, 2010. "A novel non-linear approach to minimal area rectangular packing," Annals of Operations Research, Springer, vol. 179(1), pages 243-260, September.
    5. Hong, Sung-Pil & Kim, Taegyoon & Lee, Subin, 2019. "A precision pump schedule optimization for the water supply networks with small buffers," Omega, Elsevier, vol. 82(C), pages 24-37.
    6. Wei Bian & Xiaojun Chen, 2017. "Optimality and Complexity for Constrained Optimization Problems with Nonconvex Regularization," Mathematics of Operations Research, INFORMS, vol. 42(4), pages 1063-1084, November.
    7. Dmitriy Drusvyatskiy & Alexander D. Ioffe & Adrian S. Lewis, 2015. "Clarke Subgradients for Directionally Lipschitzian Stratifiable Functions," Mathematics of Operations Research, INFORMS, vol. 40(2), pages 328-349, February.
    8. W. L. Hare & A. S. Lewis, 2005. "Estimating Tangent and Normal Cones Without Calculus," Mathematics of Operations Research, INFORMS, vol. 30(4), pages 785-799, November.
    9. Shams, Bita & Khansari, Mohammad, 2015. "On the impact of epidemic severity on network immunization algorithms," Theoretical Population Biology, Elsevier, vol. 106(C), pages 83-93.
    10. Z. Akbari & R. Yousefpour & M. Reza Peyghami, 2015. "A New Nonsmooth Trust Region Algorithm for Locally Lipschitz Unconstrained Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 164(3), pages 733-754, March.
    11. Mohammed Alfaki & Dag Haugland, 2013. "Strong formulations for the pooling problem," Journal of Global Optimization, Springer, vol. 56(3), pages 897-916, July.
    12. Dudek, Gregor & Stadtler, Hartmut, 2005. "Negotiation-based collaborative planning between supply chains partners," European Journal of Operational Research, Elsevier, vol. 163(3), pages 668-687, June.
    13. González-Parra, Gilberto & Acedo, L. & Villanueva Micó, Rafael-J. & Arenas, Abraham J., 2010. "Modeling the social obesity epidemic with stochastic networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(17), pages 3692-3701.
    14. Sarker, Ruhul A. & Gunn, Eldon A., 1997. "A simple SLP algorithm for solving a class of nonlinear programs," European Journal of Operational Research, Elsevier, vol. 101(1), pages 140-154, August.
    15. Giovanni Colombo & Antonio Marigonda & Peter R. Wolenski, 2013. "The Clarke Generalized Gradient for Functions Whose Epigraph Has Positive Reach," Mathematics of Operations Research, INFORMS, vol. 38(3), pages 451-468, August.
    16. Morteza Maleknia & Mostafa Shamsi, 2020. "A Gradient Sampling Method Based on Ideal Direction for Solving Nonsmooth Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 187(1), pages 181-204, October.
    17. Mohammed Alfaki & Dag Haugland, 2014. "A cost minimization heuristic for the pooling problem," Annals of Operations Research, Springer, vol. 222(1), pages 73-87, November.
    18. Daniel De Wolf & Yves Smeers, 2000. "The Gas Transmission Problem Solved by an Extension of the Simplex Algorithm," Management Science, INFORMS, vol. 46(11), pages 1454-1465, November.
    19. Arbore, Andrea & Fioriti, Vincenzo & Chinnici, Marta, 2016. "The topological defense in SIS epidemic models," Chaos, Solitons & Fractals, Elsevier, vol. 86(C), pages 16-22.
    20. Sajjad Kazemi & Nader Kanzi, 2018. "Constraint Qualifications and Stationary Conditions for Mathematical Programming with Non-differentiable Vanishing Constraints," Journal of Optimization Theory and Applications, Springer, vol. 179(3), pages 800-819, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:coopap:v:71:y:2018:i:3:d:10.1007_s10589-018-0030-2. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.