Abstract
A well-recognized one-dimensional global optimization method is generalized to the multidimensional case. The generalization is based on a multidimensional statistical model of multimodal functions constructed by generalizing computationally favorable properties of a popular one-dimensional model—the Wiener process. A simplicial partition of a feasible region is essential for the construction of the model. The basic idea of the proposed method is to search where improvements of the objective function are most probable; a probability of improvement is evaluated with respect to the statistical model. Some results of computational experiments are presented.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bundfuss S, Dür M (2008) Algorithmic copositivity detection by simplicial partition. Linear Algebra Appl 428(7):1511–1523
Calvin J, Žilinskas A (1999) On the convergence of the P-algorithm for one-dimensional global optimization of smooth functions. J Optim Theory Appl 102:479–495
Calvin J, Žilinskas A (2000) On one-dimensional P-algorithm with convergence rate O(n(−3+delta)) for smooth functions. J Optim Theory Appl 106:297–307
Dür M, Stix V (2005) Probabilistic subproblem selection in branch-and-bound algorithms. J Comput Appl Math 182(1):67–80
Fishburn P (1964) Decision and value theory. Wiley, New York
Gonçalves E, Palhares R, Takahashi R, Mesquita R (2006) Algorithm 860: SimpleS—an extension of Freudenthal’s simplex subdivision. ACM Trans Math Softw 32:609–621
Gutmann H (2001) A radial basis function method for global optimization. J Glob Optim 19:201–227
Hansen P, Jaumard B (1995) Lipschitz optimization. In: Horst R, Pardalos PM (eds) Handbook of global optimization. Springer, Berlin, pp 404–493
Holmström K (2008) An adaptive radial basis algorithm (ARBF) for expensive black-box global optimization. J Glob Optim 41:447–464
Hooker J (1995) Testing heuristics: we have it all wrong. J Heuristics 1:33–45
Horst R (1997) On generalised bisection of n-simplices. Math Comput 66:691–698
Horst R, Tuy H (1996) Global optimization—deterministic approaches, 3rd edn. Springer, Berlin
Jones D (2001) A taxonomy of global optimization methods based on response surfaces. J Glob Optim 21:345–383
Kushner H (1962) A versatile stochastic model of a function of unknown and time-varying form. J Math Anal Appl 5:150–167
Mockus J (1988) Bayesian approach to global optimization. Kluwer, Dordrecht
Mockus J, Eddy W, Reklaitis G (1996) Bayesian heuristic approach to discrete and global optimization. Kluwer, Dordrecht
Paulavičius R, Žilinskas J (2007) Analysis of different norms and corresponding Lipschitz constants for global optimization in multidimensional case. Inf Technol Control 36(4):383–387
Paulavičius R, Žilinskas J (2008) Improved Lipschitz bounds over multidimensional simplex. Math Model Anal 13(4):553–563
Paulavičius R, Žilinskas J, Grothey A (2010) Investigation of selection strategies in branch and bound algorithm with simplicial partitions and combination of Lipschitz bounds. Optim Lett 4(2):173–183
Pinter J (1996) Global optimization in action: Continuous and Lipschitz optimization: algorithms, implementations and applications. Kluwer, Dordrecht
Santler T, Wiliams B, Notz W (2003) The design and analysis of computer experiments. Springer, Berlin
Sergeyev Y, Kvasov D (2006) Global search based on efficient diagonal partitions and a set of Lipschitz constants. SIAM J Optim 16(3):910–937
Stein M (1999) Interpolation of spatial data: some theory of kriging. Springer, Berlin
Strongin R, Sergeyev Y (2000) Global optimization with non-convex constraints. Kluwer, Dordrecht
Törn A, Žilinskas A (1989) Global optimization. Lect Notes Comput Sci 350:1–252
Zhigljavsky A, Žilinskas A (2008) Stochastic global optimization. Springer, Berlin
Žilinskas A (1985) Axiomatic characterization of a global optimization algorithm and investigation of its search strategies. Oper Res Lett 4:35–39
Žilinskas A (1992) A review of statistical models for global optimization. J Glob Optim 2:145–153
Žilinskas J (2007) Reducing of search space of multidimensional scaling problems with data exposing symmetries. Inf Technol Control 36(4):377–382
Žilinskas J (2008) Branch and bound with simplicial partitions for global optimization. Math Model Anal 13(1):145–159
Žilinskas A, Žilinskas J (2002) Global optimization based on a statistical model and simplicial partitioning. Comput Math Appl 44(7):957–967
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Žilinskas, A., Žilinskas, J. P-algorithm based on a simplicial statistical model of multimodal functions. TOP 18, 396–412 (2010). https://doi.org/10.1007/s11750-010-0153-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-010-0153-9