2005 | OriginalPaper | Buchkapitel
An Exchange Algorithm for Minimizing Sum-Min Functions
verfasst von : Alexei V. Demyanov
Erschienen in: Optimization and Control with Applications
Verlag: Springer US
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The problem of minimizing maxmin-type functions or the sum of minimum-type functions appears to be increasingly interesting from both theoretical and practical considerations. Such functions are essentially nonsmooth and, in general, they can successfully be treated by existing tools of Nonsmooth Analysis. In some cases the problem of finding a minimizer of such a function can be reduced to solving some mixed combinatorial-continuous problem.
In the present paper the problem of minimizing the sum of minima of a finite number of functions is discussed. It is shown that this problem is equivalent to solving a finite (though may be quite large) number of simpler (and sometimes quite trivial) optimization problems. Necessary conditions for global a minimum and sufficient conditions for a local minimum are stated. An algorithm for finding a local minimizer (the so-called exchange algorithm) is proposed. It converges to a local minimizer in a finite number of steps. A more general algorithm (called
ε
-exchange algorithm) is described which allows one to escape from a local minimum point. Numerical examples demonstrate the algorithm.