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.