Skip to main content
SpringerLink
Log in

A univariate global search working with a set of Lipschitz constants for the first derivative

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

Abstract

In the paper, a global optimization problem is considered where the objective function f (x) is univariate, black-box, and its first derivative f ′(x) satisfies the Lipschitz condition with an unknown Lipschitz constant K. In the literature, there exist methods solving this problem by using an a priori given estimate of K, its adaptive estimates, and adaptive estimates of local Lipschitz constants. Algorithms working with a number of Lipschitz constants for f ′(x) chosen from a set of possible values are not known in spite of the fact that a method working in this way with Lipschitz objective functions, DIRECT, has been proposed in 1993. A new geometric method evolving its ideas to the case of the objective function having a Lipschitz derivative is introduced and studied in this paper. Numerical experiments executed on a number of test functions show that the usage of derivatives allows one to obtain, as it is expected, an acceleration in comparison with the DIRECT algorithm.

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. Baker, C.A., Watson, L.T., Grossman, B., Mason, W.H., Haftka, R.T.: Parallel global aircraft configuration design space exploration. In: Paprzycki, M, Tarricone, L., Yang, L.T. (eds.) Practical parallel computing. Special Issue of the Inernational Journal of Computer Research, vol. 10 (4), pp. 79–96. Nova Science Publishers, New York (2001)

    Google Scholar 

  2. Bartholomew-Biggs M.C., Parkhurst S.C., Wilson S.P.: Using DIRECT to solve an aircraft routing problem. Comput. Optim. Appl. 21(3), 311–323 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  3. Breiman L., Cutler A.: A deterministic algorithm for global optimization. Math. Program. 58(1–3), 179–199 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  4. Carter R.G., Gablonsky J.M., Patrick A., Kelley C.T., Eslinger O.J.: Algorithms for noisy problems in gas transmission pipeline optimization. Optim. Eng. 2(2), 139–157 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  5. Cox S.E., Haftka R.T., Baker C.A., Grossman B., Mason W.H., Watson L.T.: A comparison of global optimization methods for the design of a high-speed civil transport. J. Glob. Optim. 21(4), 415–433 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  6. Daponte P., Grimaldi D., Molinaro A., Sergeyev Ya.D.: An algorithm for finding the zero-crossing of time signals with Lipschitzean derivatives. Measurement 16(1), 37–49 (1995)

    Article  Google Scholar 

  7. Daponte P., Grimaldi D., Molinaro A., Sergeyev Ya.D.: Fast detection of the first zero-crossing in a measurement signal set. Measurement 19(1), 29–39 (1996)

    Article  Google Scholar 

  8. Finkel D.E., Kelley C.T.: Additive scaling and the DIRECT algorithm. J. Glob. Optim. 36(4), 597–608 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  9. Gablonsky J.M., Kelley C.T.: A locally-biased form of the DIRECT algorithm. J. Glob. Optim. 21(1), 27–37 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  10. Gablonsky, J.M.: An implemention of the DIRECT algorithm. Technical report CRSC-TR98-29, Center for Research in Scientific Computation, North Carolina State University, Raleigh, NC, USA (1998)

  11. Gablonsky, J.M.: DIRECT v2.04 FORTRAN code with documentation. http://www4.ncsu.edu/~ctk/SOFTWARE/DIRECTv204.tar.gz (2001)

  12. Gablonsky, J.M.: Modifications of the DIRECT algorithm. PhD thesis, North Carolina State University, Raleigh, NC (2001)

  13. Gaviano M., Lera D., Kvasov D.E., Sergeyev Ya.D.: Algorithm 829: Software for generation of classes of test functions with known local and global minima for global optimization. ACM Trans. Math. Softw. 29(4), 469–480 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  14. Gergel V.P.: A global optimization algorithm for multivariate function with Lipschitzian first derivatives. J. Glob. Optim. 10(3), 257–281 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  15. Graf P.A., Kim K., Jones W.B., Wang L.-W.: Surface passivation optimization using DIRECT. J. Comput. Phys. 224(2), 824–835 (2007)

    Article  MATH  Google Scholar 

  16. He J., Verstak A., Watson L.T., Sosonkina M.: Design and implementation of a massively parallel version of DIRECT. Comput. Optim. Appl. 40(2), 217–245 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  17. He J., Watson L.T., Ramakrishnan N., Shaffer C.A., Verstak A., Jiang J., Bae K., Tranter W.H.: Dynamic data structures for a direct search algorithm. Comput. Optim. Appl. 23(1), 5–25 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  18. Horst, R., Pardalos, P.M. (eds.): Handbook of Global Optimization, vol. 1. Kluwer, Dordrecht (1995)

    Google Scholar 

  19. Horst R., Tuy H.: Global Optimization—Deterministic Approaches. Springer, Berlin (1996)

    MATH  Google Scholar 

  20. 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  MATH  MathSciNet  Google Scholar 

  21. Jones D.R.: The DIRECT global optimization algorithm. In: Floudas, C.A., Pardalos, P.M.(eds) Encyclopedia of Optimization, vol. 1, pp. 431–440. Kluwer, Dordrecht (2001)

    Chapter  Google Scholar 

  22. Ljungberg K., Holmgren S., Carlborg Ö.: Simultaneous search for multiple QTL using the global optimization algorithm DIRECT. Bioinformatics 20(12), 1887–1895 (2004)

    Article  Google Scholar 

  23. Moles C.G., Mendes P., Banga J.R.: Parameter estimation in biochemical pathways: a comparison of global optimization methods. Genome Res. 13(11), 2467–2474 (2003)

    Article  Google Scholar 

  24. Panning T.D., Watson L.T., Allen N.A., Chen K.C., Shaffer C.A., Tyson J.J.: Deterministic parallel global parameter estimation for a model of the budding yeast cell cycle. J. Glob. Optim. 40(4), 719–738 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  25. Pintér J.: Global Optimization in Action (Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications). Kluwer, Dordrecht (1996)

    Google Scholar 

  26. Pintér J.: Global optimization: software, test problems, and applications. In: Pardalos, P.M., Romeijn, H.E.(eds) Handbook of Global Optimization, vol. 2, pp. 515–569. Kluwer, Dordrecht (2002)

    Google Scholar 

  27. Preparata F.P., Shamos M.I.: Computational Geometry: An Introduction. Springer, New York (1993)

    Google Scholar 

  28. Sergeyev Ya.D., Daponte P., Grimaldi D., Molinaro A.: Two methods for solving optimization problems arising in electronic measurements and electrical engineering. SIAM J. Optim. 10(1), 1–21 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  29. Sergeyev Ya.D., Kvasov D.E.: Global search based on efficient diagonal partitions and a set of Lipschitz constants. SIAM J. Optim. 16(3), 910–937 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  30. Sergeyev, Ya.D., Kvasov, D.E.: Diagonal Global Optimization Methods (in Russian). FizMatLit, Moscow (2008)

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

    Article  MathSciNet  Google Scholar 

  32. Stephens C.P., Baritompa W.: Global optimization requires global information. J. Optim. Theory Appl. 96(3), 575–588 (1998)

    Article  MATH  MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

  34. Törn A., Žilinskas A.: Global Optimization. Lecture Notes in Computer Science, vol. 350. Springer, Berlin (1989)

    Google Scholar 

  35. Watson L.T., Baker C.: A fully-distributed parallel global search algorithm. Eng. Comput. 18(1/2), 155–169 (2001)

    Article  MATH  Google Scholar 

  36. Zhu H., Bogy D.B.: Hard disc drive air bearing design: modified DIRECT algorithm and its application to slider air bearing surface optimization. Tribol. Int. 37(2), 193–201 (2004)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. DEIS, University of Calabria, Via P. Bucci 42C, 87036, Rende (CS), Italy

    Dmitri E. Kvasov & Yaroslav D. Sergeyev

  2. Software Department, N.I. Lobatchevsky State University, Nizhni Novgorod, Russia

    Dmitri E. Kvasov & Yaroslav D. Sergeyev

Authors
  1. Dmitri E. Kvasov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yaroslav D. Sergeyev
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yaroslav D. Sergeyev.

Additional information

This research was supported by the RFBR grant 07-01-00467-a and the grant 4694.2008.9 for supporting the leading research groups awarded by the President of the Russian Federation.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kvasov, D.E., Sergeyev, Y.D. A univariate global search working with a set of Lipschitz constants for the first derivative. Optim Lett 3, 303–318 (2009). https://doi.org/10.1007/s11590-008-0110-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-008-0110-9

Keywords

Search

Navigation