@article{522900f17f26498dacf2438589b8ae79,
title = "Distributionally robust optimization with principal component analysis∗ ",
abstract = "Distributionally robust optimization (DRO) is widely used because it offers a way to overcome the conservativeness of robust optimization without requiring the specificity of stochastic programming. On the computational side, many practical DRO instances can be equivalently (or approximately) formulated as semidefinite programming (SDP) problems via conic duality of the moment problem. However, despite being theoretically solvable in polynomial time, SDP problems in practice are computationally challenging and quickly become intractable with increasing problem sizes. We propose a new approximation method to solve DRO problems with moment-based ambiguity sets. Our approximation method relies on principal component analysis (PCA) for optimal lower dimensional representation of variability in random samples. We show that the PCA approximation yields a relaxation of the original problem and derive theoretical bounds on the gap between the original problem and its PCA approximation. Furthermore, an extensive numerical study shows the strength of the proposed approximation method in terms of solution quality and runtime. As examples, for distributionally robust conditional value-at-risk and risk-averse production-transportation problems the proposed PCA approximation using only 50% of the principal components yields near-optimal solutions (within 1%) with a one to two order of magnitude reduction in computation time.",
keywords = "Distributionally robust optimization, Principal component analysis, Semidefinite programming, Stochastic programming",
author = "Jianqiang Cheng and Chen, {Richard Li Yang} and Najm, {Habib N.} and Ali Pinar and Cosmin Safta and Watson, {Jean Paul}",
note = "Funding Information: This work was funded by the Laboratory Directed Research and Development (LDRD) program of the Sandia National Laboratories. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology and Engineering Solutions of Sandia, LLC., a wholly owned subsidiary of Honeywell International, Inc., for the U.S. Department of Energy{\textquoteright}s National Nuclear Security Administration under contract DE-NA-0003525. The authors would like to thank the two anonymous referees and the Associate Editor Andrzej Ruszczynski for their very useful comments and suggestions, which helped to improve our paper significantly. Funding Information: ∗Received by the editors May 18, 2016; accepted for publication (in revised form) March 21, 2018; published electronically June 14, 2018. http://www.siam.org/journals/siopt/28-2/M107951.html Funding: This work was funded by the Laboratory Directed Research and Development (LDRD) program of the Sandia National Laboratories. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology and Engineering Solutions of Sandia, LLC., a wholly owned subsidiary of Honeywell International, Inc., for the U.S. Department of Energy{\textquoteright}s National Nuclear Security Administration under contract DE-NA-0003525. †Department of Systems and Industrial Engineering, University of Arizona, Tucson, AZ 85721 (jqcheng@email.arizona.edu). ‡Sandia National Laboratories, Livermore, CA 94551 (rlchen@sandia.gov, hnnajm@sandia.gov, apinar@sandia.gov, csafta@sandia.gov). §Sandia National Laboratories, Albuquerque, NM 87185 (jwatson@sandia.gov). Publisher Copyright: {\textcopyright} 2018 Society for Industrial and Applied Mathematics.",
year = "2018",
doi = "10.1137/16M1075910",
language = "English (US)",
volume = "28",
pages = "1817--1841",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "2",
}