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

Pu Huang (puhuangus.ibm.com)
Dharmashankar Subramanian (dharmashus.ibm.com)

Abstract: We present a new algorithm, Iterative Estimation Maximization (IEM), for stochastic linear and convex programs with Conditional-Value-at-Risk (CVaR) constraints. IEM iteratively constructs a sequence of compact-sized linear, or convex, 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 satisfy a CVaR constraint. 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 )

Citation:

Download: [PDF]

Entry Submitted: 04/19/2008
Entry Accepted: 04/22/2008
Entry Last Modified: 04/23/2008

Modify/Update this entry