Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
New Perspective on Slack Variables Applications to Singular Optimization Problems Read chapter Read first chapter

2019 | OriginalPaper | Chapter

Piecewise Linear Bounding Functions for Univariate Global Optimization

Authors : Oleg Khamisov, Mikhail Posypkin, Alexander Usov

Published in: Optimization and Applications

Publisher: Springer International Publishing

Log in

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

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.

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 Improved Polynomial Time Approximation Scheme for Capacitated Vehicle Routing Problem with Time Windows
next chapter The Scalability Analysis of a Parallel Tree Search Algorithm
Literature
1.
2.
3.
Breiman, L., Cutler, A.: A deterministic algorithm for global optimization. Math. Program. 58(1–3), 179–199 (1993)MathSciNetCrossRef
4.
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.
Ershov, A., Khamisov, O.V.: Automatic global optimization. Diskretnyi Analiz i Issledovanie Operatsii 11(2), 45–68 (2004)MathSciNet
6.
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.
Evtushenko, Y., Posypkin, M.: A deterministic approach to global box-constrained optimization. Optimization Letters 7(4), 819–829 (2013)MathSciNetCrossRef
8.
Floudas, C., Gounaris, C.: A review of recent advances in global optimization. J. Global Optim. 45(1), 3–38 (2009)MathSciNetCrossRef
9.
Gergel, V., Grishagin, V., Israfilov, R.: Local tuning in nested scheme of global optimization. Procedia Comput. Sci. 51, 865–874 (2015)CrossRef
10.
Hansen, E., Walster, G.W.: Global Optimization Using Interval Analysis: Revised and Expanded. CRC Press, New York (2003)
11.
Horst, R., Pardalos, P.M.: Handbook of Global Optimization, vol. 2. Springer Science & Business Media, Dordrecht (2013)MATH
12.
Khajavirad, A., Sahinidis, N.: Convex envelopes of products of convex and component-wise concave functions. J. Global Optim. 52(3), 391–409 (2012)MathSciNetCrossRef
13.
14.
15.
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.
Pardalos, P.M., Rosen, J.: Reduction of nonlinear integer separable programming problems. Int. J. Comput. Math. 24(1), 55–64 (1988)CrossRef
17.
Paulavičius, R., Žilinskas, J.: Simplicial Global Optimization. Springer, New York (2014). 10.1007/978-1-4614-9093-7CrossRef
18.
Pijavskij, S.: An algorithm for finding the global extremum of function. Optimal Decisions 2, 13–24 (1967)
19.
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.
Ratz, D.: An optimized interval slope arithmetic and its application. Inst. für Angewandte Mathematik (1996)
21.
Ratz, D.: A nonsmooth global optimization technique using slopes: the one-dimensional case. J. Global Optim. 14(4), 365–393 (1999)MathSciNetCrossRef
22.
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.
Sergeyev, Y.D.: An information global optimization algorithm with local tuning. SIAM J. Optim. 5(4), 858–870 (1995)MathSciNetCrossRef
24.
Sergeyev, Y.D.: Global one-dimensional optimization using smooth auxiliary functions. Math. Program. 81(1), 127–146 (1998)MathSciNetCrossRef
25.
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.
Shubert, B.O.: A sequential method seeking the global maximum of a function. SIAM J. Numer. Anal. 9(3), 379–388 (1972)MathSciNetCrossRef
27.
Strekalovsky, A.S.: Global optimality conditions for nonconvex optimization. J. Global Optim. 12(4), 415–434 (1998)MathSciNetCrossRef
28.
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.
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
Metadata
Title
Piecewise Linear Bounding Functions for Univariate Global Optimization
Authors
Oleg Khamisov
Mikhail Posypkin
Alexander Usov
Copyright Year
2019
Book
Optimization and Applications

Print ISBN: 978-3-030-10933-2

Electronic ISBN: 978-3-030-10934-9

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-030-10934-9_13

Premium Partner

    Image Credits