Understanding Semidefinite Programming Duality Using Elementary Reformulations

半定规划是近几十年来出现的最通用、最有用、最有趣的优化问题之一。它们在工程、经济和机器学习等领域都有应用。在过去的几十年里，成千上万的论文发表在SDPs上。然而，SDP通常是病态的：它们可能无法达到其最优值，和/或其最优值可能与其对偶的最优值不同。这样的SDP经常击败甚至最好的SDP求解器，其失败或报告不正确的解决方案。 我们能用从高斯消去法继承来的行操作这样简单的东西来理解这些病态吗？该项目旨在肯定地回答这个问题，并导致半定规划，更广泛地说，在凸优化的理论和计算进步。研究所将在国际和国内会议上广泛传播研究结果，并对博士生进行培训。 一个线性方程组可能是病态的，因为它可能没有解。我们可以通过将系统转换为包含不可能方程的标准形式来理解这种病理。该转换基于基本行操作。该项目旨在使用相同的操作将SDP转换为规范形式，从中很容易看到它们的病理（例如正对偶间隙）。因此，在理论方面，该项目将表明，初等行运算-线性代数中的主要工具-有助于理解更一般的一类问题，SDP，甚至更广泛的凸优化问题。在计算方面，该项目将开发一个有用的问题库来测试SDP求解器和其他圆锥优化求解器。因此，除了发展理论，该项目将有助于解决方法的发展。该奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

Semidefinite programs (SDPs) are some of the most versatile, useful, and interesting optimization problems to emerge in the last few decades. They find uses in engineering, economics, and machine learning, to name just a few areas. In the last few decades thousands of papers have been published on SDPs. However, SDPs are often pathological: they may not attain their optimal values, and/or their optimal value may differ from that of their dual. Such SDPs often defeat even the best SDP solvers, which fail or report an incorrect solution. Can we understand these pathologies using something as simple as row operations inherited from Gaussian elimination? The project aims to answer this question affirmatively and lead to both theoretical and computational advances in semidefinite programming, and more broadly, in convex optimization. The PI will broadly disseminate the results, both in international and domestic conferences, and by training doctoral students. A linear system of equations can be pathological in the sense that it may not have a solution. We can understand this pathology by transforming the system into a standard form that contains an impossible equation. The transformation is based on elementary row operations. The proposed project aims to use the same operations to transform SDPs into a canonical form, from which their pathology (say positive duality gap) is easy to see. Thus, on the theoretical side the project will show that elementary row operations - a staple tool in linear algebra - are useful to understand a much more general class of problems, SDPs, and even more broadly, convex optimization problems. On the computational side the project will develop a useful problem library to test SDP solvers, and other conic optimization solvers. Thus, besides developing theory, the project will contribute to the development of solution methods.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.