Skip to main content

2019 | OriginalPaper | Buchkapitel

Piecewise Linear Bounding Functions for Univariate Global Optimization

verfasst von : Oleg Khamisov, Mikhail Posypkin, Alexander Usov

Erschienen in: Optimization and Applications

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The paper addresses the problem of constructing lower and upper bounding functions for univariate functions. This problem is of a crucial importance in global optimization where such bounds are used by deterministic methods to reduce the search area. It should be noted that bounding functions are expected to be relatively easy to construct and manipulate with. We propose to use piecewise linear estimators for bounding univariate functions. The rules proposed in the paper enable an automated synthesis of lower and upper bounds from the function’s expression in an algebraic form. Numerical examples presented in the paper demonstrate the high accuracy of the proposed bounds.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Literatur
1.
Zurück zum Zitat Baritompa, W.: Accelerations for a variety of global optimization methods. J. Global Optim. 4(1), 37–45 (1994)MathSciNetCrossRef Baritompa, W.: Accelerations for a variety of global optimization methods. J. Global Optim. 4(1), 37–45 (1994)MathSciNetCrossRef
2.
3.
Zurück zum Zitat Breiman, L., Cutler, A.: A deterministic algorithm for global optimization. Math. Program. 58(1–3), 179–199 (1993)MathSciNetCrossRef Breiman, L., Cutler, A.: A deterministic algorithm for global optimization. Math. Program. 58(1–3), 179–199 (1993)MathSciNetCrossRef
4.
Zurück zum Zitat Casado, L.G., MartÍnez, J.A., GarcÍa, I., Sergeyev, Y.D.: New interval analysis support functions using gradient information in a global minimization algorithm. J. Global Optim. 25(4), 345–362 (2003)MathSciNetCrossRef Casado, L.G., MartÍnez, J.A., GarcÍa, I., Sergeyev, Y.D.: New interval analysis support functions using gradient information in a global minimization algorithm. J. Global Optim. 25(4), 345–362 (2003)MathSciNetCrossRef
5.
Zurück zum Zitat Ershov, A., Khamisov, O.V.: Automatic global optimization. Diskretnyi Analiz i Issledovanie Operatsii 11(2), 45–68 (2004)MathSciNet Ershov, A., Khamisov, O.V.: Automatic global optimization. Diskretnyi Analiz i Issledovanie Operatsii 11(2), 45–68 (2004)MathSciNet
6.
Zurück zum Zitat Evtushenko, Y.G.: A numerical method of search for the global extremum of functions (scan on a nonuniform net). Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki 11(6), 1390–1403 (1971)MathSciNet Evtushenko, Y.G.: A numerical method of search for the global extremum of functions (scan on a nonuniform net). Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki 11(6), 1390–1403 (1971)MathSciNet
7.
Zurück zum Zitat Evtushenko, Y., Posypkin, M.: A deterministic approach to global box-constrained optimization. Optimization Letters 7(4), 819–829 (2013)MathSciNetCrossRef Evtushenko, Y., Posypkin, M.: A deterministic approach to global box-constrained optimization. Optimization Letters 7(4), 819–829 (2013)MathSciNetCrossRef
8.
Zurück zum Zitat Floudas, C., Gounaris, C.: A review of recent advances in global optimization. J. Global Optim. 45(1), 3–38 (2009)MathSciNetCrossRef Floudas, C., Gounaris, C.: A review of recent advances in global optimization. J. Global Optim. 45(1), 3–38 (2009)MathSciNetCrossRef
9.
Zurück zum Zitat Gergel, V., Grishagin, V., Israfilov, R.: Local tuning in nested scheme of global optimization. Procedia Comput. Sci. 51, 865–874 (2015)CrossRef Gergel, V., Grishagin, V., Israfilov, R.: Local tuning in nested scheme of global optimization. Procedia Comput. Sci. 51, 865–874 (2015)CrossRef
10.
Zurück zum Zitat Hansen, E., Walster, G.W.: Global Optimization Using Interval Analysis: Revised and Expanded. CRC Press, New York (2003) Hansen, E., Walster, G.W.: Global Optimization Using Interval Analysis: Revised and Expanded. CRC Press, New York (2003)
11.
Zurück zum Zitat Horst, R., Pardalos, P.M.: Handbook of Global Optimization, vol. 2. Springer Science & Business Media, Dordrecht (2013)MATH Horst, R., Pardalos, P.M.: Handbook of Global Optimization, vol. 2. Springer Science & Business Media, Dordrecht (2013)MATH
12.
Zurück zum Zitat Khajavirad, A., Sahinidis, N.: Convex envelopes of products of convex and component-wise concave functions. J. Global Optim. 52(3), 391–409 (2012)MathSciNetCrossRef Khajavirad, A., Sahinidis, N.: Convex envelopes of products of convex and component-wise concave functions. J. Global Optim. 52(3), 391–409 (2012)MathSciNetCrossRef
15.
Zurück zum Zitat 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)MathSciNetCrossRef 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)MathSciNetCrossRef
16.
Zurück zum Zitat Pardalos, P.M., Rosen, J.: Reduction of nonlinear integer separable programming problems. Int. J. Comput. Math. 24(1), 55–64 (1988)CrossRef Pardalos, P.M., Rosen, J.: Reduction of nonlinear integer separable programming problems. Int. J. Comput. Math. 24(1), 55–64 (1988)CrossRef
17.
Zurück zum Zitat Paulavičius, R., Žilinskas, J.: Simplicial Global Optimization. Springer, New York (2014). 10.1007/978-1-4614-9093-7CrossRef Paulavičius, R., Žilinskas, J.: Simplicial Global Optimization. Springer, New York (2014). 10.1007/978-1-4614-9093-7CrossRef
18.
Zurück zum Zitat Pijavskij, S.: An algorithm for finding the global extremum of function. Optimal Decisions 2, 13–24 (1967) Pijavskij, S.: An algorithm for finding the global extremum of function. Optimal Decisions 2, 13–24 (1967)
19.
Zurück zum Zitat Pintér, J.D.: Global Optimization in Action: Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications, vol. 6. Springer Science & Business Media, New York (2013) Pintér, J.D.: Global Optimization in Action: Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications, vol. 6. Springer Science & Business Media, New York (2013)
20.
Zurück zum Zitat Ratz, D.: An optimized interval slope arithmetic and its application. Inst. für Angewandte Mathematik (1996) Ratz, D.: An optimized interval slope arithmetic and its application. Inst. für Angewandte Mathematik (1996)
21.
Zurück zum Zitat Ratz, D.: A nonsmooth global optimization technique using slopes: the one-dimensional case. J. Global Optim. 14(4), 365–393 (1999)MathSciNetCrossRef Ratz, D.: A nonsmooth global optimization technique using slopes: the one-dimensional case. J. Global Optim. 14(4), 365–393 (1999)MathSciNetCrossRef
22.
Zurück zum Zitat Rosen, J.B., Pardalos, P.M.: Global minimization of large-scale constrained concave quadratic problems by separable programming. Math. Program. 34(2), 163–174 (1986)MathSciNetCrossRef Rosen, J.B., Pardalos, P.M.: Global minimization of large-scale constrained concave quadratic problems by separable programming. Math. Program. 34(2), 163–174 (1986)MathSciNetCrossRef
23.
Zurück zum Zitat Sergeyev, Y.D.: An information global optimization algorithm with local tuning. SIAM J. Optim. 5(4), 858–870 (1995)MathSciNetCrossRef Sergeyev, Y.D.: An information global optimization algorithm with local tuning. SIAM J. Optim. 5(4), 858–870 (1995)MathSciNetCrossRef
24.
Zurück zum Zitat Sergeyev, Y.D.: Global one-dimensional optimization using smooth auxiliary functions. Math. Program. 81(1), 127–146 (1998)MathSciNetCrossRef Sergeyev, Y.D.: Global one-dimensional optimization using smooth auxiliary functions. Math. Program. 81(1), 127–146 (1998)MathSciNetCrossRef
25.
Zurück zum Zitat Sergeyev, Y.D., Mukhametzhanov, M.S., Kvasov, D.E., Lera, D.: Derivative-free local tuning and local improvement techniques embedded in the univariate global optimization. J. Optim. Theory Appl. 171(1), 186–208 (2016)MathSciNetCrossRef Sergeyev, Y.D., Mukhametzhanov, M.S., Kvasov, D.E., Lera, D.: Derivative-free local tuning and local improvement techniques embedded in the univariate global optimization. J. Optim. Theory Appl. 171(1), 186–208 (2016)MathSciNetCrossRef
26.
Zurück zum Zitat Shubert, B.O.: A sequential method seeking the global maximum of a function. SIAM J. Numer. Anal. 9(3), 379–388 (1972)MathSciNetCrossRef Shubert, B.O.: A sequential method seeking the global maximum of a function. SIAM J. Numer. Anal. 9(3), 379–388 (1972)MathSciNetCrossRef
27.
Zurück zum Zitat Strekalovsky, A.S.: Global optimality conditions for nonconvex optimization. J. Global Optim. 12(4), 415–434 (1998)MathSciNetCrossRef Strekalovsky, A.S.: Global optimality conditions for nonconvex optimization. J. Global Optim. 12(4), 415–434 (1998)MathSciNetCrossRef
28.
Zurück zum Zitat Strongin, R.G., Sergeyev, Y.D.: Global Optimization with Non-convex Constraints: Sequential and Parallel Algorithms, vol. 45. Springer Science & Business Media, New York (2013)MATH Strongin, R.G., Sergeyev, Y.D.: Global Optimization with Non-convex Constraints: Sequential and Parallel Algorithms, vol. 45. Springer Science & Business Media, New York (2013)MATH
29.
Zurück zum Zitat Vinkó, T., Lagouanelle, J.L., Csendes, T.: A new inclusion function for optimization: Kite-the one dimensional case. J. Global Optim. 30(4), 435–456 (2004)MathSciNetCrossRef Vinkó, T., Lagouanelle, J.L., Csendes, T.: A new inclusion function for optimization: Kite-the one dimensional case. J. Global Optim. 30(4), 435–456 (2004)MathSciNetCrossRef
Metadaten
Titel
Piecewise Linear Bounding Functions for Univariate Global Optimization
verfasst von
Oleg Khamisov
Mikhail Posypkin
Alexander Usov
Copyright-Jahr
2019
DOI
https://doi.org/10.1007/978-3-030-10934-9_13