Algorithms, Complexity and Implementations for Structured Optimization

结构化优化的算法、复杂性和实现

• 批准号: 9208539
• 负责人: Michael Grigoriadis
• 金额: $ 33.49万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-08-15 至 1996-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9208539&HistoricalAwards=false
• 关键词: Algorithms; Complexity; Implementations; Structured; Optimization

This project on large-scale optimization has two main objectives: to gain better theoretical understanding of the effectiveness of sequential and parallel, and deterministic and randomized structure-exploiting methods, and to conduct large-scale experimentation leading to fast and numerically- robust implementations for solving various types of block- structured problems. A wide class of methods for general block-structured linear and convex optimization problems will be studied. The development of these methods draws upon ideas of potential-function reduction, block-coordinate descent, adaptations of scaling techniques of interior-point methods, and hybrid approaches. Theoretical emphasis will be on the complexity analysis of structure-exploiting procedures. Practical emphasis will be on the approximate solution of large-scale problems with various blocks, including special types of blocks amenable to efficient combinatorial algorithms.

这个大规模优化项目有两个主要目标：更好地理论理解顺序和并行、确定性和随机结构开发方法的有效性，并进行大规模实验，以实现快速且数值鲁棒的实现，以解决各种类型的块结构问题。 将研究用于一般块结构线性和凸优化问题的多种方法。 这些方法的发展借鉴了势函数约简、块坐标下降、内点方法的缩放技术和混合方法的思想。 理论重点将放在结构利用程序的复杂性分析上。 实际重点将放在使用各种块（包括适合高效组合算法的特殊类型的块）来近似解决大规模问题。