# Max-min convexity?

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 $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 ?

• I think I need some clarification. maximization over which variable and minimization over which variable for your question? – Siong Thye Goh Apr 21 '17 at 5:14
• Let's say $min~max\{E_{t}^J\}$, with a maximization over t and a minimization over J. – Ecterion Apr 21 '17 at 5:23
• 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. – mlc Apr 21 '17 at 5:25
• 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 ? – Ecterion Apr 21 '17 at 5:31
• $\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 ? – dohmatob Apr 21 '17 at 5:54