IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v85y2023i1d10.1007_s10898-022-01191-7.html
   My bibliography  Save this article

Finding the set of global minimizers of a piecewise affine function

Author

Listed:
  • Majid E. Abbasov

    (St. Petersburg State University
    Institute for Problems in Mechanical Engineering of the Russian Academy of Sciences)

Abstract

Coexhausters are families of convex compact sets that allow one to represent the approximation of the increment of a function at a given point in the form of minmax or maxmin of affine functions. We demonstrate that this representation can be used to define a piecewise affine function and therefore coexhausters are a natural technique for studying the problem of finding a global minimum of piecewise affine functions. All the conditions and methods in the current study were obtained by means of coexhausters theory. Firstly, we apply coexhauster based conditions to state and prove necessary and sufficient conditions for a piecewise affine function to be bounded from below. Secondly, we use coexhausters to construct a simple method which allows one to get the minimum value of the studied function and the corresponding set of all its global minimizers. Illustrative numerical examples are provided throughout the paper.

Suggested Citation

  • Majid E. Abbasov, 2023. "Finding the set of global minimizers of a piecewise affine function," Journal of Global Optimization, Springer, vol. 85(1), pages 1-13, January.
  • Handle: RePEc:spr:jglopt:v:85:y:2023:i:1:d:10.1007_s10898-022-01191-7
    DOI: 10.1007/s10898-022-01191-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-022-01191-7
    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/s10898-022-01191-7?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. M. E. Abbasov & V. F. Demyanov, 2013. "Adjoint Coexhausters in Nonsmooth Analysis and Extremality Conditions," Journal of Optimization Theory and Applications, Springer, vol. 156(3), pages 535-553, March.
    2. Silva, Thiago Lima & Camponogara, Eduardo, 2014. "A computational analysis of multidimensional piecewise-linear models with applications to oil production optimization," European Journal of Operational Research, Elsevier, vol. 232(3), pages 630-642.
    3. Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico & Adil M. Bagirov, 2018. "Minimizing nonsmooth DC functions via successive DC piecewise-affine approximations," Journal of Global Optimization, Springer, vol. 71(1), pages 37-55, May.
    4. Stephan Dempe & Felix Harder & Patrick Mehlitz & Gerd Wachsmuth, 2019. "Solving inverse optimal control problems via value functions to global optimality," Journal of Global Optimization, Springer, vol. 74(2), pages 297-325, June.
    Full references (including those not matched with items on IDEAS)

    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. M. E. Abbasov, 2016. "Second-Order Minimization Method for Nonsmooth Functions Allowing Convex Quadratic Approximations of the Augment," Journal of Optimization Theory and Applications, Springer, vol. 171(2), pages 666-674, November.
    2. Welington Oliveira, 2019. "Proximal bundle methods for nonsmooth DC programming," Journal of Global Optimization, Springer, vol. 75(2), pages 523-563, October.
    3. Astorino, Annabella & Avolio, Matteo & Fuduli, Antonio, 2022. "A maximum-margin multisphere approach for binary Multiple Instance Learning," European Journal of Operational Research, Elsevier, vol. 299(2), pages 642-652.
    4. W. Ackooij & S. Demassey & P. Javal & H. Morais & W. Oliveira & B. Swaminathan, 2021. "A bundle method for nonsmooth DC programming with application to chance-constrained problems," Computational Optimization and Applications, Springer, vol. 78(2), pages 451-490, March.
    5. Markus Friedemann & Felix Harder & Gerd Wachsmuth, 2023. "Finding global solutions of some inverse optimal control problems using penalization and semismooth Newton methods," Journal of Global Optimization, Springer, vol. 86(4), pages 1025-1061, August.
    6. Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico, 2023. "Sparse optimization via vector k-norm and DC programming with an application to feature selection for support vector machines," Computational Optimization and Applications, Springer, vol. 86(2), pages 745-766, November.
    7. M. V. Dolgopolik, 2020. "New global optimality conditions for nonsmooth DC optimization problems," Journal of Global Optimization, Springer, vol. 76(1), pages 25-55, January.
    8. Najmeh Hoseini Monjezi & S. Nobakhtian, 2021. "A filter proximal bundle method for nonsmooth nonconvex constrained optimization," Journal of Global Optimization, Springer, vol. 79(1), pages 1-37, January.
    9. Camponogara, Eduardo & Oliveira, Mateus Dubiela & Aguiar, Marco Aurélio Schmitz de, 2015. "Scheduling pumpoff operations in onshore oilfields under electric-power constraints," European Journal of Operational Research, Elsevier, vol. 247(3), pages 945-956.
    10. Milosavljevic, Predrag & Marchetti, Alejandro G. & Cortinovis, Andrea & Faulwasser, Timm & Mercangöz, Mehmet & Bonvin, Dominique, 2020. "Real-time optimization of load sharing for gas compressors in the presence of uncertainty," Applied Energy, Elsevier, vol. 272(C).
    11. Valentin V. Gorokhovik & Marina Trafimovich, 2016. "Positively Homogeneous Functions Revisited," Journal of Optimization Theory and Applications, Springer, vol. 171(2), pages 481-503, November.
    12. A. M. Bagirov & N. Hoseini Monjezi & S. Taheri, 2021. "An augmented subgradient method for minimizing nonsmooth DC functions," Computational Optimization and Applications, Springer, vol. 80(2), pages 411-438, November.
    13. Hoai An Le Thi & Vinh Thanh Ho & Tao Pham Dinh, 2019. "A unified DC programming framework and efficient DCA based approaches for large scale batch reinforcement learning," Journal of Global Optimization, Springer, vol. 73(2), pages 279-310, February.
    14. Wim Ackooij & Welington Oliveira, 2019. "Nonsmooth and Nonconvex Optimization via Approximate Difference-of-Convex Decompositions," Journal of Optimization Theory and Applications, Springer, vol. 182(1), pages 49-80, July.
    15. Shao, Yu & Zhou, Xinhong & Yu, Tingchao & Zhang, Tuqiao & Chu, Shipeng, 2024. "Pump scheduling optimization in water distribution system based on mixed integer linear programming," European Journal of Operational Research, Elsevier, vol. 313(3), pages 1140-1151.
    16. Silva, L.M.R. & Guedes Soares, C., 2023. "Robust optimization model of an offshore oil production system for cost and pipeline risk of failure," Reliability Engineering and System Safety, Elsevier, vol. 232(C).
    17. Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico, 2020. "Essentials of numerical nonsmooth optimization," 4OR, Springer, vol. 18(1), pages 1-47, March.
    18. Shiwei Yu & Shuwen Zhang & Lawrence Agbemabiese & Fukun Zhang, 2017. "Multi-stage goal programming models for production optimization in the middle and later periods of oilfield development," Annals of Operations Research, Springer, vol. 255(1), pages 421-437, August.
    19. Aloïs Duguet & Christian Artigues & Laurent Houssin & Sandra Ulrich Ngueveu, 2022. "Properties, Extensions and Application of Piecewise Linearization for Euclidean Norm Optimization in $$\mathbb {R}^2$$ R 2," Journal of Optimization Theory and Applications, Springer, vol. 195(2), pages 418-448, November.
    20. Rovatti, Riccardo & D’Ambrosio, Claudia & Lodi, Andrea & Martello, Silvano, 2014. "Optimistic MILP modeling of non-linear optimization problems," European Journal of Operational Research, Elsevier, vol. 239(1), pages 32-45.

    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:jglopt:v:85:y:2023:i:1:d:10.1007_s10898-022-01191-7. 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.