Approximatiom and Polynomial-time Algorithms for Structured Optimization

结构化优化的近似和多项式时间算法

• 批准号: 9618796
• 负责人: Michael Grigoriadis
• 金额: $ 24.55万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-03-15 至 2001-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9618796&HistoricalAwards=false
• 关键词: Approximatiom; Polynomial; time; Algorithms; Structured

This research addresses theoretical and computational aspects of structured optimization: polynomial-time algorithms, fully polynomial-time approximation schemes, complexity issues related to semidefinite programming, and numerical experimentation. The goals are: (1) to study the efficiency of widely-used Lagrangian decomposition techniques with emphasis on the development of nearly-optimal potential-reduction methods; (2) to study general block-angular and linear bordered block-diagonal problems, and, time permitting, their specialized applications in combinatorics, operations research, communications, engineering and finance; (3) to explore the complexity of semidefinite programming with real and integer variables; and (4) to conduct computational experiments which will examine the numerical behavior and practical performance of the developed algorithms.

本研究涉及结构优化的理论和计算方面：多项式时间算法，完全多项式时间近似方案，与半定规划相关的复杂性问题，以及数值实验。目标是：（1）研究广泛使用的拉格朗日分解技术的效率，重点是发展接近最佳的潜在减少方法;（2）研究一般块角和线性边界块对角问题，并在时间允许的情况下，在组合学，运筹学，通信，工程和金融方面的专门应用;（3）探索具有真实的和整数变量的半定规划的复杂性;（4）进行计算实验，以检验所开发的算法的数值行为和实际性能。