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.