A global minimization algorithm for Lipschitz functions

GAVIANO, MARCO;LERA, DANIELA

2008-01-01

---

Abstract

The global optimization problem min f(x), x in S with S=[a,b], a, b in Rn and f(x) satisfying the Lipschitz condition |f(x)-f(y)|≤l|x-y| (the maximum norm) for all x,y in S, l>0, is considered. To solve it, a region-search algorithm is introduced. This combines a local minimum algorithm with a procedure that decreases the measure of the region where the global minimum is located. Specifically, by making use of the Lipschitz condition, at each algorithm iteration a sequence of intervals {s_j} s_j a subset S is constructed, with the property that a global minimum is in s_j. A convergence property of the algorithm is given. Further, numerical experiments are carried out; these show that the algorithm is effective for problems of small dimension.