Optimization Online


Decomposition Methods for Solving Two-Stage Distributionally Robust Optimization Problems

Chen Yannan (yannan.chen***at***polyu.edu.hk)
Sun Hailin (mathhlsun***at***163.com)
Xu Huifu (h.xu***at***soton.ac.uk)

Abstract: Decomposition methods have been well studied for solving two-stage and multi-stage stochastic programming problems, see [29, 32, 33]. 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 constraint for the first stage decision variables, rearranging the minimax problem through Lagrange decomposition and applying the well-known 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 $\phi$-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

Category 1: Robust Optimization

Category 2: Stochastic Programming


Download: [PDF]

Entry Submitted: 12/08/2018
Entry Accepted: 12/08/2018
Entry Last Modified: 12/11/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society