TY - JOUR
T1 - Distributionally robust optimization with principal component analysis∗
AU - Cheng, Jianqiang
AU - Chen, Richard Li Yang
AU - Najm, Habib N.
AU - Pinar, Ali
AU - Safta, Cosmin
AU - Watson, Jean Paul
N1 - 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’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’s National Nuclear Security Administration under contract DE-NA-0003525. †Department of Systems and Industrial Engineering, University of Arizona, Tucson, AZ 85721 ([email protected]). ‡Sandia National Laboratories, Livermore, CA 94551 ([email protected], [email protected], [email protected], [email protected]). §Sandia National Laboratories, Albuquerque, NM 87185 ([email protected]).
Publisher Copyright:
© 2018 Society for Industrial and Applied Mathematics.
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
KW - Distributionally robust optimization
KW - Principal component analysis
KW - Semidefinite programming
KW - Stochastic programming
UR - http://www.scopus.com/inward/record.url?scp=85049682583&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85049682583&partnerID=8YFLogxK
U2 - 10.1137/16M1075910
DO - 10.1137/16M1075910
M3 - Article
AN - SCOPUS:85049682583
SN - 1052-6234
VL - 28
SP - 1817
EP - 1841
JO - SIAM Journal on Optimization
JF - SIAM Journal on Optimization
IS - 2
ER -