Skip to main content
SpringerLink
Log in

Derivative-Free Local Tuning and Local Improvement Techniques Embedded in the Univariate Global Optimization

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

Geometric and information frameworks for constructing global optimization algorithms are considered, and several new ideas to speed up the search are proposed. The accelerated global optimization methods automatically realize a local behavior in the promising subregions without the necessity to stop the global optimization procedure. Moreover, all the trials executed during the local phases are used also in the course of the global ones. The resulting geometric and information global optimization methods have a similar structure, and a smart mixture of new and traditional computational steps leads to 22 different global optimization algorithms. All of them are studied and numerically compared on three test sets including 120 benchmark functions and 4 applied problems.

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.

Fig. 1

Similar content being viewed by others

References

  1. Kvasov, D.E., Sergeyev, Y.D.: Lipschitz global optimization methods in control problems. Autom. Remote Control 74(9), 1435–1448 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  2. Hamacher, K.: On stochastic global optimization of one-dimensional functions. Phys. A Stat. Mech. Appl. 354, 547–557 (2005)

    Article  Google Scholar 

  3. Johnson, D.E.: Introduction to Filter Theory. Prentice Hall Inc., New Jersey (1976)

    Google Scholar 

  4. Žilinskas, A.: Optimization of one-dimensional multimodal functions: algorithm AS 133. Appl. Stat. 23, 367–375 (1978)

    Article  MATH  Google Scholar 

  5. Sergeyev, Y.D., Grishagin, V.A.: A parallel algorithm for finding the global minimum of univariate functions. J. Optim. Theory Appl. 80(3), 513–536 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  6. Kvasov, D.E., Menniti, D., Pinnarelli, A., Sergeyev, Y.D., Sorrentino, N.: Tuning fuzzy power-system stabilizers in multi-machine systems by global optimization algorithms based on efficient domain partitions. Electr. Power Syst. Res. 78(7), 1217–1229 (2008)

    Article  Google Scholar 

  7. Kvasov, D.E., Sergeyev, Y.D.: Deterministic approaches for solving practical black-box global optimization problems. Adv. Eng. Softw. 80, 58–66 (2015)

    Article  Google Scholar 

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

    Book  MATH  Google Scholar 

  9. Sergeyev, Y.D., Kvasov, D.E.: Diagonal Global Optimization Methods. Fizmatlit, Moscow (2008). (in Russian)

    MATH  Google Scholar 

  10. Sergeyev, Y.D., Kvasov, D.E., Khalaf, F.M.H.: A one-dimensional local tuning algorithm for solving GO problems with partially defined constraints. Optim. Lett. 1(1), 85–99 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  11. Strongin, R.G., Gergel, V.P., Grishagin, V.A., Barkalov, K.A.: Parallel Computing for Global Optimization Problems. Moscow University Press, Moscow (2013). (in Russian)

    Google Scholar 

  12. Liuzzi, G., Lucidi, S., Piccialli, V., Sotgiu, A.: A magnetic resonance device designed via global optimization techniques. Math. Program. 101(2), 339–364 (2004)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

  14. Calvin, J.M., Žilinskas, A.: One-dimensional global optimization for observations with noise. Comput. Math. Appl. 50(1–2), 157–169 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  15. Calvin, J.M., Chen, Y., Žilinskas, A.: An adaptive univariate global optimization algorithm and its convergence rate for twice continuously differentiable functions. J. Optim. Theory Appl. 155(2), 628–636 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  16. Gergel, V.P.: A global search algorithm using derivatives. In: Neymark, Y.I. (ed.) Systems Dynamics and Optimization, pp. 161–178. N. Novgorod University Press, Novgorod (1992). (in Russian)

    Google Scholar 

  17. Gillard, J.W., Zhigljavsky, A.A.: Optimization challenges in the structured low rank approximation problem. J. Glob. Optim. 57(3), 733–751 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  18. Gillard, J.W., Kvasov, D.E.: Lipschitz optimization methods for fitting a sum of damped sinusoids to a series of observations. Stat. Interface (2016, in press)

  19. Žilinskas, A.: A one-step worst-case optimal algorithm for bi-objective univariate optimization. Optim. Lett. 8(7), 1945–1960 (2014)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

  21. Molinaro, A., Sergeyev, Y.D.: Finding the minimal root of an equation with the multiextremal and nondifferentiable left-hand part. Numer. Algorithms 28(1–4), 255–272 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  22. Sergeyev, Y.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  MathSciNet  MATH  Google Scholar 

  23. Strongin, R.G., Sergeyev, Y.D.: Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms. Kluwer Academic Publishers, Dordrecht (2000). (2nd ed., 2012; 3rd ed., 2014, Springer, New York)

    Book  MATH  Google Scholar 

  24. Casado, L.G., García, I., Sergeyev, Y.D.: Interval algorithms for finding the minimal root in a set of multiextremal non-differentiable one-dimensional functions. SIAM J. Sci. Comput. 24(2), 359–376 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  25. Sergeyev, Y.D., Famularo, D., Pugliese, P.: Index branch-and-bound algorithm for Lipschitz univariate global optimization with multiextremal constraints. J. Glob. Optim. 21(3), 317–341 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  26. Csendes, T. (ed.): Developments in Reliable Computing. Kluwer Academic Publishers, Dordrecht (1999)

    MATH  Google Scholar 

  27. Paulavičius, R., Žilinskas, J., Grothey, A.: Investigation of selection strategies in branch and bound algorithm with simplicial partitions and combination of Lipschitz bounds. Optim. Lett. 4(2), 173–183 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  28. Paulavičius, R., Sergeyev, Y.D., Kvasov, D.E., Žilinskas, J.: Globally-biased DISIMPL algorithm for expensive global optimization. J. Glob. Optim. 59(2–3), 545–567 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  29. Paulavičius, R., Žilinskas, J.: Simplicial Global Optimization. Springer Briefs in Optimization. Springer, New York (2014)

    Book  MATH  Google Scholar 

  30. Sergeyev, Y.D., Strongin, R.G., Lera, D.: Introduction to Global Optimization Exploiting Space-Filling Curves. Springer Briefs in Optimization. Springer, New York (2013)

    Book  MATH  Google Scholar 

  31. Lera, D., Sergeyev, Y.D.: Deterministic global optimization using space-filling curves and multiple estimates of Lipschitz and Hölder constants. Commun. Nonlinear Sci. Numer. Simul. 23, 328–342 (2015)

    Article  MathSciNet  Google Scholar 

  32. Kvasov, D.E., Sergeyev, Y.D.: A univariate global search working with a set of Lipschitz constants for the first derivative. Optim. Lett. 3(2), 303–318 (2009)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  34. Sergeyev, Y.D., Kvasov, D.E.: A deterministic global optimization using smooth diagonal auxiliary functions. Commun. Nonlinear Sci. Numer. Simul. 21, 99–111 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  35. Sergeyev, Y.D., Kvasov, D.E.: On deterministic diagonal methods for solving global optimization problems with Lipschitz gradients. In: Migdalas, A., Karakitsiou, A. (eds.) Optimization, Control, and Applications in the Information Age, Springer Proceedings in Mathematics and Statistics, vol. 130, pp. 319–337. Springer, Switzerland (2015)

    Google Scholar 

  36. Gergel, V.P., Sergeyev, Y.D.: Sequential and parallel algorithms for global minimizing functions with Lipschitzian derivatives. Comput. Math. Appl. 37(4–5), 163–179 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  37. Lera, D., Sergeyev, Y.D.: Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives. SIAM J. Optim. 23(1), 508–529 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  38. Piyavskij, S.A.: An algorithm for finding the absolute extremum of a function. USSR Comput. Math. Math. Phys. 12(4), 57–67 (1972). (in Russian: Zh. Vychisl. Mat. Mat. Fiz., 12(4) (1972), pp. 888–896)

    Article  Google Scholar 

  39. Strongin, R.G.: Numerical Methods in Multiextremal Problems: Information-Statistical Algorithms. Nauka, Moscow (1978). (in Russian)

    MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  41. Strongin, R.G.: On the convergence of an algorithm for finding a global extremum. Eng. Cybern. 11, 549–555 (1973)

    MathSciNet  Google Scholar 

  42. Evtushenko, Y.G.: Numerical Optimization Techniques. Translations Series in Mathematics and Engineering. Springer, Berlin (1985)

    Book  Google Scholar 

  43. Žilinskas, A.: On similarities between two models of global optimization: statistical models and radial basis functions. J. Glob. Optim. 48(1), 173–182 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  44. Floudas, C.A., Pardalos, P.M. (eds.): Encyclopedia of Optimization (6 Volumes), 2nd edn. Springer, Berlin (2009)

    Google Scholar 

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

    MATH  Google Scholar 

  46. Zhigljavsky, A.A., Žilinskas, A.: Stochastic Global Optimization. Springer, New York (2008)

    MATH  Google Scholar 

  47. Hansen, P., Jaumard, B.: Lipschitz optimization. In: Horst, R., Pardalos, P.M. (eds.) Handbook of Global Optimization, vol. 1, pp. 407–493. Kluwer Academic Publishers, Dordrecht (1995)

    Chapter  Google Scholar 

  48. Pintér, J.D.: 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 Academic Publishers, Dordrecht (2002)

    Chapter  Google Scholar 

  49. Sergeyev, Y.D.: An information global optimization algorithm with local tuning. SIAM J. Optim. 5(4), 858–870 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  50. Sergeyev, Y.D.: A one-dimensional deterministic global minimization algorithm. Comput. Math. Math. Phys. 35(5), 705–717 (1995)

    MathSciNet  Google Scholar 

  51. Kvasov, D.E., Sergeyev, Y.D.: Univariate geometric Lipschitz global optimization algorithms. Numer. Algebra Contr. Optim. 2(1), 69–90 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  52. Kvasov, D.E., Pizzuti, C., Sergeyev, Y.D.: Local tuning and partition strategies for diagonal GO methods. Numer. Math. 94(1), 93–106 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  53. Sergeyev, Y.D.: Univariate global optimization with multiextremal non-differentiable constraints without penalty functions. Comput. Optim. Appl. 34(2), 229–248 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  54. Sergeyev, Y.D., Markin, D.L.: An algorithm for solving global optimization problems with nonlinear constraints. J. Glob. Optim. 7(4), 407–419 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  55. Gergel, A.V., Grishagin, V.A., Strongin, R.G.: Development of the parallel adaptive multistep reduction method. Vestn. Lobachevsky State Univ. Nizhni Novgorod 6(1), 216–222 (2013). (in Russian)

    Google Scholar 

  56. Gergel, V.P., Grishagin, V.A., Israfilov, R.A.: Local tuning in nested scheme of global optimization. Procedia Comput. Sci. 51, 865–874 (2015). (International conference on computational science ICCS 2015—computational science at the gates of nature)

    Article  Google Scholar 

  57. Sergeyev, Y.D.: On convergence of “Divide the Best” global optimization algorithms. Optimization 44(3), 303–325 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  58. Lera, D., Sergeyev, Y.D.: An information global minimization algorithm using the local improvement technique. J. Glob. Optim. 48(1), 99–112 (2010)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

