Generalized Farkas Lemma with Adjustable Variables and Two-Stage Robust Linear Programs
- PDF / 449,185 Bytes
- 32 Pages / 439.37 x 666.142 pts Page_size
- 8 Downloads / 232 Views
Generalized Farkas Lemma with Adjustable Variables and Two-Stage Robust Linear Programs Thai Doan Chuong1,2 · Vaithilingam Jeyakumar3 Received: 27 August 2019 / Accepted: 9 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
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 Mathematics Subject Classification 49K99 · 65K10 · 90C29 · 90C46
Communicated by Marcin Studniarski.
B
Vaithilingam Jeyakumar [email protected] Thai Doan Chuong [email protected]
1
Optimization and Applications Research Group, Ton Duc Thang University, Ho Chi Minh City, Viet Nam
2
Faculty of Mathematics and Statistics, Ton Duc Thang University, Ho Chi Minh City, Viet Nam
3
Department of Applied Mathematics, University of New South Wales, Sydney 2052, Australia
123
Journal of Optimization Theory and Applications
1 Introduction Duality theory of linear programming and optimality principles of many classes of nonlinear optimization problems are often grounded in Farkas’ lemma or its generalizations. In 1901, Farkas [1] initially established a dual characterization for a system of linear inequalities, which was then used to derive necessary optimality principles for nonlinear programming problems, and these principles, known as Kuhn–Tucker conditions, were published in the early 1950s by Kuhn and Tucker [2]. Importantly, Farkas’ lemma provides a numerically verifiable dual condition for non-negativity of a linear function over a system of linear inequalities as the dual condition can be verified by solving a linear program. We refer the interested reader to [3–8] for the generalizations of Farkas’ lemma and their applications to linear and nonlinear optimization problems. In this paper, by establishing a new generalization of Farkas’ lemma, we present strong duality theorems for affinely adjustable two-stage robust linear programs with a general uncertainty set. Affinely adjustable two-stage robust linear programs appea
Data Loading...
