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.