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