Quadratically adjustable robust linear optimization with inexact data via generalized S-lemma: Exact second-order cone program reformulations

Abstract

Adjustable robust optimization allows for some variables to depend upon the uncertain data after its realization. However, the uncertainty is often not revealed exactly. Incorporating inexactness of the revealed data in the construction of ellipsoidal uncertainty sets, we present an exact second-order cone program reformulation for robust linear optimization problems with inexact data and quadratically adjustable variables. This is achieved by establishing a generalization of the celebrated S-lemma for a separable quadratic inequality system with at most one non-homogeneous function. It allows us to reformulate the resulting separable quadratic constraints over an intersection of two ellipsoids in terms of second-order cone constraints. We illustrate our results via numerical experiments on adjustable robust lot-sizing problems with demand uncertainty, showing improvements over corresponding problems with affinely adjustable variables as well as with exactly revealed data.

Keywords

• Non-convex quadratic inequality systems
• Generalized S-lemma
• Second-order cone programs
• Exact conic reformulations
• Adjustable robust optimization
• Lot-sizing problems