Total variation bounds on the expectation of periodic functions with applications to recourse approximations

• 成果类型: Article
• 署名作者: Romeijnders, Ward; van der Vlerk, Maarten H.; Haneveld, Willem K. Klein
• 署名单位: University of Groningen
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0829-2
• 发表日期: 2016
• 页码: 3-46
• 关键词: stochastic-programming problems; simple integer recourse; convex approximations; scenario reduction; linear-programs; models; algorithms; optimization

摘要

We derive a lower and upper bound for the expectation of periodic functions, depending on the total variation of the probability density function of the underlying random variable. Using worst-case analysis we derive tighter bounds for functions that are periodically monotone. These bounds can be used to evaluate the performance of approximations for both continuous and integer recourse models. In this paper, we introduce a new convex approximation for totally unimodular recourse models, and we show that this convex approximation has the best worst-case error bound possible, improving previous bounds with a factor 2. Moreover, we use similar analysis to derive error bounds for two types of discrete approximations of continuous recourse models with continuous random variables. Furthermore, we derive a tractable Lipschitz constant for pure integer recourse models.