How do we call this optimization problem?

Question

Let $f_k\colon\Bbb R^n\to\Bbb R$, $k=1,\dots,K$, be differentiable (possibly nonconvex) functions and $X\subset\Bbb R^n$ be a convex set. Consider the following optimization problem:

$$ \min_{x\in X}\max_{k\in\{1,\dots,K\}} f_k(x). $$

This is minimax problem but the inner optimization is a maximization discrete set. Rather than a general minimax problem, I guess this may be easier to deal with. I am interested in the following things:

• Are there any papers which propose algorithms for such structured problem?
• Do the papers show non-asymptotic convergence analysis?

Answer 1

You can rewrite your problem as \begin{align*} \min y\\ \textrm{s.t. }y & \ge f_{k}(x)\quad k=1,\dots,K\\ x & \in X. \end{align*}

What algorithms are applicable (and whether they converge in finitely many steps) will depend on the specifics of the $f_k()$ functions.