RIA:Complexity Analysis and Optimal Algorithms for NonlinearProblems

这一建议涉及复杂性分析和解决非线性问题的最优算法的开发。不同于目前大多数复杂性研究本质上是离散的，本方案所考虑的问题是一个或多个实变量的(分段)连续函数。因此，这些问题的复杂性分析工具不同于传统的复杂性分析，而是基于基于信息的复杂性的思想。问题复杂性上界的发展类似于经典的数值分析(实际上可以借鉴其中的前人工作)。问题复杂性下界的推导是本研究的一个新颖方面，可以大致描述如下：利用数学技巧，一个人开发出一组函数，这些函数具有问题的不同解，但使用给定的信息量是不可区分的。除非这组函数是单例的，否则没有任何算法可以解决这个问题。这为解决问题所需的信息量提供了下限，进而限制了问题的复杂性。虽然概念很简单，但推导出一个特定的界限通常是相当困难的，并且通常提供了有助于实现更好的上限的见解。本研究涉及的非线性问题将包括一维或多维拓扑度计算的最坏情况分析和平均情况分析，一维、二维和三维的Lipschitz函数求根，以及从函数值分割/重构重叠函数(带有计算机视觉的限制)。这些问题既有理论上的重要性，也有实践上的重要性，为分析这些问题而开发的技术应该在其他地方有用。

This proposal involves complexity analysis and the development of optimal algorithms for the solution of nonlinear problems. Unlike most current research in complexity which is discrete in nature, the problems considered in this proposal are (piecewise) continuous functions of one or more real variables. The tools for complexity analysis of these problems thus differ from traditional complexity analysis and are based on the ideas of information-based complexity. The development of an upper bound on problem complexity is similar to classical numerical analysis (and may in fact borrow from previous work therein). The derivation of lower bounds on a problem's complexity is one of the novel aspects of this research, and can be roughly described as follows: Using mathematical techniques, one develops a set of functions with different solutions to the problem but which are indistinguishable using a given amount of information. Unless this set of functions is a singleton no algorithm can solve the problem. This provides lower bounds on the amount of information required to solve the problems, which in turn bounds the problem complexity from below. While the concepts are simple, the derivation of a particular bound is generally quite difficult, and often provides insight useful for achieving better upper bounds. The nonlinear problems addressed in this research will include both worst-case and "average"-case analysis of the computation of topological degree in one or more dimensions, root-finding for Lipschitz function in one two and three dimensions, and segmentation/reconstruction of overlapping functions from function values (with restrictions from computer vision). These problems have both theoretical and practical importance, and the techniques developed for their analysis should be useful elsewhere.