Global interval methods for local nonsmooth optimization

Citation
C. Gorges et H. Ratschek, Global interval methods for local nonsmooth optimization, J GLOB OPT, 14(2), 1999, pp. 157-179
Citations number
53
Categorie Soggetti
Engineering Mathematics
Journal title
JOURNAL OF GLOBAL OPTIMIZATION
ISSN journal
09255001 → ACNP
Volume
14
Issue
2
Year of publication
1999
Pages
157 - 179
Database
ISI
SICI code
0925-5001(199903)14:2<157:GIMFLN>2.0.ZU;2-6
Abstract
An interval method for determining local solutions of nonsmooth unconstrain ed optimization problems is discussed. The objective function is assumed to be locally Lipschitz and to have appropriate interval inclusions. The meth od consists of two parts, a local search and a global continuation and term ination. The local search consists of a globally convergent descent algorit hm showing similarities to epsilon-bundle methods. While epsilon-bundle met hods use polytopes as inner approximations of the epsilon-subdifferentials, which are the main tools of almost all bundle concepts, our method uses ax es parallel boxes as outer approximations of the epsilon-subdifferentials. The boxes are determined almost automatically with inclusion techniques of interval arithmetic. The dimension of the boxes is equal to the dimension o f the problem and remains constant during the whole computation. The applic ation of boxes does not suffer from the necessity to invest methodical and computational efforts to adapt the polytopes to the latest state of the com putation as well as to simplify them when the number of vertices becomes to o large, as is the case with the polytopes. The second part of the method a pplies interval techniques of global optimization to the approximative loca l solution obtained from the search of the first part in order to determine guaranteed error bounds or to improve the solution if necessary. We presen t prototype algorithms for both parts of the method as well as a complete c onvergence theory for them and demonstrate how outer approximations can be obtained.