When moving beyond simple uncertainty sets like boxes or ellipsoids, the robust counterpart of an uncertain optimization problem requires a more general framework. Consider an uncertain linear constraint $a(u)^Tx \leq b(u)$ that must hold for all $u \in \mathcal{U}$, where $\mathcal{U}$ is a convex uncertainty set. The robust counterpart is a semi-infinite constraint: $\sup_{u \in \mathcal{U}} \{a(u)^Tx - b(u)\} \leq 0$. The core challenge is reformulating this into a tractable, finite-dimensional problem.

For a general uncertain conic constraint of the form $A(u)x - b(u) \in \mathcal{K}$ for all $u \in \mathcal{U}$, where $\mathcal{K}$ is a proper cone, the robust counterpart becomes significantly more complex. We can leverage duality theory. The constraint holds if and only if the optimal value of the following problem is non-positive:

By swapping the max and min operators, assuming strong duality holds, we can derive a tractable counterpart. This often involves representing the uncertainty set $\mathcal{U}$ itself using conic constraints. If $\mathcal{U} = \{u \mid D u \preceq_{\mathcal{L}} d\}$ for some cone $\mathcal{L}$, the problem can be recast into a single, large conic program.

A powerful tool for deriving tractable robust counterparts, especially for quadratically constrained quadratic programs (QCQPs), is the S-procedure. It provides a condition for the non-negativity of one quadratic function over a set defined by other quadratic inequalities. Specifically, the implication $(x^TA_1x + 2b_1^Tx + c_1 \leq 0 \implies x^TA_0x + 2b_0^Tx + c_0 \geq 0)$ holds if there exists a non-negative scalar $\tau$ such that:

The S-procedure is a direct consequence of a more fundamental result: the conic Farkas' Lemma. For a cone $\mathcal{K}$, the lemma states that a system $Ax=b, x \in \mathcal{K}$ is infeasible if and only if there exists a vector $y$ such that $A^Ty \in \mathcal{K}^*$ and $b^Ty < 0$. This theorem of the alternative provides a certificate of infeasibility. It is the cornerstone for establishing strong duality in conic programming and, by extension, for deriving robust counterparts. It allows us to transform the requirement that a constraint holds for all uncertainties into a condition on a dual variable.

For the robust counterpart to be equivalent to a tractable dual problem, strong duality must hold. This is not guaranteed. A key concept is the robust characteristic cone. For an uncertain constraint system, this cone, denoted $\mathcal{H}$, consists of all directions $y$ in the dual space for which the supremum of $y^T(A(u)x - b(u))$ remains bounded from above as $x$ varies, for any fixed $u \in \mathcal{U}$.

Strong duality for the semi-infinite program holds if the robust characteristic cone satisfies certain regularity conditions. Essentially, the cone must be closed. This is where constraint qualifications come into play. A common condition is a robust version of Slater's condition. If there exists a point $x_0$ that is strictly feasible for every possible realization of the uncertainty, that is, $A(u)x_0 - b(u)$ is in the interior of the cone $\mathcal{K}$ for all $u \in \mathcal{U}$, then strong duality holds. This ensures there are no pathological geometries at the boundary of the feasible set that could cause a duality gap.

When these conditions are met, the semi-infinite program can be converted into a finite-dimensional, tractable convex program. The dual of the robust counterpart provides the optimal values for the dual variables, which can be interpreted as prices or sensitivities associated with the constraints under uncertainty. This dual formulation is often the key to solving large-scale robust optimization problems efficiently.