Distributionally robust optimization with decision dependent ambiguity sets
- PDF / 478,605 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 79 Downloads / 244 Views
Distributionally robust optimization with decision dependent ambiguity sets Fengqiao Luo1 · Sanjay Mehrotra1 Received: 12 April 2019 / Accepted: 21 March 2020 © The Author(s) 2020
Abstract We study decision dependent distributionally robust optimization models, where the ambiguity sets of probability distributions can depend on the decision variables. These models arise in situations with endogenous uncertainty. The developed framework includes two-stage decision dependent distributionally robust stochastic programming as a special case. Decision dependent generalizations of five types of ambiguity sets are considered. These sets are based on bounds on moments, covariance matrix, Wasserstein metric, Phi-divergence and Kolmogorov–Smirnov test. For the finite support case, we use linear, conic or Lagrangian duality to give reformulations of these models with a finite number of constraints. Reformulations are also given for the continuous support case for moment, covariance, Wasserstein and Kolmogorov–Smirnov based models. These reformulations allow solutions of such problems using global optimization techniques within the framework of a cutting surface algorithm. The importance of decision dependence in the ambiguity set is demonstrated with the help of a numerical example modeling simultaneous determination of order quantity and selling price for a newsvendor problem. Keywords Distributionally robust optimization · Decision dependent ambiguity set · Conic duality
1 Introduction The uncertain characteristics of a system’s performance often depend on its design decisions. This type of uncertainty is called endogenous uncertainty. For example in
B
Fengqiao Luo [email protected] Sanjay Mehrotra [email protected]
1
Department of Industrial Engineering and Management Science, Northwestern University, Evanston, IL, USA
123
F. Luo, S. Mehrotra
a newsvendor model product demand function may depend on its selling price [1]. Additional examples of decision problems with endogeneous uncertainty from finance, resource management, process design, and network design are given in Sect. 2. The goal of this paper is to present decision dependent ambiguity frameworks to model problems involving endogenous uncertainty. The main contribution is in showing that the dualization of a certain inner problem continues to be applicable in this more general setting. This dualization has a unique advantage for the problems under consideration. It allows application of algorithms from nonlinear global optimization to solve the resulting reformulations. Specifically, we study the optimization problems in which the ambiguity set of distributions may depend on the decisions in the following modeling framework: min x∈X
f (x) + max E P [h(x, ξ )] . P∈P (x)
(D3 RO)
Here x is the vector of decision variables with the feasible set X ⊆ Rn , and ξ is the vector of uncertain model parameters, which is defined on a measurable space (Ξ , F); Ξ is the support in Rd , and F is a σ -algebra. We may allow ξ to also depend
Data Loading...