zbMATH — the first resource for mathematics

\(\varepsilon\)-intervals in nonsmooth optimization. (English) Zbl 0898.90122
Gritzmann, Peter (ed.) et al., Recent advances in optimization. Proceedings of the 8th French-German conference on Optimization. Trier, Germany, July 21–26, 1996. Berlin: Springer. Lect. Notes Econ. Math. Syst. 452, 75-89 (1997).
Summary: The paper establishes a method for solving unconstrained optimization problems for nonsmooth objective functions. This method is based on interval arithmetic and is an alternative to the class of \(\varepsilon\)-bundle methods, which are well-known approaches to nonsmooth optimization problems. Principally, interval methods and \(\varepsilon\)-bundle methods share about almost the same local properties such as convergence theory, convergence speed and several algorithmical properties.
In contrast to the \(\varepsilon\)-bundle methods, which use polytopes to approximate the \(\varepsilon\)-subdifferentials from the inside, our approach deals with \(n\)-dimensional intervals, shortly called boxes, as outer approximations for the \(\varepsilon\)-subdifferentials, where \(n\) is the number of variables. The boxes seem to be superior to the polytopes because they easily can be computed with simple techniques of interval arithmetic. The dimension of the boxes is equal to \(n\), that is, it remains always constant whereas, in \(\varepsilon\)-bundle algorithms, it is necessary to adapt the polytope to the latest state of the computation as well as to simplify it as soon as the number of its vertices increases considerably. Optionally, the combination of interval methods with global optimization techniques do not just allow to compute solutions which are \(\varepsilon\)-optimal in the sense of \(\varepsilon\)-bundle methods, they actually enable to compute local solutions together with an absolute error bound.
We present a prototype algorithm and glance at its theoretical background and convergence properties.
For the entire collection see [Zbl 0868.00068].
90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
65G30 Interval and finite arithmetic