CAREER: Semidefinite Programming (SDP) Extended Formulations
职业:半定规划 (SDP) 扩展公式
基本信息
- 批准号:1452463
- 负责人:
- 金额:$ 50万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Continuing Grant
- 财政年份:2015
- 资助国家:美国
- 起止时间:2015-04-01 至 2020-03-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
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)计划拨款将探索半定优化问题的力量。这类广泛的优化问题是解决工程和计算机科学中许多现实世界问题的基础,也是分析算法理论性能的关键。基于半定优化的方法往往提供了更好的算法,但同时人们对半定优化问题的力量还只有部分了解。这项资助的主题是:如何最好地利用半定优化问题的力量?这笔拨款将把优化问题的结构与它们作为半定优化问题的可表现性联系起来,并探索有效解决大型半定规划的新方法。此外,它还将半定优化与较弱但更容易求解的所谓线性优化问题联系起来。了解半定优化问题的强大功能,将有助于我们更好地理解半定优化问题的理论计算复杂性和实际可行性。因此,这一结果将对社会和美国经济产生积极影响。紧密结合的教育计划将扩大代表不足群体的参与,并加强工程教育。半定程序的表达能力将在扩展公式的自然框架下进行研究,这是表示优化问题的统一方式。扩展公式对于线性规划非常成功,回答了长期悬而未决的问题。然而,对于更一般和更复杂的半定情形,人们知之甚少。这份职业资助金的一个主要方面是研究小型半定扩展公式的构造,以及强大的下界技术,潜在地允许有效地逼近困难的组合优化问题。从层次派生的结构化扩展公式已被证明是有效的,然而,人们还不太清楚它们何时可以被更一般的公式所超越。与这些方面密切相关的是关于半定扩展公式和线性扩展公式之间的关系的问题。虽然对于最大规模的实例,线性规划可以相当有效地求解,但众所周知,半定规划在实践中很难求解,因此可能需要求解线性近似。众所周知,这在一般情况下是不可能的,然而,对于大类感兴趣的问题,基于线性规划的近似可能提供充分的保证,并且识别充分条件是这一授权的一部分。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Sebastian Pokutta其他文献
Design and verify: a new scheme for generating cutting-planes
- DOI:
10.1007/s10107-013-0645-0 - 发表时间:
2013-02-15 - 期刊:
- 影响因子:2.500
- 作者:
Santanu S. Dey;Sebastian Pokutta - 通讯作者:
Sebastian Pokutta
An efficient first-order conditional gradient algorithm in data-driven sparse identification of nonlinear dynamics to solve sparse recovery problems under noise
一种在数据驱动的非线性动力学稀疏识别中有效的一阶条件梯度算法,用于解决噪声下的稀疏恢复问题
- DOI:
10.1016/j.cam.2025.116675 - 发表时间:
2025-12-15 - 期刊:
- 影响因子:2.600
- 作者:
Alejandro Carderera;Sebastian Pokutta;Christof Schütte;Martin Weiser - 通讯作者:
Martin Weiser
Absolute graphs with prescribed endomorphism monoid
- DOI:
10.1007/s00233-007-9029-1 - 发表时间:
2007-12-01 - 期刊:
- 影响因子:0.700
- 作者:
Manfred Droste;Rüdiger Göbel;Sebastian Pokutta - 通讯作者:
Sebastian Pokutta
Correction: Accelerated affine-invariant convergence rates of the Frank–Wolfe algorithm with open-loop step-sizes
- DOI:
10.1007/s10107-025-02214-3 - 发表时间:
2025-03-13 - 期刊:
- 影响因子:2.500
- 作者:
Elias Wirth;Javier Peña;Sebastian Pokutta - 通讯作者:
Sebastian Pokutta
Managing liquidity: Optimal degree of centralization
- DOI:
10.1016/j.jbankfin.2010.07.001 - 发表时间:
2011-03-01 - 期刊:
- 影响因子:
- 作者:
Sebastian Pokutta;Christian Schmaltz - 通讯作者:
Christian Schmaltz
Sebastian Pokutta的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Sebastian Pokutta', 18)}}的其他基金
EAGER: SC2: PHY-Layer-Integrated Collaborative Learning in Spectrum Coordination
EAGER:SC2:频谱协调中的 PHY 层集成协作学习
- 批准号:
1737842 - 财政年份:2017
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
Collaborative Research: Almost Symmetric Integer Programs
合作研究:几乎对称整数规划
- 批准号:
1333789 - 财政年份:2013
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
相似海外基金
Approximating Fixed-Order Scheduling Using Semidefinite Programming
使用半定规划近似固定顺序调度
- 批准号:
575791-2022 - 财政年份:2022
- 资助金额:
$ 50万 - 项目类别:
Alexander Graham Bell Canada Graduate Scholarships - Master's
Estimating turbulence and chaos using semidefinite programming
使用半定规划估计湍流和混沌
- 批准号:
RGPIN-2018-04263 - 财政年份:2022
- 资助金额:
$ 50万 - 项目类别:
Discovery Grants Program - Individual
Estimating turbulence and chaos using semidefinite programming
使用半定规划估计湍流和混沌
- 批准号:
RGPIN-2018-04263 - 财政年份:2021
- 资助金额:
$ 50万 - 项目类别:
Discovery Grants Program - Individual
EAGER‐QAC‐QSA: Quantum Chemistry with Mean-field Cost from Semidefinite Programming on Quantum Computing Devices
EAGER – QAC – QSA:量子计算设备上半定编程的具有平均场成本的量子化学
- 批准号:
2035876 - 财政年份:2020
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
Estimating turbulence and chaos using semidefinite programming
使用半定规划估计湍流和混沌
- 批准号:
RGPIN-2018-04263 - 财政年份:2020
- 资助金额:
$ 50万 - 项目类别:
Discovery Grants Program - Individual
AF:Small: Semidefinite Programming for High-dimensional Statistics
AF:Small:高维统计的半定规划
- 批准号:
2007676 - 财政年份:2020
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
Estimating turbulence and chaos using semidefinite programming
使用半定规划估计湍流和混沌
- 批准号:
522657-2018 - 财政年份:2019
- 资助金额:
$ 50万 - 项目类别:
Discovery Grants Program - Accelerator Supplements
Estimating turbulence and chaos using semidefinite programming
使用半定规划估计湍流和混沌
- 批准号:
RGPIN-2018-04263 - 财政年份:2019
- 资助金额:
$ 50万 - 项目类别:
Discovery Grants Program - Individual
Understanding Semidefinite Programming Duality Using Elementary Reformulations
使用基本重构理解半定规划对偶性
- 批准号:
1817272 - 财政年份:2018
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
Estimating turbulence and chaos using semidefinite programming
使用半定规划估计湍流和混沌
- 批准号:
DGECR-2018-00371 - 财政年份:2018
- 资助金额:
$ 50万 - 项目类别:
Discovery Launch Supplement