This one was a bit more tricky :) First let's consider the optimization problems in the constraints

(L P _ {C _ {i}}) \quad \begin{array}{l l} \underset {v _ {i} \in I R ^ {m}} {\text {m i n i m i z e}} & y ^ {T} v _ {i} \\ \text {s u b j e c t t o} & C _ {i} ^ {T} v _ {i} \geq d _ {i}, \end{array}

where $y$ is fixed. If we form the dual of $(LP_{C_i})$ we obtain

\begin{array}{l l} \text {m a x i m i z e} & d _ {i} ^ {T} z _ {i} \\ (D P _ {C _ {i}}) \quad \text {s u b j e c t t o} & y - C _ {i} z _ {i} = 0, \\ & z _ {i} \geq 0, \end{array}

where $z_{i}$ is the dual variables.

For any $z_{i}$ that satisfies the constraints in $(DP_{C_i})$ , we know that

d _ {i} ^ {T} z _ {i} \leq O p t v a l (L P _ {C _ {i}}).

This follows directly by weak duality.

We can then use this in the constraint $\min_{v_i\in \mathcal{P}_i}\{v_i^T y\} \geq c_i$ as

d _ {i} ^ {T} z _ {i} \geq c _ {i} y - C _ {i} z _ {i} = 0, z _ {i} \geq 0.

Note that the constraints above could potentially be more restrictive than the original constraints, since $d_i^T z_i \leq \text{Optval}(LP_{C_i})$ .

But, fortunately we have strong duality! Meaning that there exists a $z_{i}$ satisfying the constraints in $(DP_{C_i})$ such that $d_{i}^{T}z_{i} = \text{Optval}(LP_{C_{i}})$ . Therefore, the constraints

d _ {i} ^ {T} z _ {i} \geq c _ {i} y - C _ {i} z _ {i} = 0, z _ {i} \geq 0.

exactly represents the constraint $\min_{v_i\in \mathcal{P}_i}\{v_i^T y\} \geq c_i$

A linear programming equivalent formulation of $(RP)$ is, thus, given by

\begin{array}{l l} \text {m a x i m i z e} & b ^ {T} y \\ (L R P) & \text {s u b j e c t t o} \quad d _ {i} ^ {T} z _ {i} \geq c _ {i} \quad i = 1, \dots , n, \\ & y - C _ {i} z _ {i} = 0 \quad i = 1, \dots , n, \\ & z _ {i} \geq 0 \quad i = 1, \dots , n. \end{array}

Note that $y, z_1, \ldots, z_n$ are all variables.