P-algorithm based on a simplicial statistical model of multimodal functions. (English) Zbl 1206.90131

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


90C26 Nonconvex programming, global optimization
Full Text: DOI


[1] Bundfuss S, Dür M (2008) Algorithmic copositivity detection by simplicial partition. Linear Algebra Appl 428(7):1511–1523 · Zbl 1138.15007 · doi:10.1016/j.laa.2007.09.035
[2] 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 · Zbl 0985.90075 · doi:10.1023/A:1022677121193
[3] Calvin J, Žilinskas A (2000) On one-dimensional P-algorithm with convergence rate O(n(+delta)) for smooth functions. J Optim Theory Appl 106:297–307 · Zbl 0992.90053 · doi:10.1023/A:1004699313526
[4] Dür M, Stix V (2005) Probabilistic subproblem selection in branch-and-bound algorithms. J Comput Appl Math 182(1):67–80 · Zbl 1078.65050 · doi:10.1016/j.cam.2004.10.019
[5] Fishburn P (1964) Decision and value theory. Wiley, New York · Zbl 0149.16203
[6] 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 · Zbl 1230.65066 · doi:10.1145/1186785.1186792
[7] Gutmann H (2001) A radial basis function method for global optimization. J Glob Optim 19:201–227 · Zbl 0972.90055 · doi:10.1023/A:1011255519438
[8] Hansen P, Jaumard B (1995) Lipschitz optimization. In: Horst R, Pardalos PM (eds) Handbook of global optimization. Springer, Berlin, pp 404–493 · Zbl 0833.90105
[9] Holmström K (2008) An adaptive radial basis algorithm (ARBF) for expensive black-box global optimization. J Glob Optim 41:447–464 · Zbl 1152.90609 · doi:10.1007/s10898-007-9256-8
[10] Hooker J (1995) Testing heuristics: we have it all wrong. J Heuristics 1:33–45 · Zbl 0853.68155 · doi:10.1007/BF02430364
[11] Horst R (1997) On generalised bisection of n-simplices. Math Comput 66:691–698 · Zbl 0863.51018 · doi:10.1090/S0025-5718-97-00809-0
[12] Horst R, Tuy H (1996) Global optimization–deterministic approaches, 3rd edn. Springer, Berlin · Zbl 0867.90105
[13] Jones D (2001) A taxonomy of global optimization methods based on response surfaces. J Glob Optim 21:345–383 · Zbl 1172.90492 · doi:10.1023/A:1012771025575
[14] Kushner H (1962) A versatile stochastic model of a function of unknown and time-varying form. J Math Anal Appl 5:150–167 · Zbl 0111.33001 · doi:10.1016/0022-247X(62)90011-2
[15] Mockus J (1988) Bayesian approach to global optimization. Kluwer, Dordrecht · Zbl 0513.62084
[16] Mockus J, Eddy W, Reklaitis G (1996) Bayesian heuristic approach to discrete and global optimization. Kluwer, Dordrecht · Zbl 0864.65036
[17] 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
[18] Paulavičius R, Žilinskas J (2008) Improved Lipschitz bounds over multidimensional simplex. Math Model Anal 13(4):553–563 · Zbl 1182.90073 · doi:10.3846/1392-6292.2008.13.553-563
[19] 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 · Zbl 1189.90203 · doi:10.1007/s11590-009-0156-3
[20] Pinter J (1996) Global optimization in action: Continuous and Lipschitz optimization: algorithms, implementations and applications. Kluwer, Dordrecht
[21] Santler T, Wiliams B, Notz W (2003) The design and analysis of computer experiments. Springer, Berlin
[22] 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 · Zbl 1097.65068 · doi:10.1137/040621132
[23] Stein M (1999) Interpolation of spatial data: some theory of kriging. Springer, Berlin · Zbl 0924.62100
[24] Strongin R, Sergeyev Y (2000) Global optimization with non-convex constraints. Kluwer, Dordrecht · Zbl 0987.90068
[25] Törn A, Žilinskas A (1989) Global optimization. Lect Notes Comput Sci 350:1–252
[26] Zhigljavsky A, Žilinskas A (2008) Stochastic global optimization. Springer, Berlin · Zbl 1136.90003
[27] Žilinskas A (1985) Axiomatic characterization of a global optimization algorithm and investigation of its search strategies. Oper Res Lett 4:35–39 · Zbl 0568.90082 · doi:10.1016/0167-6377(85)90049-5
[28] Žilinskas A (1992) A review of statistical models for global optimization. J Glob Optim 2:145–153 · Zbl 0768.90071 · doi:10.1007/BF00122051
[29] Žilinskas J (2007) Reducing of search space of multidimensional scaling problems with data exposing symmetries. Inf Technol Control 36(4):377–382
[30] Žilinskas J (2008) Branch and bound with simplicial partitions for global optimization. Math Model Anal 13(1):145–159 · Zbl 1146.49029 · doi:10.3846/1392-6292.2008.13.145-159
[31] Žilinskas A, Žilinskas J (2002) Global optimization based on a statistical model and simplicial partitioning. Comput Math Appl 44(7):957–967 · Zbl 1047.90036 · doi:10.1016/S0898-1221(02)00206-7
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.