Top

Published in:

2015 | OriginalPaper | Chapter

On Deterministic Diagonal Methods for Solving Global Optimization Problems with Lipschitz Gradients

Authors : Yaroslav D. Sergeyev, Dmitri E. Kvasov

Published in: Optimization, Control, and Applications in the Information Age

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this chapter, a global optimization problem is considered where both the objective function f(x) and its gradient ∇f(x) are multidimensional black-box functions. It is supposed that ∇f(x) satisfies the Lipschitz condition over the search hyperinterval with an unknown Lipschitz constant K. Different techniques for estimating K are presented and their advantages and disadvantages are emphasized. In what regards exploring the multidimensional search domain, several adaptive partitioning strategies are discussed that can be applied in Lipschitz global optimization methods: (1) one-point-based algorithms evaluating the objective function and its gradient at one point within each subregion; (2) diagonal partitions where f(x) and ∇f(x) are evaluated at two points within each subregion; (3) more complex partitions based, for instance, on simplices or auxiliary functions of various nature. This chapter deals with diagonal deterministic methods that show a promising performance both in tests and applications. Several geometric methods based on diagonal partitions and auxiliary functions are presented and compared on eight hundred of differentiable problems randomly produced by the GKLS-generator of classes of test functions.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter A Time-Indexed Generalized Vehicle Routing Model and Stabilized Column Generation for Military Aircraft Mission Planning

next chapter Optimization of Design Parameters for Active Control of Smart Piezoelectric Structures

Baritompa, W., Cutler, A.: Accelerations for global optimization covering methods using second derivatives. J. Glob. Optim. 4(3), 329–341 (1994)

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

Evtushenko, Y.G., Posypkin, M.A.: A deterministic approach to global box-constrained optimization. Optim. Lett. 7(4), 819–829 (2013)

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

Fowkes, J.M., Gould, N.I.M., Farmer, C.L.: A branch and bound algorithm for the global optimization of Hessian Lipschitz continuous functions. J. Glob. Optim. 56(4), 1791–1815 (2013)

Gaviano, M., Lera, D., Kvasov, D.E., Sergeyev, Y.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)

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

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)

10.

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

11.

Gillard, J.W., Zhigljavsky, A.A.: Stochastic algorithms for solving structured low-rank matrix approximation problems. Commun. Nonlinear Sci. Numer. Simul. 21(1–3), 70–88 (2015)

12.

Gorodetsky, S.Y.: Paraboloid triangulation methods in solving multiextremal optimization problems with constraints for a class of functions with Lipschitz directional derivatives. Vestnik of Lobachevsky State University of Nizhni Novgorod 1(1), 144–155 (2012) (in Russian)

13.

Grishagin, V.A.: Operating characteristics of some global search algorithms. In: Problems of Stochastic Search, vol. 7, pp. 198–206. Zinatne, Riga (1978) (in Russian)

14.

Grishagin, V.A., Sergeyev, Y.D., Strongin, R.G.: Parallel characteristic algorithms for solving problems of global optimization. J. Glob. Optim. 10(2), 185–206 (1997)

15.

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

16.

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

17.

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

18.

Kvasov, D.E.: Multidimensional Lipschitz global optimization based on efficient diagonal partitions. 4OR Q. J. Oper. Res. 6(4), 403–406 (2008)

19.

Kvasov, D.E., Sergeyev, Y.D.: Multidimensional global optimization algorithm based on adaptive diagonal curves. Comput. Math. Math. Phys. 43(1), 42–59 (2003)

20.

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)

21.

Kvasov, D.E., Sergeyev, Y.D.: Lipschitz gradients for global optimization in a one-point-based partitioning scheme. J. Comput. Appl. Math. 236(16), 4042–4054 (2012)

22.

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

23.

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

24.

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

25.

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

26.

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)

27.

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(1–3), 328–342 (2015)

28.

MacLagan, D., Sturge, T., Baritompa, W.: Equivalent methods for global optimization. In: Floudas, C.A., Pardalos, P.M. (eds.) State of the Art in Global Optimization, pp. 201–212. Kluwer Academic Publishers, Dordrecht (1996)

29.

Molinaro, A., Pizzuti, C., Sergeyev, Y.D.: Acceleration tools for diagonal information global optimization algorithms. Comput. Optim. Appl. 18(1), 5–26 (2001)

30.

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

31.

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)

32.

Pintér, J.D.: Extended univariate algorithms for N-dimensional global optimization. Computing 36(1–2), 91–103 (1986)

33.

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

34.

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

35.

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

36.

Sergeyev, Y.D.: A method using local tuning for minimizing functions with Lipschitz derivatives. In: Bomze, I.M., Csendes, T., Horst, R., Pardalos, P.M. (eds.) Developments in Global Optimization, pp. 199–216. Kluwer Academic Publishers, Dordrecht (1997)

37.

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

38.

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

39.

Sergeyev, Y.D.: Multidimensional global optimization using the first derivatives. Comput. Math. Math. Phys. 39(5), 711–720 (1999)

40.

Sergeyev, Y.D.: An efficient strategy for adaptive partition of N-dimensional intervals in the framework of diagonal algorithms. J. Optim. Theory Appl. 107(1), 145–168 (2000)

41.

Sergeyev, Y.D.: Efficient partition of N-dimensional intervals in the framework of one-point-based algorithms. J. Optim. Theory Appl. 124(2), 503–510 (2005)

42.

Sergeyev, Y.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)

43.

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

44.

Sergeyev, Y.D., Kvasov, D.E.: Lipschitz global optimization. In: Cochran, J.J. et al. (eds.) Wiley Encyclopedia of Operations Research and Management Science, vol. 4, pp. 2812–2828. Wiley, New York (2011)

45.

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

46.

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)

47.

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

48.

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

49.

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

Title: On Deterministic Diagonal Methods for Solving Global Optimization Problems with Lipschitz Gradients
Authors: Yaroslav D. Sergeyev
Dmitri E. Kvasov
Publisher: Springer International Publishing
Book: Optimization, Control, and Applications in the Information Age
Print ISBN: 978-3-319-18566-8

Electronic ISBN: 978-3-319-18567-5

Copyright Year: 2015
DOI: https://doi.org/10.1007/978-3-319-18567-5_16

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner