Geometric Methods in the Probabilistic Analysis of Condition Numbers

在数值分析和优化中，许多迭代算法的运行时间受输入条件数的影响。对随机输入条件数的概率分布的研究导致了这种算法运行时间的概率分析。在许多情况下，输入的条件数与给定输入到一组不适定输入的逆距离成正比。在这种情况下，可以通过研究病态输入集合的几何来得到随机输入条件数的概率分布。该项目的目标是探索这种几何方法的范围和局限性，特别强调开发处理不同输入分布、结构化条件数和优化理论背景下出现的条件数的方法。最终，拟议的研究项目有望有助于更好地理解数值和优化算法在实践中观察到的性能。

The running time of many iterative algorithms in numerical analysis and optimisation is dominated by the condition number of the input. The study of the probability distribution of condition numbers for random inputs thus leads to a probabilistic analysis of the running time of such algorithms. In many cases, the condition number of an input is proportional to the inverse distance of the given input to a set of ill-posed inputs. In these situations, results about the probability distribution of condition numbers for random inputs can be obtained from studying the geometry of the set of ill-posed inputs. The goal of this project is to explore the scope and limitations of this geometric approach, with a particular emphasis on developing methods for dealing with different input distributions, with structured condition numbers, and with condition numbers arising in the context of optimisation theory. Ultimately, the proposed research project is expected to contribute to a better understanding of the performance of numerical and optimisation algorithms as observed in practice.