Defeinition of robust counterpart in robust optimization

Question

I'm working on robust optimization problems and trying to summarize a bit about some basic ideas.

However, one really confusing thing is the definition of a robust counterpart.

Definition 1.2.5 from Ben-tal's book, says \begin{equation} \min _{x}\left\{\widehat{c}(x)=\sup _{(c, d, A, b) \in \mathcal{U}}\left[c^{T} x+d\right]: A x \leq b \forall(c, d, A, b) \in \mathcal{U}\right\} \end{equation} is the robust counterpart of the uncertain linear optimization \begin{equation} \left\{\min _{x}\left\{c^{T} x+d: A x \leq b\right\}\right\}_{(c, d, A, b) \in \mathcal{U}}. \end{equation}

This sounds like a robust counterpart is the corresponding optimization problem finding the worst-case optimal solution.

However, in his paper "Robust Solutions of Uncertain Linear Programs", the robust counterpart is defined as reformulating a deterministic nominal optimization problem to an optimization problem taking uncertainty set into account.

Can someone explain a bit how to define robust counterpart?

And also an example is given that \begin{equation} \min x_{1}+x_{2} \text { s.t. }\left\{\begin{array}{rr} \frac{1}{2} x_{1}+x_{2} \geq 1 \\ x_{1}+\frac{1}{2} x_{2} \geq 1 \\ x_{1}+x_{2}=1 \\ x_{1}, \quad x_{2} \geq 0 \end{array}\right. \end{equation}

is a robust counterpart for \begin{equation} \min x_{1}+x_{2} \text { s.t. }\left\{\begin{array}{rr} a_{11} x_{1}+x_{2} \geq 1 \\ x_{1}+a_{22} x_{2} \geq 1 \\ x_{1}+\quad x_{2}=1 \\ x_{1}, \quad x_{2} \geq 0 \end{array}\right. \end{equation} with $\mathcal{U}=\left\{a_{11}+a_{22}=2, \frac{1}{2} \leq a_{11} \leq \frac{3}{2}\right\}$. I'm not able to understand why optimization with the selection of $a_{11}$ and $a_{22}$ as $\frac{1}{2}$ is a robust counterpart. This selection doesn't even satisfy the uncertainty constraint set $\mathcal{U}$.

Any hint would be appreciated and many thanks!

Answer 1

The robust counterpart is a model which solves the uncertain worst-case problem without having uncertain variables.

In your example, the worst thing that can happen to the first constraint (once you have selected $x$) is that $a_{11}$ is small so that the constraint becomes violated. We know that $a_{11} \geq 1/2$, hence the solution must satisfy $(1/2) x_1 + x_2 \geq 1$ to cover for that worst case. For the second constraint, the worst thing that can happen is that $a_{22}$ becomes small, and by the same reasoning that worst possible $a_{22}$ that ever can happen is $a_{22} = 1/2$.

The two worst-case scenarios do not happen at the same time, every single constraint is analyzed independently. Just compare with surviving a trip to the desert, you want to survive the worst-case scenarios of being extremely warm during the day and thus bring your cooler, but you also want to survive during the possibly freezing night so you bring your heater. Those two scenarios do not happen at the same time, but your solution to survive both of them requires you to have a solution which handles two different worst-case scenarios.