Global interval methods for local nonsmooth optimization

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.