IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v66y2016i3d10.1007_s10898-015-0384-2.html
   My bibliography  Save this article

Delaunay-based derivative-free optimization via global surrogates, part I: linear constraints

Author

Listed:
  • Pooriya Beyhaghi

    (University of California)

  • Daniele Cavaglieri

    (University of California)

  • Thomas Bewley

    (University of California)

Abstract

A new derivative-free optimization algorithm is introduced for nonconvex functions within a feasible domain bounded by linear constraints. Global convergence is guaranteed for twice differentiable functions with bounded Hessian, and is found to be remarkably efficient even for many functions which are not differentiable. Like other Response Surface Methods, at each optimization step, the algorithm minimizes a metric combining an interpolation of existing function evaluations and a model of the uncertainty of this interpolation. By adjusting the respective weighting of these two terms, the algorithm incorporates a tunable balance between global exploration and local refinement; a rule to adjust this balance automatically is also presented. Unlike other methods, any well-behaved interpolation strategy may be used. The uncertainty model is built upon the framework of a Delaunay triangulation of existing datapoints in parameter space. A quadratic function which goes to zero at each datapoint is formed within each simplex of this triangulation; the union of each of these quadratics forms the desired uncertainty model. Care is taken to ensure that function evaluations are performed at points that are well situated in parameter space; that is, such that the simplices of the resulting triangulation have circumradii with a known bound. This facilitates well-behaved local refinement as additional function evaluations are performed.

