I am trying to solve this robust LP problem by writing it as a QP
$$\min_x x^TSx : \mu \leq r^T x , Ax \leq b$$
Under Box uncertainty model: $$R = \{r : \| r - \hat{r}\|_\infty \leq \rho\}$$
Here is the solution outlined by the instructor
First we note that
$$\mu \leq x^T r \:\:\text{ for every } r \in R$$ Can be written as $$\mu \leq \min_{r \in R} r^T x$$
The above makes sense
The rest of this lost me
$$\min_{x \in R} r^T x = \hat{r}^T x + \rho . \:\:\:\: \min_{u : \|u\|_\infty \leq 1}u^Tx = \hat{r}^T x - \rho \|x\|_1$$
$$\min_x x^T S x : \mu + \rho \|x\|_1 \leq \hat{r}^Tx, Ax \leq b$$
can be expressed as a QP $$\min_x x^T S x : \mu + \rho y^T \textbf{1} \leq \hat{r}^T , Ax \leq b , -y \leq x \leq y$$
Specifically, I don't understand how
$$\min_{x \in R} r^T x = \hat{r}^T x + \rho . \:\:\:\: \min_{u : \|u\|_\infty \leq 1}u^Tx = \hat{r}^T x - \rho \|x\|_1$$
is true with the given condition
I thought
$$\min_{x \in R} r^T x =\hat{r}^T x - |\rho x| $$
As
$$R = \{r : \| r - \hat{r}\|_\infty \leq \rho\}$$
$$ \hat{r_i} - \rho \leq r_i \leq \hat{r}_i + \rho$$
so if $x_i < 0 \Rightarrow r = \hat{r}_i + \rho$ and vice versa resulting in
$$\min_{x \in R} r^T x = \hat{r}^T x - |\rho x| $$
Note that the minimization is with respect to $r$. Lets do a change of variables. If we set $u = \frac{r - \hat{r}}{\rho}$, we get:
$$\min_{r \in R} r^T x = \min_{u : \|u\|_\infty \leq 1} \rho u^Tx + \hat{r}^Tx.$$
Further,
$$\min_{u : \|u\|_\infty \leq 1} \rho u^Tx + \hat{r}^Tx = -\max_{u : \|u\|_\infty \leq 1} \rho u^Tx + \hat{r}^Tx.$$
Then, you can use an identity known as Holder's inequality to the first term:
$$\max_{u : \|u\|_\infty \leq 1} \rho u^Tx = \rho\|x\|_1.$$
Thus,
$$\min_{r \in R} r^T x = -\rho\|x\|_1 + \hat{r}^Tx.$$
Substituting the above in our original program gives the desired program that you have further simplified using another set of variables $y$.