I have a worst-case optimization problem, where i want to maximize the minimum from the uncertainty set (uncertainty is given as an ensemble of 100 realizations, so an ensemble based approach). It is a typical max-min problem.
What i am trying to understand is: for different inputs, i have a different worst-case realization (the member in uncertainty ensemble that gives worst objective function value). Which leads to a many possibilities of max-min depending upon the input. So is there no unique input that ensures me to give the 'real' worst-case (the worst of worst)?
I will highly appreciate if you help to try to understand this problem with the worst-case optimization (any good basic/tutorial reference is also welcome). Many thanks in advance.
P.S: It's a non convex optimization problem.
Let me quickly explain what is usually done in worst case optimization. As you say there is an "uncertainty set", typically represented by a random variable with realization $\omega$ drawn from set $\Omega$. $\Omega$ includes all values in the support of the random variable.
In the worst case optimization, say we talk about maximization of the worst case of a function $f: X\times\Omega\to \mathbb{R}$. The problem can then be written as $$\max_{x\in X} \min_{\omega\in\Omega} f(x,\omega).$$
Now you say you get different worst case realization. I am guessing that is because you draw randomly 100 realizations $\omega_1,\omega_2,...$ of the random variable and determine the worst case among these? Then you would be solving the problem $$\max_{x\in X} \min_{\omega\in\Omega'} f(x,\omega),$$ where $\Omega'\subseteq\Omega$ depends on the realization of your 100 draws. Depending on $\Omega'$, the max-min you get will change, because you are omitting other possible realizations in the set $\Omega$.
If you cannot tackle the max-min problem analytically, then you can try to find the solution numerically. You want the policy that guarantees the best worst case outcome. So you have to search through all $x\in X$ (e.g., numerically or with a grid), find the worst $\omega\in\Omega$ for each policy, compute the corresponding function value at the worst $\omega$, and in the end select the policy that guarantees the highest of these function values. That is,
1) For all $x\in X$ [discretize or use numerical maximizer], find $\min_{\omega\in\Omega} f(x,\omega)$. Define $\omega^*(x)=\arg\min_{\omega\in\Omega} f(x,\omega)$.
2) Find $\max_{x\in X} f(x,\omega^*(x))$. This is the policy you want.
On step 1: $\omega^*(x)$ could be a vector of the same length as your $x$ parameter grid, that assigns to each of the $x$ in your grid the $\omega\in\Omega$ which minimizes the function value $f(x,\omega)$. Or you just use some min-function in your programming language along with the numerical maximizer.