-

 

 

 




Optimization Online





 

Discrete Approximation Scheme in Distributionally Robust Optimization

Yongchao Liu (lyc***at***dlut.edu.cn)
Xiaoming Yuan (xmyuan***at***hku.hk)
Jin Zhang (zhangj9***at***sustc.edu.cn)

Abstract: Discrete approximation which is the prevailing scheme in stochastic programming in the past decade has been extended to distributionally robust optimization (DRO) recently. In this paper we conduct rigorous quantitative stability analysis of discrete approximation schemes for DRO, which measures the approximation error in terms of discretization sample size. For the ambiguity set defined through equality and inequality moment conditions, we quantify the discrepancy between the discretized ambiguity set and the original one with respect to Wasserstein metric. To establish the quantitative convergence, we develop a Hoffman error bound theory with Hoffman constant calculation criteria in infinite dimensional space, which can be regarded as a byproduct of independent interest. For the ambiguity set defined by Wasserstein ball, and moment conditions combined with Wasserstein ball, we present associated quantitative stability analysis by taking full advantage of the convexity inherently admitted by Wasserstein metric. Efficient numerical methods for specifically solving discrete approximation DRO problems with thousands of samples are also designed. In particular, we reformulate different types of discrete approximation problems into a class of saddle point problems with completely separable structures. The stochastic primal-dual hybrid gradient (PDHG) algorithm where in each iteration we update a random subset of the sampled variables is then amenable as a solution method. Some primary numerical tests are reported.

Keywords: Quantitative stability analysis, Hoffman Lemma, discrete approximation method, distributionally robust optimization, stochastic primal-dual hybrid gradient

Category 1: Robust Optimization

Citation:

Download: [PDF]

Entry Submitted: 01/20/2019
Entry Accepted: 01/20/2019
Entry Last Modified: 01/24/2019

Modify/Update this entry


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

 

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