Optimization Online


Iterative Estimation Maximization for Stochastic Linear Programs with Conditional Value-at-Risk Constraints

Pu Huang (puhuang***at***us.ibm.com)
Dharmashankar Subramanian (dharmash***at***us.ibm.com)

Abstract: We present a new algorithm, Iterative Estimation Maximization (IEM), for stochastic linear programs with Conditional Value-at-Risk constraints. IEM iteratively constructs a sequence of compact-sized linear optimization problems, and solves them sequentially to find the optimal solution. The problem size IEM solves in each iteration is unaffected by the size of random samples, which makes it extreme efficient for real-world, large-scale problems. We prove that IEM converges to the true optimal solution, and give a lower bound on the number of samples required to probabilistically bound the solution error. Experiments show that IEM is an order of magnitude faster than the best known algorithm on large problem instances.

Keywords: Conditional Value at Risk, Stochastic Programs, Iterative Estimation Maximization

Category 1: Applications -- OR and Management Sciences (Finance and Economics )

Category 2: Stochastic Programming

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 04/19/2008
Entry Accepted: 04/22/2008
Entry Last Modified: 03/26/2009

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 Programming Society