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

$\endgroup$
6
  • 1
    $\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, 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

Reset to default
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$

You must log in to answer this question.

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