Generating moment matching scenarios using optimization techniques

Sanjay Mehrotra*, Dávid Papp

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

Abstract

An optimization based method is proposed to generate moment matching scenarios for numerical integration and its use in stochastic programming. The main advantage of the method is its flexibility: it can generate scenarios matching any prescribed set of moments of the underlying distribution rather than matching all moments up to a certain order, and the distribution can be defined over an arbitrary set. This allows for a reduction in the number of scenarios and allows the scenarios to be better tailored to the problem at hand. The method is based on a semi-infinite linear programming formulation of the problem that is shown to be solvable with polynomial iteration complexity. A practical column generation method is implemented. The column generation subproblems are polynomial optimization problems; however, they need not be solved to optimality. It is found that the columns in the column generation approach can be efficiently generated by random sampling. The number of scenarios generated matches a lower bound of Tchakaloff's. The rate of convergence of the approximation error is established for continuous integrands, and an improved bound is given for smooth integrands. Extensive numerical experiments are presented in which variants of the proposed method are compared to Monte Carlo and quasi-Monte Carlo methods on both numerical integration problems and stochastic optimization problems. The benefits of being able to match any prescribed set of moments, rather than all moments up to a certain order, is also demonstrated using optimization problems with 100-dimensional random vectors. Empirical results show that the proposed approach outperforms Monte Carlo and quasi-Monte Carlo based approaches on the tested problems.

Original languageEnglish (US)
Pages (from-to)963-999
Number of pages37
JournalSIAM Journal on Optimization
Volume23
Issue number2
DOIs
StatePublished - 2013

Keywords

  • Column generation
  • Convex programming
  • Cubature
  • Moment matching
  • Scenario generation
  • Semi-infinite programming
  • Statistical bounds

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'Generating moment matching scenarios using optimization techniques'. Together they form a unique fingerprint.

Cite this