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

点击翻译按钮获取中文摘要

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: