Minmaxmin problems revisited
Anton V Demyanov, Vladimir F. Demyanov, Vasily N. Malozemov · Optimization methods & software · 2002
The following problem is discussed: Find a (constrained or unconstrained) minimizer of the function $$ F(x) = \max _{y\in G_1}\min _{z\in G_2} \varphi (x,y,z),$$ where } ( x,y,z ) is a function defined and continuous on $ R^n\times R^p\times R^q, G_1\subset R^p $ and $ G_2\subset R^q $ are compact sets in the respective spaces. The case where the function } is continuously differentiable was studied earlier. It is well known that the problem of minimizing the function F is nonconvex and multiextremal. It is shown in the article that the problem is reduced to solving a family of minimax problems. The discrete case (where G 1 and G 2 contain a finite number of points) is discussed in more detail. In such a case the problem is reduced to solving a finite number of minimax problems. A necessary condition for a point to be a global minimizer and a sufficient condition for a point to be a local one are proved. Numerical methods for finding stationary points (i.e. points satisfying the necessary condition) are proposed. These methods (as well as the necessary condition) are of nonlocal nature thus in some cases allowing one to escape from a local minimizer. Each stationary point is a local minimizer while the converse is not true.