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.