Continuous Approaches to Optimization Problems in Graphs

离散优化问题出现在许多重要的应用领域，包括计算生物化学、社会网络、电信和基于网络的大数据分析。该奖项资助基础研究，开发计算效率高的算法，用于使用连续优化技术解决困难的离散优化问题。除了对离散优化的基本贡献外，本研究的结果可能会刺激连续优化的新发展。所开发的方法将被整合到教学课程中，以及本科和研究生阶段的研究和教育项目中。虽然基于线性、半定和二次规划的凸松弛是离散优化问题精确算法的一个共同特征，但它们的非凸对立物尚未在此背景下进行研究，尽管其中一些可以有效地解决。本研究旨在通过研究允许二元二次公式的优化问题的非凸松弛来填补这一空白（例如，最大团/独立集问题，最小顶点覆盖，最大切割等）。本研究将发展和分析新的离散问题的连续非凸公式；基于离散优化问题的连续非线性公式，导出了离散优化问题的新的最优性条件；推导出连续优化一般和特殊情况下重要的计算复杂度结果；基于非线性公式得到下界和上界，可用于设计精确的分支定界算法；设计基于非凸、多项式时间可解松弛的近似算法（具有可证明的近似比）。

Discrete optimization problems arise in many important application areas, including computational biochemistry, social networks, telecommunications, and network-based analysis of big data. This award funds fundamental research to develop computationally efficient algorithms for solving hard discrete optimization problems using techniques from continuous optimization. In addition to fundamental contributions to discrete optimization, the results from this research may stimulate new developments in continuous optimization. The developed methodology will be integrated into the teaching curricula, as well as into research and educational programs at the undergraduate and graduate levels.While convex relaxations based on linear, semidefinite, and conic programming represent a common feature of exact algorithms for discrete optimization problems, their non-convex counterparts have not been studied in this context, even though some of them can be solved efficiently. This research is to fill this gap by investigating non-convex relaxations of optimization problems that admit binary quadratic formulations (e.g., the maximum clique/independent set problems, minimum vertex cover, max-cut, etc.). This research will develop and analyze new continuous non-convex formulations of discrete problems; derive new optimality conditions for discrete optimization problems based on their continuous nonlinear formulations; deduct important computational complexity results for general and special cases of continuous optimization; obtain lower and upper bounds based on nonlinear formulations that can be utilized in designing exact branch-and-bound algorithms; and design approximation algorithms (with provable approximation ratio) based on non-convex, polynomial-time solvable relaxations.