Optimization Online


Distributionally Robust Optimization with Principal Component Analysis

Jianqiang Cheng(jianqiang.cheng***at***gmail.com)
Richard Chen(rlchen***at***sandia.gov)
Habib Najm(hnnajm***at***sandia.gov)
Ali Pinar(apinar***at***sandia.gov)
Cosmin Safta(csafta***at***sandia.gov)
Jean-Paul Watson(jwatson***at***sandia.gov)

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 optimization. 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 size. In this paper, 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 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. For certain classes of distributionally robust conditional value-at-risk (CVaR) problems, the proposed PCA approximation using only 50% of the principal components provides a near-optimal solution (within 1%) with a one to two order of magnitude reduction in computation time. Finally, the proposed PCA approximation is exact when all principal components are used and significantly outperforms the original reformulation with respect to computation time.

Keywords: stochastic programming, distributionally robust optimization, principal component analysis, semidefinite programming

Category 1: Stochastic Programming

Category 2: Robust Optimization


Download: [PDF]

Entry Submitted: 05/18/2016
Entry Accepted: 05/18/2016
Entry Last Modified: 05/18/2016

Modify/Update this entry

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


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