New Synergies Between Combinatorial and Continuous Optimization

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

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.