Discrete Moment Problems and Applications

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

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.