First Order Convergence Analysis for Sparse Grid Method in Stochastic Two-Stage Linear Optimization Problem

• 作者: Shengyuan Chen
• 来源期刊: 美国计算数学期刊(英文)
• 学科: 数学
• 关键词: Convergence ANALYSIS STOCHASTIC Optimization SCENARIO Generation CONVEX ANALYSIS Measure Theory
• 年，卷（期）: 2011,（4）
• 页码范围: 294-302
• 页数: 9页
• 分类号: O1

摘要

Stochastic two-stage linear optimization is an important and widely used optimization model. Efficiency of numerical integration of the second stage value function is critical. However, the second stage value function is piecewise linear convex, which imposes challenges for applying the modern efficient spare grid method. In this paper, we prove the first order convergence rate of the sparse grid method for this important stochastic optimization model, utilizing convexity analysis and measure theory. The result is two-folded: it establishes a theoretical foundation for applying the sparse grid method in stochastic programming, and extends the convergence theory of sparse grid integration method to piecewise linear and convex functions.