IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v62y2015i3p693-715.html
   My bibliography  Save this article

Mesh adaptive direct search with second directional derivative-based Hessian update

Author

Listed:
  • Árpád Bűrmen
  • Jernej Olenšek
  • Tadej Tuma

Abstract

The subject of this paper is inequality constrained black-box optimization with mesh adaptive direct search (MADS). The MADS search step can include additional strategies for accelerating the convergence and improving the accuracy of the solution. The strategy proposed in this paper involves building a quadratic model of the function and linear models of the constraints. The quadratic model is built by means of a second directional derivative-based Hessian update. The linear terms are obtained by linear regression. The resulting quadratic programming (QP) problem is solved with a dedicated solver and the original functions are evaluated at the QP solution. The proposed search strategy is computationally less expensive than the quadratically constrained QP strategy in the state of the art MADS implementation (NOMAD). The proposed MADS variant (QPMADS) and NOMAD are compared on four sets of test problems. QPMADS outperforms NOMAD on all four of them for all but the smallest computational budgets. Copyright Springer Science+Business Media New York 2015

Suggested Citation

  • Árpád Bűrmen & Jernej Olenšek & Tadej Tuma, 2015. "Mesh adaptive direct search with second directional derivative-based Hessian update," Computational Optimization and Applications, Springer, vol. 62(3), pages 693-715, December.
    • Handle: RePEc:spr:coopap:v:62:y:2015:i:3:p:693-715
    DOI: 10.1007/s10589-015-9753-5
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10589-015-9753-5
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10589-015-9753-5?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. A. Custódio & H. Rocha & L. Vicente, 2010. "Incorporating minimum Frobenius norm models in direct search," Computational Optimization and Applications, Springer, vol. 46(2), pages 265-278, June.
    2. Benjamin Dyke & Thomas J. Asaki, 2013. "Using QR Decomposition to Obtain a New Instance of Mesh Adaptive Direct Search with Uniformly Distributed Polling Directions," Journal of Optimization Theory and Applications, Springer, vol. 159(3), pages 805-821, December.
    3. I. D. Coope & C. J. Price, 2000. "Frame Based Methods for Unconstrained Optimization," Journal of Optimization Theory and Applications, Springer, vol. 107(2), pages 261-274, November.
    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. Árpád Bűrmen & Tadej Tuma & Jernej Olenšek, 2021. "Randomized Simplicial Hessian Update," Mathematics, MDPI, vol. 9(15), pages 1-18, July.
    2. Árpád Bűrmen & Iztok Fajfar, 2019. "Mesh adaptive direct search with simplicial Hessian update," Computational Optimization and Applications, Springer, vol. 74(3), pages 645-667, December.

    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. Y. Diouane & S. Gratton & L. Vicente, 2015. "Globally convergent evolution strategies for constrained optimization," Computational Optimization and Applications, Springer, vol. 62(2), pages 323-346, November.
    2. Benjamin Van Dyke, 2014. "Equal Angle Distribution of Polling Directions in Direct-Search Methods," Journal of Optimization, Hindawi, vol. 2014, pages 1-15, July.
    3. Árpád Bűrmen & Iztok Fajfar, 2019. "Mesh adaptive direct search with simplicial Hessian update," Computational Optimization and Applications, Springer, vol. 74(3), pages 645-667, December.
    4. Benjamin Dyke & Thomas J. Asaki, 2013. "Using QR Decomposition to Obtain a New Instance of Mesh Adaptive Direct Search with Uniformly Distributed Polling Directions," Journal of Optimization Theory and Applications, Springer, vol. 159(3), pages 805-821, December.
    5. A. Sanchez & Diego Martinez, 2011. "Optimization in Non-Standard Problems. An Application to the Provision of Public Inputs," Computational Economics, Springer;Society for Computational Economics, vol. 37(1), pages 13-38, January.
    6. Remigijus Paulavičius & Lakhdar Chiter & Julius Žilinskas, 2018. "Global optimization based on bisection of rectangles, function values at diagonals, and a set of Lipschitz constants," Journal of Global Optimization, Springer, vol. 71(1), pages 5-20, May.
    7. C.J. Price & I.D. Coope, 2003. "Frame-Based Ray Search Algorithms in Unconstrained Optimization," Journal of Optimization Theory and Applications, Springer, vol. 116(2), pages 359-377, February.
    8. C.J. Price & I.D. Coope & D. Byatt, 2002. "A Convergent Variant of the Nelder–Mead Algorithm," Journal of Optimization Theory and Applications, Springer, vol. 113(1), pages 5-19, April.
    9. He, Fang & Yin, Yafeng & Chen, Zhibin & Zhou, Jing, 2015. "Pricing of parking games with atomic players," Transportation Research Part B: Methodological, Elsevier, vol. 73(C), pages 1-12.
    10. Charles Audet & Michael Kokkolaras & Sébastien Le Digabel & Bastien Talgorn, 2018. "Order-based error for managing ensembles of surrogates in mesh adaptive direct search," Journal of Global Optimization, Springer, vol. 70(3), pages 645-675, March.
    11. Ubaldo M. García-Palomares, 2020. "Non-monotone derivative-free algorithm for solving optimization models with linear constraints: extensions for solving nonlinearly constrained models via exact penalty methods," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(3), pages 599-625, October.
    12. Javaid Ali & Muhammad Saeed & Muhammad Farhan Tabassam & Shaukat Iqbal, 2019. "Controlled showering optimization algorithm: an intelligent tool for decision making in global optimization," Computational and Mathematical Organization Theory, Springer, vol. 25(2), pages 132-164, June.
    13. Sander Dedoncker & Wim Desmet & Frank Naets, 2021. "Generating set search using simplex gradients for bound-constrained black-box optimization," Computational Optimization and Applications, Springer, vol. 79(1), pages 35-65, May.
    14. Remigijus Paulavičius & Yaroslav Sergeyev & Dmitri Kvasov & Julius Žilinskas, 2014. "Globally-biased Disimpl algorithm for expensive global optimization," Journal of Global Optimization, Springer, vol. 59(2), pages 545-567, July.
    15. Eric Newby & M. Ali, 2015. "A trust-region-based derivative free algorithm for mixed integer programming," Computational Optimization and Applications, Springer, vol. 60(1), pages 199-229, January.
    16. C. P. Brás & A. L. Custódio, 2020. "On the use of polynomial models in multiobjective directional direct search," Computational Optimization and Applications, Springer, vol. 77(3), pages 897-918, December.
    17. László Pál, 2017. "Empirical study of the improved UNIRANDI local search method," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 25(4), pages 929-952, December.
    18. Wu, Di & Yin, Yafeng & Lawphongpanich, Siriphong & Yang, Hai, 2012. "Design of more equitable congestion pricing and tradable credit schemes for multimodal transportation networks," Transportation Research Part B: Methodological, Elsevier, vol. 46(9), pages 1273-1287.
    19. Charles Audet & Sébastien Le Digabel & Renaud Saltet, 2022. "Quantifying uncertainty with ensembles of surrogates for blackbox optimization," Computational Optimization and Applications, Springer, vol. 83(1), pages 29-66, September.
    20. Charles Audet & Christophe Tribes, 2018. "Mesh-based Nelder–Mead algorithm for inequality constrained optimization," Computational Optimization and Applications, Springer, vol. 71(2), pages 331-352, November.

    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:62:y:2015:i:3:p:693-715. 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.