Skip to main content
SpringerLink
Log in

A deterministic approach to global box-constrained optimization

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

A deterministic global optimization algorithm for box-constrained problems is presented. The proposed approach is based on well-known non-uniform space covering technique. In the paper this approach is further elaborated. We propose a new techniques that enables a significant reduction of the search space by means of dropping parts of processed boxes. Also a new quadratic underestimation for the objective function based on hessian eigenvalues bounds is presented. It is shown how this underestimation can be improved by exploiting the first-order optimality conditions. In the experimental section we compare the proposed approach with existing methods and programming tools. Numerical tests indicate that the proposed algorithm is highly competitive with considered methods.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Evtushenko Yu.: Numerical methods for finding global extreme (case of a non-uniform mesh). U.S.S.R. Comput. Maths. Math. Phys 11(6), 38–54 (1971)

    Article  Google Scholar 

  2. Evtushenko Yu.G., Potapov M.A., Korotkich V.V.: Numerical Methods for Global Optimization. Recent Advances in Global Optimization, pp. 274–299. Princeton University Press, Oxford (1992)

    Google Scholar 

  3. Evtushenko, Yu., Malkova, V., Stanevichyus, A.: Parallel global optimization of functions of several variables. Comput. Math. Math. Phys. 49(2), 246–260 (2009). MAIK Nauka. doi:10.1134/S0965542509020055

    Google Scholar 

  4. Kearfott R.B.: Rigorous Global Search: Continuous Problems. Kluwer, Dordrecht (1996)

    Book  MATH  Google Scholar 

  5. Hansen E., Wastler G.: Global Optimization Using Interval Analysis: Revised and Expanded. Dekker, New York (2004)

    MATH  Google Scholar 

  6. Tawarmalani M., Sahinidis N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer, Dordrecht (2002)

    MATH  Google Scholar 

  7. Strongin R.G., Sergeyev Ya.D.: Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms. Kluwer, Dordrecht (2000)

    MATH  Google Scholar 

  8. Pinter J.D.: Global Optimization in Action. Kluwer, Dordrecht (1996)

    Book  MATH  Google Scholar 

  9. Ratschek H., Rokne J.: New Computer Methods for Global Optimization (Ellis Horwood Books in Information Technology). Horwood, Buckinghamshire (1988)

    Google Scholar 

  10. Nesterov Y.: Introductory Lectures on Convex Optimization: A Basic Course (Applied Optimization). Springer, Netherlands (2003)

    Google Scholar 

  11. Evtushenko Yu., Posypkin M., Sigal I.: A framework for parallel large-scale global optimization. Comput. Sci. Res. Development 23(3), 211–215 (2009)

    Article  Google Scholar 

  12. http://www.gams.com/. Accessed 19 Feb 2012

  13. Tawarmalani M., Sahinidis N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103(2), 225–249 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  14. http://www.lindo.com/. Accessed 19 Feb 2012

  15. Pardalos P.M., Romeijn E., Tuy H.: Recent developments and trends in global optimization. J. Comput. Appl. Math. 124(1–2), 209–228 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  16. Pardalos, P.M., Resende, M. (eds): Handbook of Applied Optimization. Oxford University Press, Oxford (2002)

    MATH  Google Scholar 

  17. Piyavskii S.A.: An algorithm for finding the absolute extremum of a function. USSR Comput. Math. Math. Phys. 12, 57–67 (1972)

    Article  Google Scholar 

  18. Shubert B.: A sequential method seeking the global maximum of a function. SIAM J. Numer. Anal. 9, 379–388 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  19. Jones D.R., Perttunen C.D., Stuckman B.E.: Lipschitzian optimization without the Lipschitz constant. J. Optim. Theory Appl. 79(1), 157–181 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  20. Jones D.R.: The DIRECT global optimization algorithm. In: Floudas, A., Pardalos, P. (eds) Encyclopedia of Optimization, pp. 725–735. Springer, Berlin (1999)

    Google Scholar 

  21. Gergel V.P.: A global optimization algorithm for multivariate functions with Lipschitzian first derivatives. J. Global Optim. 10, 257–281 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  22. Sergeyev Ya.D.: Global one-dimensional optimization using smooth auxiliary functions. Math. Program. 81(1), 127–146 (1998)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computing Centre of Russian Academy of Sciences, Moscow, Russia

    Yury Evtushenko

  2. Institute for Systems Analysis of Russian Academy of Sciences, Moscow, Russia

    Mikhail Posypkin

Authors
  1. Yury Evtushenko
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mikhail Posypkin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mikhail Posypkin.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Evtushenko, Y., Posypkin, M. A deterministic approach to global box-constrained optimization. Optim Lett 7, 819–829 (2013). https://doi.org/10.1007/s11590-012-0452-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-012-0452-1

Keywords

Search

Navigation