AF: SMALL: Topics in Bridging Continuous and Discrete Optimization

离散数学中一个著名的结果是，任何地图上的国家都可以被赋予四种颜色中的一种，这样任何两个共享边界的国家都会有不同的颜色。在数学中，这个结果通常被表述为任何平面图都是四色的。这一结果的证明涉及对数百个个案的检查；这个结果的第一个证明（给出于1976年）是最早使用计算机进行检验的著名数学证明之一。本项目尝试用不同的途径来获得这一证明，其中包括使用连续函数的优化来获得一个乍一看根本不涉及连续量的结果（因为最终人们只想在每个国家使用四种颜色中的一种）。其目标是消除原始证明中的所有案例检查。这样的证明将进一步增强数学家的信心，使他们相信最初的证明没有遗漏任何重要的情况。该项目还包括其他问题，这些问题使用连续优化来获得优化离散量的结果。这些结果包括尝试最小化一般（非平面）图上色时使用的颜色数量，以及找到解决某些类型的线性方程组的实用算法。这项研究将被用作向本科生推广的一种手段，并使他们参与到他们的项目中。特别是，本项目探索了离散和连续优化界面的几个新进展方向。第一个回归到使用半定规划技术，线性规划的扩展，在复数上突破了近20年的3色图着色障碍。第二部分考虑用半定规划方法直接证明著名的四色平面定理。第三章考虑了一种基于特征向量的逼近算法来解决Trevisan问题，并寻找可能的改进和扩展。第四章着眼于解决由Kelner、Orrechia、Sidford和Zhu提出的拉普拉斯方程组的算法，并考虑了可能使该算法与当前线性系统求解器竞争的方向。这些方向包括批处理更新和查看算法的双重版本。第五个方向，也是最后一个方向，着眼于霍夫曼和辛格尔顿在谱图理论方面的早期成果，并考虑是否可以解决该论文中遗留的一个未决问题。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

One well-known result in discrete mathematics is that the countries for any map can be given one of four colors so that any two countries sharing a border will have different colors. In mathematics, this result is usually stated as saying that any planar graph is four-colorable. The proofs of this result that are known involve checking hundreds of individual cases; the first proof of this result (given in 1976) was one of the first well-known mathematical proofs to involve computers in doing the checking. This project attempts a different route to obtain this proof, one that involves using the optimization of continuous functions to obtain a result that at first glance appears not to involve continuous quantities at all (since in the end one only wants to use one of four colors per country). The goal is to eliminate all the case-checking that went into the original proof. Such a proof would give further confidence to mathematicians that the original proofs did not miss any important cases. The project includes other problems that have this flavor of using continuous optimization to obtain results in optimizing discrete quantities. These include other results in trying to minimize the number of colors used in coloring general (non-planar) graphs, and finding practical algorithms to solve certain types of linear systems of equations. The research will be used as a means of outreach to undergraduates, and involve them in their project. In particular, this project explores several new directions for progress on the interface of discrete and continuous optimization. The first returns to the technique of using semidefinite programming, an extension of linear programming, over the complex numbers to break through a nearly 20-year old barrier in coloring 3-colorable graphs. The second considers finding a direct proof of the famous theorem about four-coloring planar graphs via semidefinite programming. The third considers an eigenvector-based approximation algorithm for the maximum-cut problem due to Trevisan and looks for possible improvements and extensions. The fourth looks at an algorithm for solving Laplacian systems of equations due to Kelner, Orrechia, Sidford, and Zhu, and considers possible directions that might make the algorithm competitive with current linear-system solvers. These directions include batching updates and looking at a dual version of the algorithm. The fifth and final direction looks at an early result in spectral graph theory due to Hoffman and Singleton, and considers whether one remaining open issue in that paper can be resolved.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.