New Synergies Between Combinatorial and Continuous Optimization

点击翻译按钮获取中文摘要

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.