Strong Duality in Robust Convex Programming: Complete Characterizations

TLDR

Duality theory has been central to convex programming when data uncertainty is absent. The paper develops a duality theory for convex programming under data uncertainty using robust optimization. The authors introduce a robust characteristic cone constraint qualification, necessary and sufficient for strong duality, and derive it via a robust theorem of the alternative for parameterized convex inequality systems using conjugate analysis. They characterize strong duality between the robust counterpart and its optimistic Lagrangian dual, show it always holds for uncertain polyhedral convex programs, and provide a necessary and sufficient constraint qualification, supported by numerical examples.

Abstract

Duality theory has played a key role in convex programming in the absence of data uncertainty. In this paper, we present a duality theory for convex programming problems in the face of data uncertainty via robust optimization. We characterize strong duality between the robust counterpart of an uncertain convex program and the optimistic counterpart of its uncertain Lagrangian dual. We provide a new robust characteristic cone constraint qualification which is necessary and sufficient for strong duality in the sense that the constraint qualification holds if and only if strong duality holds for every convex objective function of the program. We further show that this strong duality always holds for uncertain polyhedral convex programming problems by verifying our constraint qualification, where the uncertainty set is a polytope. We derive these results by way of first establishing a robust theorem of the alternative for parameterized convex inequality systems using conjugate analysis. We also give a convex characteristic cone constraint qualification that is necessary and sufficient for strong duality between the deterministic dual pair: the robust counterpart and its Lagrangian dual. Through simple numerical examples we also provide an insightful account of the development of our duality theory.