0
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ I think I need some clarification. maximization over which variable and minimization over which variable for your question? $\endgroup$ – Siong Thye Goh Apr 21 '17 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 '17 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 '17 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 '17 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 '17 at 5:54
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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