In a robust linear program $\min_{x \in X} c^T x, X = \{x|x\geq 0, a_i^Tx \leq b_i, \forall i = 1, 2, ..., m$, $a_i \in A_i\}$, I have the following uncertainty parameter set:
$$A_i = \{a_i \in R^n| \text{ } ||a_i - \bar{a}_i||_1 \leq e_i\}, $$ where $e_i$ is a positive constant.
We need to convert the Robust LP into a linear program.
I think we need to solve the following problem:
$$\max_{a_i} a_i^T x$$ $$s.t. ||a_i - \bar{a}_i||_1 \leq e_i, $$ where $x \geq 0$.
KKT condistions are:
$$x = \lambda \begin{bmatrix}\text{sign}(a_{i1} - \bar{a}_{i1})\\\text{sign}(a_{i2} - \bar{a}_{i2})\\ \vdots \\ \text{sign}(a_{in} - \bar{a}_{in})\\\end{bmatrix}$$ $$\lambda(||a_i - \bar{a}_i||_1 - e_i) = 0$$ $$\lambda \geq 0$$ $$||a_i - \bar{a}_i||_1 \leq e_i$$
But I do not know how to deal with such KKT.
The maximum of $a^Tx$ over $||a-\bar{a}||_1\leq \epsilon$, i.e., the maximum of $\bar{a}^Tx + z^Tx$ over $||z||_1\leq \epsilon$, is given by $\bar{a}^Tx + \epsilon ||x||_{\infty}$. This follows from dual norms, and is a standard case in robust optimization.
https://en.wikipedia.org/wiki/Dual_norm
Consequently, the robust counterpart is the polytope given by the constraints $\bar{a}_i^Tx + e_i ||x||_{\infty} \leq b_i$ (where the term $||x||_{\infty}$ can be represented using a standard linear epigraph model)