×

A branch and bound algorithm for the global optimization of Hessian Lipschitz continuous functions. (English) Zbl 1296.90090

Summary: 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.

MSC:

90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

SNOBFIT
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] 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 · Zbl 0846.90087 · doi:10.1007/BF01099647
[2] 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 · Zbl 0759.93036 · doi:10.1002/rnc.4590010404
[3] Bishop, C.M.: Neural Networks for Pattern Recognition. Oxford University Press, Oxford. http://books.google.co.uk/books?id=-aAwQO_-rXwC (1996) · Zbl 0868.68096
[4] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge. http://www.stanford.edu/ boyd/cvxbook/ (2004) · Zbl 1058.90049
[5] 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 · Zbl 1129.62071 · doi:10.1137/050639983
[6] Cartan, H.: Differential calculus. Cours de mathématiques II, Hermann. http://books.google.co.uk/books?id=PIg_AQAAIAAJ (1971) · Zbl 0759.93036
[7] 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 · Zbl 1229.90192
[8] 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) · Zbl 0922.62098
[9] 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) · Zbl 0958.65071
[10] 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) · Zbl 0759.93036
[11] 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) · Zbl 0581.90073
[12] 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 · Zbl 0090.34505
[13] 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) · Zbl 1097.90071
[14] 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) · Zbl 0581.90073
[15] 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 · Zbl 1193.65098 · doi:10.1007/s12532-010-0011-7
[16] 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) · Zbl 1172.90492
[17] 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 · Zbl 0090.34505 · doi:10.1007/BF01386213
[18] 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 · Zbl 0581.90073 · doi:10.1007/BF00939825
[19] 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) · Zbl 0805.00009
[20] 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 · Zbl 1142.90500
[21] 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 · Zbl 1172.90492 · doi:10.1023/A:1012771025575
[22] 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 · Zbl 0796.49032 · doi:10.1007/BF00941892
[23] 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 · Zbl 1097.90071 · doi:10.1007/s10898-004-2120-1
[24] 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 · Zbl 1142.90500 · doi:10.1007/s10107-006-0706-8
[25] Neumaier A.: Complete search in continuous global optimization and constraint satisfaction. Acta Numerica 13, 271-369 (2004). doi:10.1017/S0962492904000194 · Zbl 1113.90124 · doi:10.1017/S0962492904000194
[26] O’Hagan A.: Curve fitting and optimal design for prediction. J. R. Stat. Soc. B 40(1), 1-42 (1978). doi:10.2307/2984861 · Zbl 0374.62070 · doi:10.2307/2984861
[27] 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) · Zbl 0991.00017
[28] 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) · Zbl 0836.90134
[29] 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) · Zbl 1177.68165
[30] 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 · Zbl 0943.65017 · doi:10.1023/A:1018975909870
[31] 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) · Zbl 1041.62068
[32] 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) · Zbl 1088.90002
[33] 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) · Zbl 1075.65021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.