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

Thai Doan Chuong () and Vaithilingam Jeyakumar ()
Additional contact information
Thai Doan Chuong: Ton Duc Thang University
Vaithilingam Jeyakumar: University of New South Wales

Journal of Optimization Theory and Applications, 2020, vol. 187, issue 2, No 11, 488-519

Abstract: Abstract 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.

Keywords: Generalized Farkas’ lemma; Semi-infinite linear system; Adjustable robust linear programming; Strong duality; Conic programming; 49K99; 65K10; 90C29; 90C46 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-020-01753-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:187:y:2020:i:2:d:10.1007_s10957-020-01753-3

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-020-01753-3

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().