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.