Discrete Moment Problems and Applications

离散矩问题及应用

• 批准号: 0856663
• 负责人: Andras Prekopa
• 金额: $ 30万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-15 至 2013-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0856663&HistoricalAwards=false
• 关键词: Discrete; Moment; Problems; Applications

The research objective of this project is to develop new models and methods to find sharp bounds in a numerically stable and computationally efficient manner, under the knowledge of the support of the discrete random variables involved and partial knowledge of their distribution. In many cases this means the knowledge of a finite number of moments, including in the multivariate case problems where the univariate marginals and some of the moments are known. These type of problems, including the Boolean Probabillity Bounding Problem, Discrete Moment Problems and Multivariate Discrete Moment Problems, are notoriously difficult computationally, and can equivalently be viewed as very large scale (typically exponentially large in the number of random variables) linear programming problems. Linear programming will be the basic methodology of the proposed research focusing on the special combinatorial structure of the arising linear programs. In addition, multivariate Lagrange interpolation and graph theoretical tools will be used and further developed. The linear programs arising in this research area are either of exponential size or numerically unstable. New constraint generation techniques, aggregation and disaggregation procedures, as well as special arithmetic procedures will be used to come up with sharp and efficiently computable bounds.If successful, the results of this research will lead to new and computationally efficient methods to derive sharp probability bounds. The quality and computational complexity of such bounds is the bottleneck in numerous applications, including communication/transportation/electric network reliability analysis, financial engineering, risk analysis, as well as stochastic optimization problems. In particular, the improved methodology will allow better planning for extreme events in large stochastic networks, such as evaluating emergency evacuation plans in transportation networks, preparing for heat events in electric networks, etc. The proposed work will also contribute to the theory and computational methodology of linear programming.

该项目的研究目标是开发新的模型和方法，在知道所涉及的离散随机变量的支持和部分了解其分布的情况下，以数值稳定和计算高效的方式找到尖锐的边界。在许多情况下，这意味着知道有限数量的矩，包括在多元情况下的问题，其中单变量的边际和一些矩是已知的。这些类型的问题，包括布尔概率边界问题，离散矩问题和多元离散矩问题，在计算上是出了名的困难，并且可以等效地视为非常大规模（通常在随机变量的数量上呈指数级增长）线性规划问题。本文将以线性规划为基本方法论，重点研究新兴线性规划的特殊组合结构。此外，多元拉格朗日插值和图理论工具将被使用和进一步发展。在这个研究领域中出现的线性规划要么是指数大小的，要么是数值不稳定的。新的约束生成技术，聚合和分解过程，以及特殊的算术过程将被用来提出清晰和有效的可计算边界。如果成功，这项研究的结果将导致新的和计算效率高的方法来推导尖锐的概率界限。这些边界的质量和计算复杂性是许多应用中的瓶颈，包括通信/交通/电网可靠性分析、金融工程、风险分析以及随机优化问题。特别是，改进的方法将允许对大型随机网络中的极端事件进行更好的规划，例如评估交通网络中的紧急疏散计划，为电网中的热事件做好准备等。所建议的工作也将有助于线性规划的理论和计算方法。