Technical Note—On Nested Partitions Method for Global Optimization.

GLOBAL optimization; OPERATIONS research; MATHEMATICAL optimization; MARKOV processes; ALGORITHMS; NUMERACY

Finite-Time Behavior of Nested Partitions Method for Global Optimization In "Nested Partitions Method for Global Optimization," Shi and Ólafsson propose the nested partitions (NP) method for global optimization. The NP method takes a global perspective and provides a setting for an efficient combination of global and local search. The motivation behind this method is that some parts of the feasible region may be most likely to contain the global optimal solution. Hence, this method considers them promising regions and concentrates the computational effort in these promising ones. Two of their main results are the properties of the global convergence of the NP method stated in theorems 3 and 4, respectively. In particular, theorem 3 provides a hitting-probability-based formula to represent the bound of the expected number of convergence iterations, and theorem 4 evaluates its expected numeric bound of convergence iterations under a particular case. We prove that both theorems are fundamentally incorrect and rectify them in this study. Shi and Ólafsson [(2000) Nested Partitions Method for Global Optimization. Operations Research. 48(3):390–407] proposed the Nested Partitions (NP) method with two different NP backtracking rules—namely, NP I and NP II—for solving global optimization problems. Two of their main results are the properties of the global convergence of the NP method stated in theorems 3 and 4 on pages 398 and 399, respectively. In particular, theorem 3 provides a hitting-probability-based formula to represent the bound of the expected number of convergence iterations for both NP I and II, and theorem 4 evaluates its expected numeric bound of convergence iterations under a particular case for NP II. We prove that both theorems are fundamentally incorrect and rectify them in this study. Our computational results show that the expected convergence bounds presented by Shi and Ólafsson can be deviated from the actual convergence bounds of NP II approximately by 50% for some tested scenarios. [ABSTRACT FROM AUTHOR]

Copyright of Operations Research is the property of INFORMS: Institute for Operations Research and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)