IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v9y2021i2p134-d477948.html
   My bibliography  Save this article

Automatic Convexity Deduction for Efficient Function’s Range Bounding

Author

Listed:
  • Mikhail Posypkin

    (Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, Vavilova 44-2, 119333 Moscow, Russia)

  • Oleg Khamisov

    (Melentiev Energy Systems Institute of Siberian Branch of the Russian Academy of Sciences, Lermontov St., 130, 664033 Irkutsk, Russia)

Abstract

Reliable bounding of a function’s range is essential for deterministic global optimization, approximation, locating roots of nonlinear equations, and several other computational mathematics areas. Despite years of extensive research in this direction, there is still room for improvement. The traditional and compelling approach to this problem is interval analysis. We show that accounting convexity/concavity can significantly tighten the bounds computed by interval analysis. To make our approach applicable to a broad range of functions, we also develop the techniques for handling nondifferentiable composite functions. Traditional ways to ensure the convexity fail in such cases. Experimental evaluation showed the remarkable potential of the proposed methods.

Suggested Citation

  • Mikhail Posypkin & Oleg Khamisov, 2021. "Automatic Convexity Deduction for Efficient Function’s Range Bounding," Mathematics, MDPI, vol. 9(2), pages 1-16, January.
    • Handle: RePEc:gam:jmathe:v:9:y:2021:i:2:p:134-:d:477948
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/2/134/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/9/2/134/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Strekalovsky, Alexander S., 2015. "On local search in d.c. optimization problems," Applied Mathematics and Computation, Elsevier, vol. 255(C), pages 73-83.
    2. Daniela Lera & Yaroslav D. Sergeyev, 2018. "GOSH: derivative-free global optimization using multi-dimensional space-filling curves," Journal of Global Optimization, Springer, vol. 71(1), pages 193-211, May.
    3. Lera, Daniela & Posypkin, Mikhail & Sergeyev, Yaroslav D., 2021. "Space-filling curves for numerical approximation and visualization of solutions to systems of nonlinear inequalities with applications in robotics," Applied Mathematics and Computation, Elsevier, vol. 390(C).
    4. A. Žilinskas, 1978. "Optimization of One‐Dimensional Multimodal Functions," Journal of the Royal Statistical Society Series C, Royal Statistical Society, vol. 27(3), pages 367-375, November.
    5. Robert Fourer & Chandrakant Maheshwari & Arnold Neumaier & Dominique Orban & Hermann Schichl, 2010. "Convexity and Concavity Detection in Computational Graphs: Tree Walks for Convexity Assessment," INFORMS Journal on Computing, INFORMS, vol. 22(1), pages 26-43, February.
    6. Orhan Arıkan & Regina S. Burachik & C. Yalçın Kaya, 2020. "Steklov regularization and trajectory methods for univariate global optimization," Journal of Global Optimization, Springer, vol. 76(1), pages 91-120, January.
    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. Mikhail Posypkin & Andrey Gorshenin & Vladimir Titarev, 2022. "Preface to the Special Issue on “Control, Optimization, and Mathematical Modeling of Complex Systems”," Mathematics, MDPI, vol. 10(13), pages 1-8, June.

    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. Naveed Ishtiaq Chaudhary & Muhammad Asif Zahoor Raja & Zeshan Aslam Khan & Khalid Mehmood Cheema & Ahmad H. Milyani, 2021. "Hierarchical Quasi-Fractional Gradient Descent Method for Parameter Estimation of Nonlinear ARX Systems Using Key Term Separation Principle," Mathematics, MDPI, vol. 9(24), pages 1-14, December.
    2. S. Dempe & S. Franke, 2016. "On the solution of convex bilevel optimization problems," Computational Optimization and Applications, Springer, vol. 63(3), pages 685-703, April.
    3. Alexander S. Strekalovsky, 2017. "Global Optimality Conditions in Nonconvex Optimization," Journal of Optimization Theory and Applications, Springer, vol. 173(3), pages 770-792, June.
    4. 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.
    5. Sinha, Ankur & Das, Arka & Anand, Guneshwar & Jayaswal, Sachin, 2023. "A general purpose exact solution method for mixed integer concave minimization problems," European Journal of Operational Research, Elsevier, vol. 309(3), pages 977-992.
    6. Joki, Kaisa & Bagirov, Adil M. & Karmitsa, Napsu & Mäkelä, Marko M. & Taheri, Sona, 2020. "Clusterwise support vector linear regression," European Journal of Operational Research, Elsevier, vol. 287(1), pages 19-35.
    7. Sinha, Ankur & Das, Arka & Anand, Guneshwar & Jayaswal, Sachin, 2021. "A General Purpose Exact Solution Method for Mixed Integer Concave Minimization Problems (revised as on 12/08/2021)," IIMA Working Papers WP 2021-03-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    8. Ruth Misener & Christodoulos Floudas, 2014. "ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations," Journal of Global Optimization, Springer, vol. 59(2), pages 503-526, July.
    9. Huo, Jinbiao & Liu, Zhiyuan & Chen, Jingxu & Cheng, Qixiu & Meng, Qiang, 2023. "Bayesian optimization for congestion pricing problems: A general framework and its instability," Transportation Research Part B: Methodological, Elsevier, vol. 169(C), pages 1-28.
    10. Sinha, Ankur & Das, Arka & Anand, Guneshwar & Jayaswal, Sachin, 2021. "A General Purpose Exact Solution Method for Mixed Integer Concave Minimization Problems," IIMA Working Papers WP 2021-03-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    11. 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.
    12. Alberto Lovison & Kaisa Miettinen, 2021. "On the Extension of the DIRECT Algorithm to Multiple Objectives," Journal of Global Optimization, Springer, vol. 79(2), pages 387-412, February.
    13. Lera, Daniela & Posypkin, Mikhail & Sergeyev, Yaroslav D., 2021. "Space-filling curves for numerical approximation and visualization of solutions to systems of nonlinear inequalities with applications in robotics," Applied Mathematics and Computation, Elsevier, vol. 390(C).
    14. Ziadi, Raouf & Bencherif-Madani, Abdelatif & Ellaia, Rachid, 2020. "A deterministic method for continuous global optimization using a dense curve," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 178(C), pages 62-91.

    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:gam:jmathe:v:9:y:2021:i:2:p:134-:d:477948. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.