I am looking for an answer to the following question:

Is the objective function $\max \min(f(x))$ convex for all $f(x)$? Is it convex for a function like the following? $$f(x) = \sum_{i=1}^{\infty} x_i$$

I don't really know how to work on the max min (or min max) ... I know max / min are convex but does it help to understand the convexity of max min (min max) ?

Example: Let's say we would like to minimize the maximum energy use for a bunch of jobs over the time, and be sure that every jobs are finished on time (typical scheduling problem).

We are going to have a problem like that: $min~max(f(x))$, where $f(x) = E_t^J = \sum_{j=1}^{J}x_{j},\forall j \in J$ and $\forall~t \in T$. Where $J$ is the set of our jobs and $x_j$ the energy you deliver to each job working in a timeslot $t$ and $E_t^J$ the total energy consumes by the jobs working in timeslot $t$.

We would do the maximisation over $t$ and the minimization over $J$. How can we state if this is convex or not ?

  • 1
    $\begingroup$ I think I need some clarification. maximization over which variable and minimization over which variable for your question? $\endgroup$ Apr 21, 2017 at 5:14
  • $\begingroup$ Let's say $min~max\{E_{t}^J\}$, with a maximization over t and a minimization over J. $\endgroup$
    – Ecterion
    Apr 21, 2017 at 5:23
  • $\begingroup$ What do you mean by max/min are convex? E.g., the max of $n$ linear functions is a convex function, but the min is a concave function. $\endgroup$
    – mlc
    Apr 21, 2017 at 5:25
  • $\begingroup$ In fact I have to work on a function which is "minimize the maximum of Energy", corresponding to what I have wrote above. I would like to prove that this is convex to be able to use the dual decomposition on this function and divide it into subproblems. In fact it is a maximization problem of a minimization function. I have read some article about max-min convex function, but this kind of assumptions assume that their is also non-convex max-min function, and I have no clue to prove the convexity of this. Here it is min-max, so probably concave, but is it always the case ? $\endgroup$
    – Ecterion
    Apr 21, 2017 at 5:31
  • $\begingroup$ $\min f(x)$ is a constant, and so $\max \min f(x)$ doesn't make much sense. What are you minimizing over and what are you maximizing over ? $\endgroup$
    – dohmatob
    Apr 21, 2017 at 5:54

1 Answer 1


The max-min problem is a quasi-convex problem You can check "Convex Optimization" book of Boyd

I think it can be transformed to convex form by using the bisection algorithm


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .