13
$\begingroup$

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}

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Great, thanks for your answer! Indeed, I now get a finite optimum, there is no reason to believe this is wrong. $\endgroup$ – dourouc05 Oct 7 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.