Optimization algorithms: worst-case behaviours and related conjectures

优化算法：最坏情况行为和相关猜想

• 批准号: 311969-2010
• 负责人: Deza, Antoine
• 金额: $ 2.4万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2014
• 资助国家: 加拿大
• 起止时间: 2014-01-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=548578
• 关键词: Optimization; algorithms; worst; case; behaviours

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.

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