Decomposition and discrete approximation methods for solving two-stage distributionally robust optimization problems
- PDF / 3,024,095 Bytes
- 34 Pages / 439.37 x 666.142 pts Page_size
- 55 Downloads / 213 Views
Decomposition and discrete approximation methods for solving two‑stage distributionally robust optimization problems Yannan Chen1 · Hailin Sun2 · Huifu Xu3 Received: 29 November 2019 / Accepted: 8 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Decomposition methods have been well studied for solving two-stage and multistage stochastic programming problems, see Rockafellar and Wets (Math. Oper. Res. 16:119–147, 1991), Ruszczyński and Shapiro (Stochastic Programming, Handbook in OR & MS, North-Holland Publishing Company, Amsterdam, 2003) and Ruszczyński (Math. Program. 79:333–353, 1997). In this paper, we propose an algorithmic framework based on the fundamental ideas of the methods for solving two-stage minimax distributionally robust optimization (DRO) problems where the underlying random variables take a finite number of distinct values. This is achieved by introducing nonanticipativity constraints for the first stage decision variables, rearranging the minimax problem through Lagrange decomposition and applying the wellknown primal-dual hybrid gradient (PDHG) method to the new minimax problem. The algorithmic framework does not depend on specific structure of the ambiguity set. To extend the algorithm to the case that the underlying random variables are continuously distributed, we propose a discretization scheme and quantify the error arising from the discretization in terms of the optimal value and the optimal solutions when the ambiguity set is constructed through generalized prior moment conditions, the Kantorovich ball and 𝜙-divergence centred at an empirical probability distribution. Some preliminary numerical tests show the proposed decomposition algorithm featured with parallel computing performs well. Keywords Distributionally robust optimization · Decomposition method · Moment conditions · Kantorovich ball · Discrete approximation · Parallel computing
1 Introduction We consider the following two-stage distributionally robust optimization problem: * Hailin Sun [email protected] Extended author information available on the last page of the article
13
Vol.:(0123456789)
Y. Chen et al.
min sup 𝔼P [f1 (x, 𝜉) + v(x, 𝜉)]
x∈ℝn P∈P
s.t. x ∈ X,
(1)
where f1 is a continuous function mapping from ℝn × ℝl to ℝ , x is a decision vector restricted to taking values from a convex and compact set X ⊂ ℝn , 𝜉 ∶ 𝛺 → ℝl is a random vector defined in the probability space (𝛺, F, ℙ) with support set 𝛯 , v(x, 𝜉) is the optimal value function of the second stage problem
min g(x, y, 𝜉)
s.t. h(x, y, 𝜉) ≤ 0, y
(2)
where g and h are continuous functions mapping from ℝn × ℝm × ℝl to ℝ and ℝs respectively, P is a set of probability measures supported by 𝛯 . In the case when P = {P∗ } , where P∗ = ℙ◦𝜉 −1 , (1) reduces to an ordinary two-stage stochastic programming problem. P∗ is known as push-forward probability measure induced by 𝜉 or alternatively the true probability distribution of 𝜉 . Our focus here is on the case that the true probability distribution is unknown, b
Data Loading...
