A partition-based global optimization algorithm (Q1959242): Difference between revisions

In this paper the problem of globally minimizing a Lipschitz continuous function \(f\) over a hyperractangle \(D\) is considered. In the literature, several approaches have been proposed in order to solve this problem; among them, a class of methods searches for the global minimum points by using sequences of partitions of the feasible domain. Following this line, the authors propose two partitioning strategies. After a description of a general scheme of partition-based algorithms (PBA) and some theoretical properties in Section 2, they introduce their strategies in Section 3. For the first one, they assume that the optimal function \(f^*\) is known and that \(f\) is continuously differentiable. The aim of the algorithm to be defined is therefore to determine a point \(\overline{x}\) with \(f(\overline{x})\) as close as possible to \(f^*.\) Via an overestimate of the local Lipschitz constant of the function \((f-f^*)^p\) and a suitable selection choice of the selection, they prove in Proposition 7 that their strategy is able to guarantee the convergence of every infinite sequences of trial points to global minimum points. For the second one, the partitioning-based on estimate algorithm, the global minimum value is supposed to be not known a priori. The strategy consists in shifting the difficulty of the problem from the estimate of the Lipschitz constant to the estimate of the objective function value of the global minimum. They try to exploit information on the objective function gathered during progress of the algorithm. In Section 4, some illustrative numerical results are presented.