Optimization algorithms: worst-case behaviours and related conjectures

通过定量建模和分析进行理性决策是运筹学背后的指导原则，运筹学是一个在研究和工业中有几个深远应用的领域。运筹学关注的几个领域是寻找资源的最优分配、调度任务和设计原型。在许多情况下，这些问题可以表示或近似为线性优化问题，这涉及到在由一组线性不等式定义的区域上最大化或最小化线性函数。单纯形法和原对偶内点法是目前计算最成功的线性最优化算法。单纯形方法遵循边缘路径，而内点方法遵循中心路径。在这个框架内，多面体的曲率，定义为相关中心路径的最大可能总曲率，可以被视为其直径的连续模拟。算法问题与可行域的组合和几何结构密切相关。我的研究建议集中在这些计算上成功的线性最优化算法与输入的几何和组合结构之间的相互联系。该方法基于具有增强的组合和几何性质的新的多面体结构的组合，以及对当前建立的边界的更紧密的分析。

Rational decision-making through quantitative modelling and analysis is the guiding principle behind operations research, a field with several far-reaching applications in research and industry. Finding optimal allocations of resources, scheduling tasks, and designing prototypes are a few of the areas operations research is concerned with. In many cases, these problems can be formulated or approximated as linear optimization problems, which involve maximizing or minimizing a linear function over a domain defined by a set of linear inequalities. The simplex and primal-dual interior point methods are currently the most computationally successful algorithms for linear optimization. While the simplex methods follow an edge path, the interior point methods follow the central path. Within this framework, the curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as the continuous analogue of its diameter. The algorithmic issues are closely related to the combinatorial and geometric structure of the feasible region. My research proposal focuses on the interconnections between these computationally successful algorithms for linear optimization, and the geometric and combinatorial structure of the input. The methodology is based on a combination of new polyhedral constructions with enhanced combinatorial and geometric properties and a tighter analysis of the currently established bounds.