CAREER: Semidefinite Programming (SDP) Extended Formulations

这项教师早期职业发展(Career)计划拨款将探索半定优化问题的力量。这类广泛的优化问题是解决工程和计算机科学中许多现实世界问题的基础，也是分析算法理论性能的关键。基于半定优化的方法往往提供了更好的算法，但同时人们对半定优化问题的力量还只有部分了解。这项资助的主题是：如何最好地利用半定优化问题的力量？这笔拨款将把优化问题的结构与它们作为半定优化问题的可表现性联系起来，并探索有效解决大型半定规划的新方法。此外，它还将半定优化与较弱但更容易求解的所谓线性优化问题联系起来。了解半定优化问题的强大功能，将有助于我们更好地理解半定优化问题的理论计算复杂性和实际可行性。因此，这一结果将对社会和美国经济产生积极影响。紧密结合的教育计划将扩大代表不足群体的参与，并加强工程教育。半定程序的表达能力将在扩展公式的自然框架下进行研究，这是表示优化问题的统一方式。扩展公式对于线性规划非常成功，回答了长期悬而未决的问题。然而，对于更一般和更复杂的半定情形，人们知之甚少。这份职业资助金的一个主要方面是研究小型半定扩展公式的构造，以及强大的下界技术，潜在地允许有效地逼近困难的组合优化问题。从层次派生的结构化扩展公式已被证明是有效的，然而，人们还不太清楚它们何时可以被更一般的公式所超越。与这些方面密切相关的是关于半定扩展公式和线性扩展公式之间的关系的问题。虽然对于最大规模的实例，线性规划可以相当有效地求解，但众所周知，半定规划在实践中很难求解，因此可能需要求解线性近似。众所周知，这在一般情况下是不可能的，然而，对于大类感兴趣的问题，基于线性规划的近似可能提供充分的保证，并且识别充分条件是这一授权的一部分。

This Faculty Early Career Development (CAREER) Program grant will explore the power of Semidefinite Optimization problems. This broad class of optimization problems is fundamental to solving many real-world problems in engineering and computer science as well as pivotal in analyzing the theoretical performance of algorithms. Approaches based on semidefinite optimization often provide superior algorithms yet at the same time the power of semidefinite optimization problems is only partially understood. The leitmotif of this grant is: How best to exploit the power of semidefinite optimization problems? This grant will relate the structure of optimization problems to their representability as semidefinite optimization problems and explore new ways of solving large semidefinite programs efficiently. Moreover, it will relate semidefinite optimization to the weaker but more easily solvable class of so called linear optimization problems. Understanding the power of semidefinite optimization problems will advance both our understanding of theoretical computational complexity as well as practical feasibility of solving semidefinite optimization problems. As such the results will positively impact both society and the U.S. economy. The tightly integrated educational program will broaden the involvement of under-represented groups and enhance engineering education.The expressive power of semidefinite programs will be studied in the natural framework of extended formulations, which is a unified way of denoting optimization problems. Extended formulations have been highly successful for linear programming, answering long standing open problems. However very little is known about the more general and significantly more complex semidefinite case. A major aspect of this CAREER grant is to study both the construction of small semidefinite extended formulations, as well as strong lower bounding techniques, potentially allowing for efficient approximations of hard combinatorial optimization problems. Structured extended formulations derived from hierarchies have proven to be powerful however it is not well-understood when they can be outperformed by more general formulations. Closely related to these aspects is the question regarding the relation between semidefinite extended formulations and linear extended formulations. While linear programs can be solved rather efficiently for largest scale instances, semidefinite programs are notoriously hard to solve in practice, so that it can be desirable to solve a linear approximation instead. It is known that this is not possible in general, however for large classes of problems of interest linear programming based approximation might provide sufficient guarantees and identifying sufficient conditions is part of this grant.