# Robust counterpart: why is dual reformulation not working?

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}

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}

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.