IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v195y2009i1p31-45.html
   My bibliography  Save this article

Finding local optima of high-dimensional functions using direct search methods

Author

Listed:
  • Hvattum, Lars Magnus
  • Glover, Fred

Abstract

This paper focuses on a subclass of box-constrained, non-linear optimization problems. We are particularly concerned with settings where gradient information is unreliable, or too costly to calculate, and the function evaluations themselves are very costly. This encourages the use of derivative free optimization methods, and especially a subclass of these referred to as direct search methods. The thrust of our investigation is twofold. First, we implement and evaluate a number of traditional direct search methods according to the premise that they should be suitable as local optimizers when used in a metaheuristic framework. Second, we introduce a new direct search method, based on Scatter Search, designed to remedy the lack of a good derivative free method for solving problems of high dimensions. Our new direct search method has convergence properties comparable to those of existing methods in addition to being able to solve larger problems more effectively.

Suggested Citation

  • Hvattum, Lars Magnus & Glover, Fred, 2009. "Finding local optima of high-dimensional functions using direct search methods," European Journal of Operational Research, Elsevier, vol. 195(1), pages 31-45, May.
    • Handle: RePEc:eee:ejores:v:195:y:2009:i:1:p:31-45
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00171-9
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Marti, Rafael & Laguna, Manuel & Glover, Fred, 2006. "Principles of scatter search," European Journal of Operational Research, Elsevier, vol. 169(2), pages 359-372, March.
    2. Hedar, Abdel-Rahman & Fukushima, Masao, 2006. "Tabu Search directed by direct search methods for nonlinear global optimization," European Journal of Operational Research, Elsevier, vol. 170(2), pages 329-349, April.
    3. Chelouah, Rachid & Siarry, Patrick, 2005. "A hybrid method combining continuous tabu search and Nelder-Mead simplex algorithms for the global optimization of multiminima functions," European Journal of Operational Research, Elsevier, vol. 161(3), pages 636-654, March.
    4. Herrera, F. & Lozano, M. & Molina, D., 2006. "Continuous scatter search: An analysis of the integration of some combination methods and improvement strategies," European Journal of Operational Research, Elsevier, vol. 169(2), pages 450-476, March.
    5. Francisco J. Solis & Roger J.-B. Wets, 1981. "Minimization by Random Search Techniques," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 19-30, February.
    6. Chelouah, Rachid & Siarry, Patrick, 2003. "Genetic and Nelder-Mead algorithms hybridized for a more accurate global optimization of continuous multiminima functions," European Journal of Operational Research, Elsevier, vol. 148(2), pages 335-348, July.
    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. Jianfeng Liu & Nikolaos Ploskas & Nikolaos V. Sahinidis, 2019. "Tuning BARON using derivative-free optimization algorithms," Journal of Global Optimization, Springer, vol. 74(4), pages 611-637, August.
    2. Schmitt, Thomas G. & Kumar, Sanjay & Stecke, Kathryn E. & Glover, Fred W. & Ehlen, Mark A., 2017. "Mitigating disruptions in a multi-echelon supply chain using adaptive ordering," Omega, Elsevier, vol. 68(C), pages 185-198.
    3. Pinto, Roberto, 2016. "Stock rationing under a profit satisficing objective," Omega, Elsevier, vol. 65(C), pages 55-68.
    4. Michele Samorani & Yang Wang & Yang Wang & Zhipeng Lv & Fred Glover, 2019. "Clustering-driven evolutionary algorithms: an application of path relinking to the quadratic unconstrained binary optimization problem," Journal of Heuristics, Springer, vol. 25(4), pages 629-642, October.
    5. Jean-David Fermanian & Dragan Radulovic & Marten Wegkamp, 2013. "A Asymptotic Total Variation Test for Copulas," Working Papers 2013-25, Center for Research in Economics and Statistics.
    6. Kammerdiner, A.R. & Pasiliao, E.L., 2014. "In and out forests on combinatorial landscapes," European Journal of Operational Research, Elsevier, vol. 236(1), pages 78-84.
    7. Qinghua Gu & Xuexian Li & Song Jiang, 2019. "Hybrid Genetic Grey Wolf Algorithm for Large-Scale Global Optimization," Complexity, Hindawi, vol. 2019, pages 1-18, February.
    8. Luis Rios & Nikolaos Sahinidis, 2013. "Derivative-free optimization: a review of algorithms and comparison of software implementations," Journal of Global Optimization, Springer, vol. 56(3), pages 1247-1293, July.

    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. Gouvêa, Érica J.C. & Regis, Rommel G. & Soterroni, Aline C. & Scarabello, Marluce C. & Ramos, Fernando M., 2016. "Global optimization using q-gradients," European Journal of Operational Research, Elsevier, vol. 251(3), pages 727-738.
    2. Herrera, F. & Lozano, M. & Molina, D., 2006. "Continuous scatter search: An analysis of the integration of some combination methods and improvement strategies," European Journal of Operational Research, Elsevier, vol. 169(2), pages 450-476, March.
    3. M. Bierlaire & M. Thémans & N. Zufferey, 2010. "A Heuristic for Nonlinear Global Optimization," INFORMS Journal on Computing, INFORMS, vol. 22(1), pages 59-70, February.
    4. Mariani, Viviana Cocco & Coelho, Leandro dos Santos, 2011. "A hybrid shuffled complex evolution approach with pattern search for unconstrained optimization," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 81(9), pages 1901-1909.
    5. Garcia-Martinez, C. & Lozano, M. & Herrera, F. & Molina, D. & Sanchez, A.M., 2008. "Global and local real-coded genetic algorithms based on parent-centric crossover operators," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1088-1113, March.
    6. Nantiwat Pholdee & Sujin Bureerat, 2016. "Hybrid real-code ant colony optimisation for constrained mechanical design," International Journal of Systems Science, Taylor & Francis Journals, vol. 47(2), pages 474-491, January.
    7. Kaelo, P. & Ali, M.M., 2007. "Integrated crossover rules in real coded genetic algorithms," European Journal of Operational Research, Elsevier, vol. 176(1), pages 60-76, January.
    8. Morteza Ahandani & Mohammad-Taghi Vakil-Baghmisheh & Mohammad Talebi, 2014. "Hybridizing local search algorithms for global optimization," Computational Optimization and Applications, Springer, vol. 59(3), pages 725-748, December.
    9. Abraham Duarte & Rafael Martí & Fred Glover & Francisco Gortazar, 2011. "Hybrid scatter tabu search for unconstrained global optimization," Annals of Operations Research, Springer, vol. 183(1), pages 95-123, March.
    10. Wang, Yong-Jun & Zhang, Jiang-She & Zhang, Gai-Ying, 2007. "A dynamic clustering based differential evolution algorithm for global optimization," European Journal of Operational Research, Elsevier, vol. 183(1), pages 56-73, November.
    11. Noordhoek, Marije & Dullaert, Wout & Lai, David S.W. & de Leeuw, Sander, 2018. "A simulation–optimization approach for a service-constrained multi-echelon distribution network," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 292-311.
    12. Maenhout, Broos & Vanhoucke, Mario, 2010. "A hybrid scatter search heuristic for personalized crew rostering in the airline industry," European Journal of Operational Research, Elsevier, vol. 206(1), pages 155-167, October.
    13. Tammy Drezner & Zvi Drezner, 2019. "Cooperative Cover of Uniform Demand," Networks and Spatial Economics, Springer, vol. 19(3), pages 819-831, September.
    14. Schlereth, Christian & Stepanchuk, Tanja & Skiera, Bernd, 2010. "Optimization and analysis of the profitability of tariff structures with two-part tariffs," European Journal of Operational Research, Elsevier, vol. 206(3), pages 691-701, November.
    15. Sels, Veronique & Craeymeersch, Kjeld & Vanhoucke, Mario, 2011. "A hybrid single and dual population search procedure for the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 215(3), pages 512-523, December.
    16. Weitao Sun & Yuan Dong, 2011. "Study of multiscale global optimization based on parameter space partition," Journal of Global Optimization, Springer, vol. 49(1), pages 149-172, January.
    17. S.-C. Horng & S.-Y. Lin, 2009. "Ordinal Optimization of G/G/1/K Polling Systems with k-Limited Service Discipline," Journal of Optimization Theory and Applications, Springer, vol. 140(2), pages 213-231, February.
    18. Prietula, Michael J. & Watson, Harry S., 2008. "When behavior matters: Games and computation in A Behavioral Theory of the Firm," Journal of Economic Behavior & Organization, Elsevier, vol. 66(1), pages 74-94, April.
    19. Pavlos S. Georgilakis, 2020. "Review of Computational Intelligence Methods for Local Energy Markets at the Power Distribution Level to Facilitate the Integration of Distributed Energy Resources: State-of-the-art and Future Researc," Energies, MDPI, vol. 13(1), pages 1-37, January.
    20. Witanowski, Ł. & Klonowicz, P. & Lampart, P. & Suchocki, T. & Jędrzejewski, Ł. & Zaniewski, D. & Klimaszewski, P., 2020. "Optimization of an axial turbine for a small scale ORC waste heat recovery system," Energy, Elsevier, vol. 205(C).

    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:eee:ejores:v:195:y:2009:i:1:p:31-45. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.