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

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

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: