Data-driven Distributionally Robust Polynomial Optimization
We consider robust optimization for polynomial optimization problems where the uncertainty set is a set of candidate probability density functions. This set is a ball around a density function estimated from data samples, i.e., it is data-driven and random. Polynomial optimization problems are inherently hard due to nonconvex objectives and constraints. However, we show that by employing polynomial and histogram density estimates, we can introduce robustness with respect to distributional uncertainty sets without making the problem harder. We show that the optimum to the distributionally robust problem is the limit of a sequence of tractable semidefinite programming relaxations. We also give finite-sample consistency guarantees for the data-driven uncertainty sets. Finally, we apply our model and solution method in a water network optimization problem.
The authors considered robust optimization for 
      polynomial optimization problems where the uncertainty set is a set of 
      possible distributions of the parameter. In specific, this set is a ball 
      around a density function estimated from data samples. The authors showed 
      that this distributionally robust optimization formulation can be reduced 
      to a polynomial optimization problem, hence computationally the robust 
      counterpart is of the same hardness as the nominal (non-robust) problem, 
      and can be solved using a tower of SDP known in literature. The authors 
      also provide finite-sample guarantees for estimating the uncertaity set 
      from data. Finally, they applied their methods to a water network problem. 
      This seems to be an interesting paper. Distributionally robust 
      optimization is now topical in operations research. Most previous 
      literature is restricted to the case that the distribution is 
      characterized by (first and second) moments, which has the apparent 
      disadvantage that consistency is impossible regardless of the number of 
      samples obtained. In contrast, the proposed approach overcomes this 
      difficulty, as when more samples are obtained, we can shrink the 
      uncertainty set until it becomes a singleton, and hence achieving 
      consistency. It is also nice to see that, at least for the polynomial 
      optimization problems, the resulting robust counterpart does not incur 
      additional computational difficulty. Some minor points: 1. 
      Assumption 4.1 is a bit confusing. In particular, I am not sure how the 
      sentence "and there exist u\in R[x]... compact." is related to the set X 
      and S. 2. In line 194, "\hat{S} satisfies Assumption 4.1". Why? 3. 
      L236, "We consider the multi-dimensional case in the next section" appears 
      to be wrong. 4. L375 "Table 6". There is no table 6 in the submission. 
      5. L379 "Un-biased". I am not sure why the uncertainty set are 
      unbiased (in fact I am even sure what does it mean that a set is 
      unbiased). 6. L148, "A notion of distributional uncertainty set has 
      also been studied in the setting of Markov decision problems [14]". I 
      think [14] does not consider distributional uncertainty. To my knowledge, 
      distributional uncertainty in MDP is investigated in Xu and Mannor (2012). 
      Ref: H. Xu, S. Mannor, "Distributionally Robust Markov 
      Decision Processes", Mathematics of Operations Research, 37(2), pp288-300, 
      2012.