Sparse Matrix Algorithms and their Application to Dual Active Set Techniques in Optimization

稀疏矩阵算法及其在优化中双主动集技术的应用

• 批准号: 0203270
• 负责人: Timothy Davis
• 金额: $ 51万
• 依托单位: University of Florida
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-07-01 至 2007-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0203270&HistoricalAwards=false
• 关键词: Sparse; Matrix; Algorithms; their; Application

Davis, TimothyUniversity of Florida0203270The focus of this project is the development of innovative library-quality software and under-lying mathematics for dual active set techniques in optimization.The dual active set algorithm(DASA)was .rst introduced in the context of state constrained control problems,and later in thecontext of constrained mathematical programs.For linear or quadratic programming,each step ofthe algorithm is equivalent to solving a linear system of equations,and in successive steps,thereis a small rank change in the matrix corresponding to the change in the active set.Numericalexperience has shown that the dual active set framework is an extremely e .cient approach forsolving some broad classes of optimization problems,including problems in optimal control andquadratic network optimization.A version of the algorithm targeted to linear programming hasalready solved some LPs that other state-of-the-art packages are unable to solve.We will developa variety of sparse matrix techniques,which have broad applicability,and which provide,in par-ticular,the numerical foundation for DASA.Each technique will be developed into library-qualitysoftware and made widely available.These include:

Davis，蒂莫西佛罗里达大学 0203270 该项目的重点是开发创新的图书馆质量软件和优化中双活动集技术的基础数学。双活动集算法 (DASA) 首先在状态约束控制问题的背景下引入，后来在约束数学程序的背景下引入。对于线性或二次规划， 算法相当于求解线性方程组，并且在连续的步骤中，矩阵中存在与活动集的变化相对应的较小的秩变化。数值经验表明，对偶活动集框架是解决一些广泛的优化问题（包括最优控制和二次网络优化问题）的极其有效的方法。针对线性规划的算法版本已经存在 解决了一些其他最先进的软件包无法解决的LP。我们将开发各种稀疏矩阵技术，这些技术具有广泛的适用性，特别是为DASA提供数值基础。每种技术都将开发成库质量的软件并广泛使用。其中包括：