1

I am a beginner in optimization and I have the following questions: First question: is there a difference between the two optimization formulations?

OP1: $\max_{x} \min_{k} g_k=f(x)$ and OP2: $\max_{x} \min_{k} G=f(x,k)$

I think there is a big difference between the two problems and the solution methodologies. For OP2, one can first minimize of k, then second maximize over x. I do not think this approach works for OP1.

I am interested in solving OP1 (any methods but game theory), but I do not know where to start. Any advice?

Another question: under any conditions OP1 can be written as $\min_{k} \max_{x} g_k=f(x)$, or this is not possible?

Thanks in advance.

Noor
  • 145

1 Answers1

0

Another way to write $g_k(x)$ is $g(x,k)$ so your first two problem formulations look equivalent. For a fixed $x$, you are minimizing a function over $k$ and then for all of the minimums, you are taking the maximum over $x$. It is pretty rare to be able to swap the order of the minimization and maximization and still get the same answer. But under some conditions it is possible, for example if $g(x,k)$ is independent of either $x$ or $k$.

user2566092
  • 26,142
  • Thank you for your answer @user2566092 Let me reformulate OP1 and please let me know if you still think that both problems are equivalent. Consider OP1: $\max_x \min_k{f_{k=1}(x), f_{k=2}(x), ..., f_{k=K}(x)}$, do you think OP1 and OP2 are still equivalent? – Noor Aug 21 '14 at 17:04
  • I see you point now. I think you mean to introduce binary variables. – Noor Aug 21 '14 at 19:38