New Synergies Between Combinatorial and Continuous Optimization

组合优化和连续优化之间的新协同作用

• 批准号: RGPIN-2020-06141
• 负责人: Shepherd, Bruce
• 金额: $ 2.99万
• 依托单位: University of British Columbia
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=749911
• 关键词: New; Synergies; Between; Combinatorial; Continuous

Optimization refers to any problem where we have a list of feasible solutions and a measure on their relative desirability. The goal is to find the feasible solution which is most desirable. Intuitively, we partition these into one of two types: minimum cost problems or maximum profit. One does not need examples to understand that optimizing is a universal phenomenon which arises in essentially every organization. It is used to run hospitals, airlines, power grids and also to inform public policy. The dual faces of optimization are modelling and algorithms. Optimization remains vibrant partly by its continual infusion into new models and requirements arising in state-of-the-art applications in engineering, physics, medicine, statistics and computer science. These models place challenging new requirements on solution techniques or algorithms. In the countless ads for employees with expertise in analytics, data science, AI, logistics and machine learning, I often observe that organizations are seeking personnel with a maturity in optimization. It takes time to learn how to recognize opportunities for optimization in the wild. It also takes maturity to argue against the use of optimization when it does not make sense! The consummate optimizer has the confidence gained from understanding theoretical trade-offs (runtime efficiency, degree of optimality, code simplicity) together with intuition acquired from numerical experience. This proposal's focus is on new synergies between combinatorial and continuous optimization. There has been an increasing tendency for conceptual developments in the continuous and discrete realms to occur together for mutual benefit. Examples include advances in semi-definite programming, polynomial optimization, electrical flows in networks and submodular optimization. This interplay is a long-term positive force for optimization and this proposal identifies several themes which have the potential for expanding the interface between continuous and discrete optimization. Given the current demand for big-data models, it is natural that our research themes often have relatively simple algorithms (such as greedy or local search) at their core. For instance, one theme proposes a parameter for a polytope which measures precisely the performance of the (or a) greedy algorithm on the polytope. This notion of "greedy gap" is inspired by matroids but also has interesting connections to norm-constrained optimization. In a second theme, our objective is to extend the breakthrough results for the continuous greedy algorithm to be applicable to (max sum) diversity maximization problems. Diversity maximization is often used in the ubiquitous problem of clustering data points. This is done by choosing a small set of items which are "far apart" so that they act as cluster representatives.

优化是指任何问题，我们有一个可行的解决方案和衡量他们的相对可取性的列表。目标是找到最理想的可行方案。直觉上，我们将这些问题分为两类：最小成本问题或最大利润问题。我们不需要例子就能理解，优化是一种普遍现象，基本上出现在每个组织中。它被用于运行医院，航空公司，电网，并为公共政策提供信息。优化的两面性是建模和算法。优化仍然充满活力，部分原因是它不断注入新的模型和需求，这些模型和需求出现在工程、物理、医学、统计和计算机科学的最新应用中。这些模型对求解技术或算法提出了具有挑战性的新要求。在无数招聘具有分析、数据科学、人工智能、物流和机器学习专业知识的员工的广告中，我经常观察到，企业正在寻找在优化方面成熟的员工。学习如何在野外识别优化机会需要时间。当优化没有意义时，反对使用优化也需要成熟！完美的优化器通过理解理论上的权衡（运行时效率、最优程度、代码简单性）以及从数值经验中获得的直觉而获得信心。该提案的重点是组合优化和连续优化之间的新协同作用。在连续领域和离散领域的概念发展中，有一种日益增长的趋势是为了互利而共同发生。例子包括半定规划，多项式优化，网络中的电流和子模块优化的进展。这种相互作用是优化的长期积极力量，本提案确定了几个主题，这些主题有可能扩大连续优化和离散优化之间的界面。鉴于当前对大数据模型的需求，我们的研究主题通常以相对简单的算法（如贪婪或局部搜索）为核心。例如，一个主题提出了一个参数的多面体，它精确地衡量性能的（或）贪婪算法的多面体。这个“贪婪间隙”的概念是受拟阵的启发，但也与范数约束优化有着有趣的联系。在第二个主题中，我们的目标是扩展连续贪婪算法的突破性成果，以适用于（最大和）多样性最大化问题。多样性最大化经常用于数据点的聚类问题。这是通过选择一小组“相距甚远”的项目来完成的，这样它们就可以作为集群代表。