Generalized Farkas Lemma with Adjustable Variables and Two-Stage Robust Linear Programs

In this paper, we establish strong duality between affinely adjustable two-stage robust linear programs and their dual semidefinite programs under a general uncertainty set, that covers most of the commonly used uncertainty sets of robust optimization. This is achieved by first deriving a new versio...

Full description

Saved in:
Bibliographic Details
Published in:Journal of optimization theory and applications 2020-11, Vol.187 (2), p.488-519
Main Authors: Chuong, Thai Doan, Jeyakumar, Vaithilingam
Format: Article
Language:English
Subjects:
Applications of Mathematics
Calculus of Variations and Optimal Control
Optimization
Duality theorem
Engineering
Linear functions
Linear programming
Mathematics
Mathematics and Statistics
Operations Research/Decision Theory
Optimization
Robustness
Theory of Computation
Uncertainty
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we establish strong duality between affinely adjustable two-stage robust linear programs and their dual semidefinite programs under a general uncertainty set, that covers most of the commonly used uncertainty sets of robust optimization. This is achieved by first deriving a new version of Farkas’ lemma for a parametric linear inequality system with affinely adjustable variables. Our strong duality theorem not only shows that the primal and dual program values are equal, but also allows one to find the value of a two-stage robust linear program by solving a semidefinite linear program. In the case of an ellipsoidal uncertainty set, it yields a corresponding strong duality result with a second-order cone program as its dual. To illustrate the efficacy of our results, we show how optimal storage cost of an adjustable two-stage lot-sizing problem under a ball uncertainty set can be found by solving its dual semidefinite program, using a commonly available software.
ISSN:0022-3239
1573-2878
DOI:10.1007/s10957-020-01753-3