CAREER: Semidefinite Programming (SDP) Extended Formulations

这项教师早期职业发展（Career）计划将探索半确定优化问题的力量。这类广泛的优化问题是解决工程和计算机科学中许多现实问题的基础，也是分析算法理论性能的关键。基于半定优化的方法往往提供了更好的算法，但与此同时，人们对半定优化问题的能力却只有部分的了解。这项资助的主题是：如何最好地利用半确定优化问题的力量？这项资助将把优化问题的结构与它们作为半确定优化问题的可表征性联系起来，并探索有效解决大型半确定规划的新方法。此外，它将半确定优化与较弱但更容易解决的一类所谓的线性优化问题联系起来。了解半定优化问题的力量将促进我们对理论计算复杂性的理解以及解决半定优化问题的实际可行性。因此，其结果将对社会和美国经济产生积极影响。紧密结合的教育计划将扩大代表性不足的群体的参与，并加强工程教育。在扩展公式的自然框架中研究半定规划的表达能力，这是表示最优化问题的一种统一方式。扩展公式在线性规划方面非常成功，回答了长期存在的开放性问题。然而，对于更一般和更复杂的半确定情况，我们所知甚少。这项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.