CAREER: Semidefinite Programming (SDP) Extended Formulations

职业：半定规划 (SDP) 扩展公式

• 批准号: 1452463
• 负责人: Sebastian Pokutta
• 金额: $ 50万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-04-01 至 2020-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1452463&HistoricalAwards=false
• 关键词: CAREER; Semidefinite; Programming; SDP; Extended

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.

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