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?

1 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.

  • $\begingroup$ Thank you for answering the question. I investigate more detail properties of $f_k$ to ensure some good convergence results. $\endgroup$
    – Keith
    Commented Oct 17, 2022 at 3:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.