Abstract
We propose a branch-and-bound framework for the global optimization of unconstrained Hölder functions. The general framework is used to derive two algorithms. The first one is a generalization of Piyavskii's algorithm for univariate Lipschitz functions. The second algorithm, using a piecewise constant upper-bounding function, is designed for multivariate Hölder functions. A proof of convergence is provided for both algorithms. Computational experience is reported on several test functions from the literature.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
AtkinsonM.D., SackJ.-R., SantoroN., and StrotholteT. (1986), Min-max Heaps and Generalized Priority Queues,Communications of the ACM 29, 996–1000.
BassoP. (1982), Iterative Method for the Localization of the Global Maximum,SIAM Journal on Numerical Analysis 19, 781–792.
BraninF.H.Jr. (1972), Widely Convergent Method for Multiple Solution of Simultaneous Nonlinear Equations,IBM Journal of Research and Development 16, 504–522.
Fichtenholz, G.M. (1964),Differential- und Integralrechnung I, Berlin.
Gourdin, E., Hansen, P., and Jaumard, B. (1996) ‘Multivariate Lipschitz Optimization: a Survey’, submitted for publication.
GoldsteinA.A. and PriceJ.-F. (1971), On Descent from Local Minima,Mathematics of Computation 25, 569–574.
HansenP. and JaumardB. (1994). Lipschitz Optimization, inHandbook of Global Optimization (R.Horst and P.Pardalos, eds.), Kluwer, The Netherlands, pp. 407–494.
HansenP., JaumardB., and LuS.-H. (1991), On the Number of Iterations of Piyavskii's Global Optimization Algorithm,Mathematics of Operations Research 16, 334–350.
HanjoulP., HansenP., PeetersD., and ThisseJ.-F., (1990), Uncapacitated Plant Location under Alternative Space Price Policies,Management Science 36, 41–47.
HorstR. and TuyH. (1992),Global Optimization-Deterministic Approaches, 2nd Edition, Berlin: Springer.
Jaumard, B., Ribault, H., and Herrmann, T. (1995), An On-line Cone Intersection Algorithm for Global Optimization of Multivariate Lipschitz Functions, to appear inMathematical Programming.
Jaumard, G. and Gourdin, E. (1992), Techniques Informatiques pour la Recherche Opérationnelle: Partie I,Cahiers du Gerard, G-92-43, Montréal, Canada.
LevyA.V., MontalvoA., GomezS., and CalderonA. (1981), Topics in Global Optimization, inLecture Notes on Mathematics 909, Springer, Berlin.
LuenbergerD.G. (1984),Linear and Nonlinear Programming, 2nd Edition, Addison-Wesley, Reading, Massachusetts.
McCormickG.P. (1976), Computability of Global Solutions to Factorable Non-convex Programs: Part 1 — Convex Understanding Problems,Mathematical Programming 10, 147–175.
MladineoR.H. (1986), An Algorithm for Finding the Global Maximum of a Multimodal, Multivariate Function,Mathematical Programming 34, 188–200.
Mladineo, R.H. (1992), Stochastic Minimization of Lipschitz Functions, inRecent Advances in Global Optimization, C. Floudas and P. Pardalos, eds., Princeton University Press, pp. 369–383.
PhillipsD.T., RavindranA., and SolbergJ.J. (1976),Operations Research Principles and Practice, Wiley, New York.
PiyavskiiS.A. (1967), An Algorithm for Finding the Absolute Minimum of a Function,Theory of Optimal Solutions,2, Kiev, IK AN USSR (in Russian), pp. 13–24.
PiyavskiiS.A. (1972), An Algorithm for Finding the Absolute Extremum of a Function,USSR Computational Mathematics and Mathematical Physics 12, 57–67 (Zh. v1 12(4) (1972) 888–896).
SchittkowskiK. (1987),More Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems282, Springer Verlag, Berlin, Heidelberg, New York.
TimonovL.N. (1977), An Algorithm for Search of a Global Extremum,Engineering Cybernetics 15, 38–44.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Gourdin, E., Jaumard, B. & Ellaia, R. Global optimization of Hölder functions. J Glob Optim 8, 323–348 (1996). https://doi.org/10.1007/BF02403997
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF02403997