Abstract
This article develops a novel global optimization algorithm using potential Lipschitz constants and response surfaces (PLRS) for computationally expensive black box functions. With the usage of the metamodeling techniques, PLRS proposes a new approximate function \({\hat{F}}\) to describe the lower bounds of the real function \(f\) in a compact way, i.e., making the approximate function \({\hat{F}}\) closer to \(f\). By adjusting a parameter \({\hat{K}}\) (an estimate of the Lipschitz constant \(K\)), \({\hat{F}}\) could approximate \(f\) in a fine way to favor local exploitation in some interesting regions; \({\hat{F}}\) can also approximate \(f\) in a coarse way to favor global exploration over the entire domain. When doing optimization, PLRS cycles through a set of identified potential estimates of the Lipschitz constant to construct the approximate function from fine to coarse. Consequently, the optimization operates at both local and global levels. Comparative studies with several global optimization algorithms on 53 test functions and an engineering application indicate that the proposed algorithm is promising for expensive black box functions.
Similar content being viewed by others
References
Pintér, J.: Global Optimization in Action: Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications, vol. 6. Springer, Berlin (1996)
Strongin, R.G., Sergeyev, Y.D.: Global Optimization With Non-convex Constraints: Sequential and Parallel Algorithms, vol. 45. Springer, Berlin (2000)
Shubert, B.O.: A sequential method seeking the global maximum of a function. SIAM J. Numer. Anal. 9(3), 379–388 (1972)
Mladineo, R.H.: An algorithm for finding the global maximum of a multimodal, multivariate function. Math. Program. 34(2), 188–200 (1986)
Jones, D.R., Perttunen, C.D., Stuckman, B.E.: Lipschitzian optimization without the Lipschitz constant. J. Optim. Theory Appl. 79(1), 157–181 (1993)
Kvasov, D.E., Sergeyev, Y.D.: Multidimensional global optimization algorithm based on adaptive diagonal curves. Comput. Math. Math. Phys. 43(1), 40–56 (2003)
Sergeyev, Y.D., Kvasov, D.E.: Global search based on efficient diagonal partitions and a set of Lipschitz constants. SIAM J. Optim. 16(3), 910–937 (2006)
Kvasov, D.E., Sergeyev, Y.D.: A univariate global search working with a set of Lipschitz constants for the first derivative. Optim. Lett. 3(2), 303–318 (2009)
Strongin, R.: On the convergence of an algorithm for finding a global extremum. Eng. Cybern. 11, 549–555 (1973)
De Haan, L.: Estimation of the minimum of a function using order statistics. J. Am. Stat. Assoc. 76(374), 467–469 (1981)
Wood, G., Zhang, B.: Estimation of the Lipschitz constant of a function. J. Glob. optim. 8(1), 91–103 (1996)
Sergeyev, Y.D., Pugliese, P., Famularo, D.: Index information algorithm with local tuning for solving multidimensional global optimization problems with multiextremal constraints. Math. Program. 96(3), 489–512 (2003)
Piyavskii, S.: An algorithm for finding the absolute extremum of a function. USSR Comput. Math. Math. Phys. 12(4), 57–67 (1972)
Liu, H., Xu, S., Wang, X., Wu, J., Song, Y.: A global optimization algorithm for simulation-based problems via the extended DIRECT scheme. Eng. Optim. (2014). doi:10.1080/0305215X.2014.971777
Gablonsky, J.M., Kelley, C.T.: A locally-biased form of the DIRECT algorithm. J. Glob. Optim. 21(1), 27–37 (2001)
Watson, L.T., Baker, C.A.: A fully-distributed parallel global search algorithm. Eng. Comput. 18(1/2), 155–169 (2001)
Siah, E.S., Sasena, M., Volakis, J.L., Papalambros, P.Y., Wiese, R.W.: Fast parameter optimization of large-scale electromagnetic objects using DIRECT with Kriging metamodeling. Microw. Theory Tech. IEEE Trans. 52(1), 276–285 (2004)
Liuzzi, G., Lucidi, S., Piccialli, V.: A DIRECT-based approach exploiting local minimizations for the solution of large-scale global optimization problems. Comput. Optim. Appl. 45(2), 353–375 (2010)
Liu, Q., Cheng, W.: A modified direct algorithm with bilevel partition. J. Glob. Optim. 60(3), 483–499 (2014)
Paulavičius, R., Žilinskas, J.: Simplicial Lipschitz optimization without the Lipschitz constant. J. Glob. Optim. 59(1), 23–40 (2013)
Paulavičius, R., Sergeyev, Y.D., Kvasov, D.E., Žilinskas, J.: Globally-biased Disimpl algorithm for expensive global optimization. J. Glob. Optim. 59(2–3), 545–567 (2014)
Jones, D.R.: Direct global optimization algorithm. In: Floudas, C., Pardalos, P. (eds.) Encyclopedia of Optimization, pp. 431–440. Kluwer Academic Publishers, Dordrecht (2001)
Paulavičius, R., Žilinskas, J.: Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints. Optim. Lett., pp. 1–10 (2014)
Tavassoli, A., Haji Hajikolaei, K., Sadeqi, S., Wang, G.G., Kjeang, E.: Modification of DIRECT for high-dimensional design problems. Eng. Optim. 46(6), 810–823 (2014)
Huyer, W., Neumaier, A.: Global optimization by multilevel coordinate search. J. Glob. Optim. 14(4), 331–355 (1999)
Ljungberg, K., Holmgren, S., Carlborg, Ö.: Simultaneous search for multiple QTL using the global optimization algorithm DIRECT. Bioinformatics 20(12), 1887–1895 (2004)
Sergeyev, Y.D.: An information global optimization algorithm with local tuning. SIAM J. Optim. 5(4), 858–870 (1995)
Kvasov, D.E., Pizzuti, C., Sergeyev, Y.D.: Local tuning and partition strategies for diagonal GO methods. Numer. Math. 94(1), 93–106 (2003)
Sergeyev, Y.D.: Global one-dimensional optimization using smooth auxiliary functions. Math. Program. 81(1), 127–146 (1998)
Sergeyev, Y.D., Kvasov, D.E.: A deterministic global optimization using smooth diagonal auxiliary functions. Commun. Nonlinear Sci. Numer. Simul. 21(1), 99–111 (2015)
Cressie, N.: Spatial prediction and ordinary kriging. Math. Geol. 20(4), 405–421 (1988)
Fang, H., Horstemeyer, M.F.: Global response approximation with radial basis functions. Eng. Optim. 38(04), 407–424 (2006)
Jones, D.R., Schonlau, M., Welch, W.J.: Efficient global optimization of expensive black-box functions. J. Glob. Optim. 13(4), 455–492 (1998)
Gutmann, H.-M.: A radial basis function method for global optimization. J. Glob. Optim. 19(3), 201–227 (2001)
Regis, R.G., Shoemaker, C.A.: Constrained global optimization of expensive black box functions using radial basis functions. J. Glob. Optim. 31(1), 153–171 (2005)
Holmström, K.: An adaptive radial basis algorithm (ARBF) for expensive black-box global optimization. J. Glob. Optim. 41(3), 447–464 (2008)
Gu, J., Li, G., Dong, Z.: Hybrid and adaptive meta-model-based global optimization. Eng. Optim. 44(1), 87–104 (2012)
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)
Sergeyev, Y.D., Strongin, R.G., Lera, D.: Introduction to Global Optimization Exploiting Space-Filling Curves. Springer, New York (2013)
Meewella, C., Mayne, D.: An algorithm for global optimization of Lipschitz continuous functions. J. Optim. Theory Appl. 57(2), 307–322 (1988)
Johnson, M.E., Moore, L.M., Ylvisaker, D.: Minimax and maximin distance designs. J. Stat. Plan. Inference 26(2), 131–148 (1990)
Viana, F.A., Venter, G., Balabanov, V.: An algorithm for fast optimal Latin hypercube design of experiments. Int. J. Numer. Methods Eng. 82(2), 135–156 (2010)
Liu, H., Xu, S., Wang, X.: Sequential sampling designs based on space reduction. Eng. Optim., 1–18 (2014)
Gaviano, M., Kvasov, D.E., Lera, D., Sergeyev, Y.D.: Algorithm 829: software for generation of classes of test functions with known local and global minima for global optimization. ACM Trans. Math. Softw. (TOMS) 29(4), 469–480 (2003)
Wang, G.G., Shan, S.: Review of metamodeling techniques in support of engineering design optimization. J. Mech. Des. 129(4), 370–380 (2007)
Lautenschlager, U., Eschenauer, H.A., Mistree, F.: Multiobjective flywheel design: a doe-based concept exploration task. In: Dutta, D., (ed.) Advances in Design Automation, pp. 14–17 (1997)
Eby, D., Averill, R., Goodman, E., Punch, W.: The optimization of flywheels using an injection island genetic algorithm. Evol. Des. Comput., pp. 167–190 (1999)
Kress, G.: Shape optimization of a flywheel. Struct. Multidiscip. Optim. 19(1), 74–81 (2000)
Arslan, M.A.: Flywheel geometry design for improved energy storage using finite element analysis. Mater. Des. 29(2), 514–518 (2008)
Acknowledgments
The authors appreciate the financial support from National Natural Science Foundation of China (11402047, 51308090), National Program on Key Basic Research Project (2015CB057301) and Ph.D. Programs Foundation of Liaoning Province (20131019).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Liu, H., Xu, S., Ma, Y. et al. Global optimization of expensive black box functions using potential Lipschitz constants and response surfaces. J Glob Optim 63, 229–251 (2015). https://doi.org/10.1007/s10898-015-0283-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-015-0283-6