Robust counterpart: why is dual reformulation not working?

Question

I am trying to solve robust optimisation problems, but I am getting nonsensical solutions most of the time… Here is a very simplified example:

\begin{alignat}{2}\max&\quad x+z&\\\text{s.t.}&\quad\alpha x + \beta z& \leq 2&, \quad\forall (\alpha, \beta) \in \mathcal{U}\\&\quad x, z&\,\,\geq 0&\end{alignat}

Here is my uncertainty set $\mathcal U$:

$$\gamma+\alpha\leq4,\quad \delta+\beta\leq4\gamma,\quad \gamma+\delta\leq2,\qquad \alpha,\beta,\gamma,\delta\geq0$$

Following A Practical Guide to Robust Optimization and The Price of Robustness, I reformulate the problem as such, sequentially:

$$\alpha x + \beta z \leq 2,\quad\forall (\alpha, \beta) \in \mathcal{U}$$ \begin{align}\max_{(\alpha, \beta) \in \mathcal{U}} \alpha x + \beta z &\leq 2\\\min_{(u, v, w) \in \mathcal{U}^*} 4u+2w &\leq 2\end{align}

Finally,

\begin{alignat}{2}\max&\quad x+z&\\\text{s.t.}&\quad4u+2w&\leq 2\\&\quad u&\leq z\\&\quad v&\leq x\\&\quad u+w-4v&\leq0\\&\quad v+w&\leq0\\&\quad u, v, w, x, z&\,\,\geq 0\end{alignat}

However, this reformulation is unbounded. Nevertheless, you can compute an upper bound to the original formulation: $\alpha=1$ and $\beta=2$ is in $\mathcal U$, and using only this point from the uncertainty set, the objective function is $2$:

\begin{alignat}{2}\max&\quad x+z&\\\text{s.t.}&\quad x + 2 z &\leq 2\\&\quad x, z&\,\,\geq 0\end{alignat}

Answer 1

I think there are two small mistakes in your formulation:

1. In the final formulation, the roles of $x$ and $z$ should be reversed.
2. Except for the first constraint and for the non-negativity of the variables, all signs should be reversed.

The mistake probably occured when using duality to rewrite the expression $\max\limits_{(\alpha, \beta, \gamma, \delta) \in \mathcal{U}} x\alpha + z\beta$.

The above expression is a linear program, and can be written as follows (nothing special going on yet): \begin{align}\max&\quad c^\top \zeta\\\text{s.t.}&\quad A\zeta \le b\\&\quad\zeta \ge 0\end{align} in which $\zeta = (\alpha, \beta, \gamma, \delta)^\top$, $c=(x,z,0,0)^\top$, \begin{equation} A = \begin{bmatrix}1 & 0 & 1 & 0\\ 0 & 1 & -4 & 1 \\ 0 & 0 & 1 & 1\\\end{bmatrix}, \end{equation} and $b = (4,0,2)^\top$. Verify for yourself that $\{\zeta : A\zeta \le b, \zeta \ge 0\}$ indeed describes the uncertainty set $\mathcal{U}$.

Now we use standard duality theory to write down the dual problem: \begin{align}\min&\quad b^\top \lambda\\\text{s.t.}&\quad A^\top \lambda \ge c\\&\quad\lambda \ge 0\end{align} with $\lambda = (u,v,w)^\top$.

By writing out the equations, we get \begin{alignat}{4}\min\quad&4u + 2w&\\\text{s.t.}\quad &u&\ge x\\\quad &v& \ge z\\\quad &u - 4v + w& \ge 0\\\quad &v + w& \ge 0\\\quad &u, v, w&\,\,\ge 0\end{alignat}

This should lead you to the correct answer.

The papers that you reference may use different standard forms for linear programs. The first one (Gorissen et al.), for example, uses $D\zeta + q \ge 0$ instead of $A \zeta \le b$ and $\zeta \ge 0$, like I did above. Transforming between these forms is not that difficult, and not even necessary. The main step is always the same: use duality to transform a $\max$ in a $\min$, and which standard form you use to derive the dual does not change the correctness of this approach.