Learning algorithms for separable approximations of discrete stochastic optimization problems

• 成果类型: Article
• 署名作者: Powell, W; Ruszczynski, A; Topaloglu, H
• 署名单位: Princeton University; Rutgers University System; Rutgers University New Brunswick; Cornell University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1040.0107
• 发表日期: 2004
• 页码: 814-836
• 关键词: Allocation problem; linear-programs; DECOMPOSITION; newsvendor; networks; MODEL

摘要

We propose the use of sequences of separable, piecewise linear approximations for solving nondifferentiable stochastic optimization problems. The approximations are constructed adaptively using a combination of stochastic subgradient information and possibly sample information on the objective function itself. We prove the convergence of several versions of such methods when the objective function is separable and has integer break points, and we illustrate their behavior on numerical examples. We then demonstrate the performance on nonseparable problems that arise in the context of two-stage stochastic programming problems, and demonstrate that these techniques provide near-optimal solutions with a very fast rate of convergence compared with other solution techniques.