Theory and Applications of Information-Based Complexity

基于信息的复杂性理论与应用

• 批准号: 0097348
• 负责人: Joseph Traub
• 金额: $ 24.99万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-08-15 至 2004-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0097348&HistoricalAwards=false
• 关键词: Theory; Applications; Information; Based; Complexity

Proposal #0097348Traub, Joseph F.Columbia UniversityThere is huge interest in solving high dimensional problems. Many applications involve functions of hundreds, thousands or even an infinite number of variables. Examples occur in physics, chemistry,mathematical finance, and economics. It is the rare high dimensional problem that can be solved analytically. Generally one must settle for an approximate numerical solution to within an error e. The computational complexity is the minimal computational resource need to solve a problem to within e. Time is the resource consideredand is measured by the number of information operations, arithmetic operations and comparisons. An example of an information operation is the computation of a function value.If a worst case deterministic assurance of an e-approximation is desired, then often the computational complexity depends exponentially on the number of variables d; the problem suffers the "curse ofdimensionality". Examples include integration, approximation, globaloptimization, integral and partial differential equations over typical isotropic classical spaces of r-times continuously differentiablefunctions. If the computational complexity is exponential in either 1/e or d the problem is said to be intractable. If the complexity is polynomial in 1/e and d, it is tractable. If, in addition, the minimal number of information operations, arithmetic operations and comparisons is independent of d the problem is strongly tractable. Intractability may sometimes be broken by settling for a stochastic assurance of error; examples are randomization (for instance, Monte Carlo) or the average case. A second way in which intractability mightbe broken is additional domain knowledge about the problem. An example of the domain knowledge is that the integrands in certain mathematical finance problems are non-isotropic. Additional domain knowledge can sometimes be used to make the problem strongly tractable even in the worst case deterministic setting!Continuation of research on achieving tractability and strong tractability is proposed. In particular, one proposed area of research is under what conditions is a double-win achievable for high dimensional integration: * convergence faster than Monte Carlo, * with a worst case deterministic assurance.The theoretical results will be used to improve the FinDer software system. More generally, research is proposed on the following topics: * Theory and Computer Experiments for Mathematical Finance, * Tractability of Quasi-Monte Carlo and Monte Carlo Algorithms, * Variable Smoothness, * Generalized Tractability.

Proposal #0097348 Traub，Joseph F.哥伦比亚大学在解决高维问题方面有着巨大的兴趣。许多应用程序涉及数百，数千甚至无限数量的变量的函数。例子出现在物理学，化学，数学金融学和经济学。这是罕见的高维问题，可以解析解决。一般来说，必须满足于误差e以内的近似数值解。计算复杂度是在e.时间是一种资源，它是通过信息运算、算术运算和比较的次数来衡量的。信息运算的一个例子是函数值的计算。如果期望在最坏情况下确定性地保证e-近似，那么计算复杂度通常指数地依赖于变量的数量d;该问题遭受“维数灾难”。例子包括积分，近似，全局优化，积分和偏微分方程在典型的各向同性经典空间的r次连续微分函数。如果计算复杂度在1/e或d中是指数的，则该问题被称为是难处理的。如果复杂度是1/e和d的多项式，则它是易处理的。 此外，如果信息运算、算术运算和比较的最小数目与d无关，则问题是强易处理的。有时，通过满足于随机的误差保证，可以打破顽固性;例子是随机化（例如，蒙特卡罗）或平均情况。第二种方法是增加关于问题的领域知识。领域知识的一个例子是某些数学金融问题中的被积函数是各向异性的。附加的领域知识有时可以用来使问题变得非常容易处理，即使是在最坏的情况下确定性设置！提出了实现易处理性和强易处理性的研究方向。特别是，一个拟议的研究领域是在什么条件下是一个双赢的实现高维集成： * 收敛速度比蒙特卡罗更快， * 最坏情况下的确定性保证。理论结果将用于改进Finder软件系统。 更一般地说，建议就下列专题进行研究： * 金融数学理论与计算机实验， * 拟蒙特卡罗和蒙特卡罗算法的易处理性， * 可变平滑度， * 广义可追踪性