Reduction and Minimality of Coexhausters

Аннотация

V.F. Demyanov introduced exhausters for the study of nonsmooth functions. These are families of convex compact sets that enable one to represent the main part of the increment of a considered function in a neighborhood of the studied point as MaxMin or MinMax of linear functions. Optimality conditions were described in terms of these objects. This provided a way for constructing new algorithms for solving nondifferentiable optimization problems. Exhausters are defined not uniquely. It is obvious that the smaller an exhauster, the less are the computational expenses when working with it. Thus, the problem of reduction of an available family arises. For the first time, this problem was considered by V.A. Roshchina. She proposed conditions for minimality and described some methods of reduction in the case when these conditions are not satisfied. However, it turned out that the exhauster mapping is not continuous in the Hausdorff metrics, which leads to the problems with convergence of numerical methods. To overcome this difficulty, Demyanov proposed the notion of coexhausters. These objects enable one to represent the main part of the increment of the considered function in a neighborhood of the studied point in the form of MaxMin or MinMax of affine functions. One can define a class of functions with the continuous coexhauster mapping. Optimality conditions can be stated in terms of these objects too. But coexhausters are also defined not uniquely. The problem of reduction of coexhausters is considered in this paper for the first time. Definitions of minimality proposed by Roshchina are used. In contrast to ideas proposed in the works of Roshchina, the minimality conditions and the technique of reduction developed in this paper have a clear and transparent geometric interpretation.