Abstract
We present a branch and bound algorithm for the global optimization of a twice differentiable nonconvex objective function with a Lipschitz continuous Hessian over a compact, convex set. The algorithm is based on applying cubic regularisation techniques to the objective function within an overlapping branch and bound algorithm for convex constrained global optimization. Unlike other branch and bound algorithms, lower bounds are obtained via nonconvex underestimators of the function. For a numerical example, we apply the proposed branch and bound algorithm to radial basis function approximations.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Androulakis I.P., Maranas C.D., Floudas C.A.: αBB: a global optimization method for general constrained nonconvex problems. J. Glob. Optim. 7, 337–363 (1995). doi:10.1007/BF01099647
Balakrishnan V., Boyd S., Balemi S.: Branch and Bound algorithm for computing the minimum stability degree of parameter-dependent linear systems. Int. J. Robust Nonlinear Control 1(4), 295–317 (1991). doi:10.1002/rnc.4590010404
Bishop, C.M.: Neural Networks for Pattern Recognition. Oxford University Press, Oxford. http://books.google.co.uk/books?id=-aAwQO_-rXwC (1996)
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge. http://www.stanford.edu/~boyd/cvxbook/ (2004)
Busby D., Farmer C.L., Iske A.: Hierarchical nonlinear approximation for experimental design and statistical data fitting. SIAM J. Sci. Comput. 29(1), 49–69 (2007). doi:10.1137/050639983
Cartan, H.: Differential calculus. Cours de mathématiques II, Hermann. http://books.google.co.uk/books?id=PIg_AQAAIAAJ (1971)
Cartis, C., Gould, N.I.M., Toint, P.L.: Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results. Math. Program. (2009). doi:10.1007/s10107-009-0286-5
Chilès, J., Delfiner, P.: Geostatistics: Modeling Spatial Uncertainty. Wiley Series in Probability and Statistics. Wiley, New York. http://books.google.co.uk/books?id=adkSAQAAIAAJ (1999)
Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust region methods. MPS-SIAM Series on Optimization, SIAM. http://books.google.co.uk/books?id=5kNC4fqssYQC (2000)
Conway, J., Sloane, N.: Sphere Packings, Lattices, and Groups, Grundlehren der mathematischen Wissenschaften, vol 290. Springer, Berlin. http://www.springer.com/mathematics/algebra/book/978-0-387-98585-5 (1999)
Dixon, L.C.W., Szegő, G.P.: The global optimisation problem: an introduction. In: Dixon, L.C.W., Szegő, G.P. (eds.) Towards Global Optimisation, vol. 2, pp 1–15, North-Holland. http://books.google.co.uk/books?id=SUSrAAAAIAAJ (1978)
Farmer, C.L., Fowkes, J.M., Gould, N.I.M.: Optimal well placement. Presented at the 12th European Conference on the Mathematics of Oil Recovery, Oxford, 6–9 September 2010. http://www.earthdoc.org/detail.php?pubid=41313
Floudas, C., Pardalos, P.: Handbook of Test Problems in Local and Global Optimization. Nonconvex Optimization and its Applications. Kluwer, Dordrecht. http://books.google.co.uk/books?id=vndwQgAACAAJ (1999)
Forrester, A., Sóbester, A., Keane, A.: Engineering Design via Surrogate Modelling: A Practical Guide. Progress in Astronautics and Aeronautics. Wiley, New York. http://books.google.co.uk/books?id=AukeAQAAIAAJ (2008)
Gould N.I.M., Robinson D.P., Thorne H.S.: On solving trust-region and other regularised subproblems in optimization. Math. Program. Comput. 2(1), 21–57 (2010). doi:10.1007/s12532-010-0011-7
Griewank, A.: The modification of newton’s method for unconstrained optimization by bounding cubic terms. Tech. Rep. NA/12 (1981), Department of Applied Mathematics and Theoretical Physics, University of Cambridge (1981)
Halton J.H.: On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numerische Mathematik 2, 84–90 (1960). doi:10.1007/BF01386213
Horst R.: A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization. J. Optim. Theory Appl. 51(2), 271–291 (1986). doi:10.1007/BF00939825
Horst, R., Pardalos, P.M.: Handbook of Global Optimization, Nonconvex Optimization and its Applications, vol. 2. Springer, Berlin. http://www.springer.com/mathematics/book/978-0-7923-3120-9 (1995)
Huyer, W., Neumaier, A.: SNOBFIT—stable noisy optimization by branch and fit. ACM Trans. Math. Softw. 35(2):9:1–9:25 (2008). doi:10.1145/1377612.1377613
Jones D.R.: A taxonomy of global optimization methods based on response surfaces. J. Glob. Optim. 21(4), 345–383 (2001). doi:10.1023/A:1012771025575
Jones D.R., Perttunen C.D., Stuckman B.E.: Lipschitzian optimization without the Lipschitz constant. J. Optim. Theory Appl. 79(1), 157–181 (1993). doi:10.1007/BF00941892
Kreinovich V., Kearfott R.: Beyond convex? Global optimization is feasible only for convex objective functions: a theorem. J. Glob. Optim. 33, 617–624 (2005). doi:10.1007/s10898-004-2120-1
Nesterov Y., Polyak B.: Cubic regularization of Newton method and its global performance. Math. Program. 108(1), 177–205 (2006). doi:10.1007/s10107-006-0706-8
Neumaier A.: Complete search in continuous global optimization and constraint satisfaction. Acta Numerica 13, 271–369 (2004). doi:10.1017/S0962492904000194
O’Hagan A.: Curve fitting and optimal design for prediction. J. R. Stat. Soc. B 40(1), 1–42 (1978). doi:10.2307/2984861
Pardalos, P.M., Romeijn, H.E.: Handbook of Global Optimization Volume 2, Nonconvex Optimization and its Applications, vol. 62. Springer, Berlin. http://www.springer.com/mathematics/book/978-1-4020-0632-6 (2002)
Pardalos, P.M., Horst, R., Thoai, N.V.: Introduction To Global Optimization, Nonconvex Optimization and its Applications, vol. 3. Springer, Berlin. http://www.springer.com/mathematics/book/978-0-7923-3556-6 (1995)
Rasmussen, C.E., Williams, C.K.I.: Gaussian Processes for Machine Learning. Adaptive Computation and Machine Learning, MIT Press, Cambridge. http://www.gaussianprocess.org/gpml/chapters/RW.pdf (2006)
Rippa S.: An algorithm for selecting a good value for the parameter c in radial basis function interpolation. Adv. Comput. Math. 11(2), 193–210 (1999). doi:10.1023/A:1018975909870
Santner, T.J., Williams, B.J., Notz, W.: The Design and Analysis of Computer Experiments. Springer Series in Statistics. Springer, Berlin. http://www.springer.com/statistics/statistical+theory+and+methods/book/978-0-387-95420-2 (2003)
Spall, J.C.: Introduction to Stochastic Search and Optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York. http://books.google.co.uk/books?id=f66OIvvkKnAC (2003)
Wendland, H.: Scattered Data Approximation. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge. http://books.google.co.uk/books?id=qy4cbWUmSyYC (2005)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
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, 1791–1815 (2013). https://doi.org/10.1007/s10898-012-9937-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-012-9937-9