# Is the objective function $\max \min(f(x))$ convex for all $f(x)$?

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 ?

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