Suggested Citation

  • Pooriya Beyhaghi & Daniele Cavaglieri & Thomas Bewley, 2016. "Delaunay-based derivative-free optimization via global surrogates, part I: linear constraints," Journal of Global Optimization, Springer, vol. 66(3), pages 331-382, November.
  • Handle: RePEc:spr:jglopt:v:66:y:2016:i:3:d:10.1007_s10898-015-0384-2
    DOI: 10.1007/s10898-015-0384-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-015-0384-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/s10898-015-0384-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. Paul Belitz & Thomas Bewley, 2013. "New horizons in sphere-packing theory, part II: lattice-based derivative-free optimization via global surrogates," Journal of Global Optimization, Springer, vol. 56(1), pages 61-91, May.
    2. T. H. Matheiss & David S. Rubin, 1980. "A Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets," Mathematics of Operations Research, INFORMS, vol. 5(2), pages 167-185, May.
    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. Ryan Alimo & Daniele Cavaglieri & Pooriya Beyhaghi & Thomas R. Bewley, 2021. "Design of IMEXRK time integration schemes via Delaunay-based derivative-free optimization with nonconvex constraints and grid-based acceleration," Journal of Global Optimization, Springer, vol. 79(3), pages 567-591, March.
    2. Pooriya Beyhaghi & Thomas Bewley, 2017. "Implementation of Cartesian grids to accelerate Delaunay-based derivative-free optimization," Journal of Global Optimization, Springer, vol. 69(4), pages 927-949, 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. repec:cep:stiecm:em/2012/559 is not listed on IDEAS
    2. Li, Changmin & Yang, Hai & Zhu, Daoli & Meng, Qiang, 2012. "A global optimization method for continuous network design problems," Transportation Research Part B: Methodological, Elsevier, vol. 46(9), pages 1144-1158.
    3. Tatiana Komarova, 2012. "Binary Choice Models with Discrete Regressors: Identification and Misspecification," STICERD - Econometrics Paper Series 559, Suntory and Toyota International Centres for Economics and Related Disciplines, LSE.
    4. Liesiö, Juuso & Andelmin, Juho & Salo, Ahti, 2020. "Efficient allocation of resources to a portfolio of decision making units," European Journal of Operational Research, Elsevier, vol. 286(2), pages 619-636.
    5. Haines, Linda M., 1998. "A statistical approach to the analytic hierarchy process with interval judgements. (I). Distributions on feasible regions," European Journal of Operational Research, Elsevier, vol. 110(1), pages 112-125, October.
    6. Pooriya Beyhaghi & Thomas R. Bewley, 2016. "Delaunay-based derivative-free optimization via global surrogates, part II: convex constraints," Journal of Global Optimization, Springer, vol. 66(3), pages 383-415, November.
    7. repec:cep:stiecm:/2012/559 is not listed on IDEAS
    8. Makowski, David & Hendrix, Eligius M. T. & van Ittersum, Martin K. & Rossing, Walter A. H., 2001. "Generation and presentation of nearly optimal solutions for mixed-integer linear programming, applied to a case in farming system design," European Journal of Operational Research, Elsevier, vol. 132(2), pages 425-438, July.
    9. Ida, Masaaki, 2005. "Efficient solution generation for multiple objective linear programming based on extreme ray generation method," European Journal of Operational Research, Elsevier, vol. 160(1), pages 242-251, January.
    10. Komarova, Tatiana, 2013. "Binary choice models with discrete regressors: Identification and misspecification," Journal of Econometrics, Elsevier, vol. 177(1), pages 14-33.
    11. Harju, Mikko & Liesiö, Juuso & Virtanen, Kai, 2019. "Spatial multi-attribute decision analysis: Axiomatic foundations and incomplete preference information," European Journal of Operational Research, Elsevier, vol. 275(1), pages 167-181.
    12. Pey-Chun Chen & Pierre Hansen & Brigitte Jaumard & Hoang Tuy, 1998. "Solution of the Multisource Weber and Conditional Weber Problems by D.-C. Programming," Operations Research, INFORMS, vol. 46(4), pages 548-562, August.
    13. José H. Dulá & Francisco J. López, 2006. "Algorithms for the Frame of a Finitely Generated Unbounded Polyhedron," INFORMS Journal on Computing, INFORMS, vol. 18(1), pages 97-110, February.
    14. Mattila, V. & Virtanen, K., 2015. "Ranking and selection for multiple performance measures using incomplete preference information," European Journal of Operational Research, Elsevier, vol. 242(2), pages 568-579.
    15. Ryan Alimo & Pooriya Beyhaghi & Thomas R. Bewley, 2020. "Delaunay-based derivative-free optimization via global surrogates. Part III: nonconvex constraints," Journal of Global Optimization, Springer, vol. 77(4), pages 743-776, August.
    16. Troutt, M. D. & Pang, W. K. & Hou, S. H., 1999. "Performance of some boundary-seeking mode estimators on the dome bias model," European Journal of Operational Research, Elsevier, vol. 119(1), pages 209-218, November.
    17. Mohammadali S. Monfared & Sayyed Ehsan Monabbati & Mahsa Mahdipour Azar, 2020. "Bi-objective optimization problems with two decision makers: refining Pareto-optimal front for equilibrium solution," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(2), pages 567-584, June.
    18. Vetschera, Rudolf, 1996. "A recursive algorithm for volume-based sensitivity analysis of linear decision models," Discussion Papers, Series I 279, University of Konstanz, Department of Economics.
    19. Gallagher, Richard J. & Saleh, Ossama A., 1995. "A representation of an efficiency equivalent polyhedron for the objective set of a multiple objective linear program," European Journal of Operational Research, Elsevier, vol. 80(1), pages 204-212, January.
    20. Nonås, Sigrid Lise, 2009. "Finding and identifying optimal inventory levels for systems with common components," European Journal of Operational Research, Elsevier, vol. 193(1), pages 98-119, February.
    21. Pooriya Beyhaghi & Thomas Bewley, 2017. "Implementation of Cartesian grids to accelerate Delaunay-based derivative-free optimization," Journal of Global Optimization, Springer, vol. 69(4), pages 927-949, December.
    22. Piet-Lahanier, Hélène & Veres, Sándor M. & Walter, Eric, 1992. "Comparison of methods for solving sets of linear inequalities in the bounded-error context," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 34(6), pages 515-524.

    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:66:y:2016:i:3:d:10.1007_s10898-015-0384-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.