This work was supported by the Project No. 15-11-30022 “Global optimization, supercomputing computations, and applications” of the Russian Science Foundation.

Author information

Authors and Affiliations

  1. Dipartimento di Ingegneria Informatica, Modellistica, Elettronica e Sistemistica, Università della Calabria, Rende, CS, Italy

    Yaroslav D. Sergeyev, Marat S. Mukhametzhanov & Dmitri E. Kvasov

  2. Department of Software and Supercomputing Technologies, Lobachevsky State University of Nizhni Novgorod, Nizhni Novgorod, Russia

    Yaroslav D. Sergeyev, Marat S. Mukhametzhanov & Dmitri E. Kvasov

  3. Dipartimento di Matematica e Informatica, Università di Cagliari, Cagliari, Italy

    Daniela Lera

Authors
  1. Yaroslav D. Sergeyev
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marat S. Mukhametzhanov
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dmitri E. Kvasov
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Daniela Lera
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yaroslav D. Sergeyev.

Additional information

Communicated by Alexander S. Strekalovsky.

Appendices

Appendix 1

See Table 10.

Table 10 Twenty test functions from [47] used in numerical experiments
Full size table

Appendix 2

See Table 11.

Table 11 Four one-dimensional test functions taken from practical applications
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sergeyev, Y.D., Mukhametzhanov, M.S., Kvasov, D.E. et al. Derivative-Free Local Tuning and Local Improvement Techniques Embedded in the Univariate Global Optimization. J Optim Theory Appl 171, 186–208 (2016). https://doi.org/10.1007/s10957-016-0947-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-016-0947-5

Keywords

Mathematics Subject Classification

Search

Navigation