Information-Based Complexity of Multivariate Problems

多元问题的基于信息的复杂性

• 批准号: 9729971
• 负责人: Grzegorz Wasilkowski
• 金额: $ 20.9万
• 依托单位: University of Kentucky Research Foundation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-06-01 至 2001-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9729971&HistoricalAwards=false
• 关键词: Information; Based; Complexity; Multivariate; Problems

Multivariate problems appear in many diverse applications; yet they are often intractable in the worst case setting. A significant part of the research will concentrate on the study of multivariate problems in the average case setting. In particular, the study of the reduction in complexity by switching from the worst case to the average case setting will be one of the central foci. This will enrich understanding of the average case complexity of important multivariate problems and will provide new algorithms that solve worst case intractable problems with small expected cost and small expected error. Related to the average case analysis are path integrals. The research will provide complexity bounds for his important problem and should reveal new algorithms that are more efficient than Monte Carlo methods (that are commonly used) for some path integrals. One of the approaches in studying path integrals is through the analysis of multivariate weighted integration and approximation over unbounded domains. A part of the research will deal with the complexity of such problems. In addition to theoretical results, the research will result in efficient software for such problems as multivariate integration/approximation, weighted integration/approximation, and path integrals.

多变量问题出现在许多不同的应用中，但它们在最坏的情况下往往是棘手的。研究的一个重要部分将集中在平均情况下设置的多变量问题的研究。 特别是，通过从最坏情况切换到平均情况设置来降低复杂性的研究将是中心焦点之一。这将丰富重要的多变量问题的平均情况下的复杂性的理解，并将提供新的算法，解决最坏情况下棘手的问题，小的预期成本和小的预期误差。与平均情况分析相关的是路径积分。这项研究将提供复杂的界限，他的重要问题，并应揭示新的算法，是更有效的比蒙特卡罗方法（这是常用的），一些路径积分。研究路径积分的途径之一是通过分析无界域上的多元加权积分和逼近。这项研究的一部分将涉及这些问题的复杂性。除了理论结果，研究将导致有效的软件等问题的多元集成/近似，加权集成/近似，路径积分。