Linear Algebra Enhancements to the PATH Solver
作者： Todd Munson , Michael C. Ferris , Qian Li
DOI:
关键词: Key (cryptography) 、 Scheme (programming language) 、 Solver 、 Component (UML) 、 Mathematics 、 Reliability (computer networking) 、 Path (graph theory) 、 Mathematical optimization 、 Linear algebra 、 Linear system
摘要: This research aims enhancing the efficiency and reliability of PATH, most widely used solver for mixed complementarity problems. A key component PATH algorithm is solving a series linear complementary subproblems with pivotal scheme. Improving system routines (factor, solve, update) required by method critical computational issue. We incorporate two new options besides default LUSOL package in such functionalities. One employs UMFPACK factor solve operations, together an implementation stable efficient block-LU updating scheme, which l eads to significantly more effective version many large-scale sparse systems. The other option exploits COIN-OR utilities enhanced adapting refinements scaling schemes COIN-LP routines, smaller-scale systems but less competitive on cases.
参考文章(28)
R. M. Chamberlain, M. J. D. Powell, C. Lemarechal, H. C. Pedersen, The watchdog technique for forcing convergence in algorithms for constrained optimization Mathematical Programming Studies. pp. 1- 17 ,(1982) , 10.1007/BFB0120945
A. K. Cline, Two Subroutine Packages for the Efficient Updating of Matrix Factorizations University of Texas at Austin. ,(1977)
Michael C. Ferris, Todd S. Munson, Interfaces to PATH 3.0: Design, Implementation and Usage Computational Optimization and Applications. ,vol. 12, pp. 207- 227 ,(1999) , 10.1023/A:1008636318275
Walter Murray, Philip E. Gill, Margaret H. Wright, Numerical linear algebra and optimization Addison-Wesley Pub. Co., Advanced Book Program. ,(1991)
Stephen C. Billups, Steven P. Dirkse, Michael C. Ferris, A Comparison of Large Scale Mixed Complementarity Problem Solvers Computational Optimization and Applications. ,vol. 7, pp. 3- 25 ,(1997) , 10.1023/A:1008632215341
Richard Ericson, Ariel Pakes, Markov-Perfect Industry Dynamics: A Framework for Empirical Work The Review of Economic Studies. ,vol. 62, pp. 53- 82 ,(1995) , 10.2307/2297841
Stephen M. Robinson, Normal maps inducted by linear transformations Mathematics of Operations Research. ,vol. 17, pp. 691- 714 ,(1992) , 10.1287/MOOR.17.3.691
J. J. H. Forrest, J. A. Tomlin, Updated triangular factors of the basis to maintain sparsity in the product form simplex method Mathematical Programming. ,vol. 2, pp. 263- 278 ,(1972) , 10.1007/BF01584548
Steven P. Dirkse, Michael C. Ferris, Mcplib: a collection of nonlinear mixed complementarity problems Optimization Methods & Software. ,vol. 5, pp. 319- 345 ,(1995) , 10.1080/10556789508805619
Timothy A. Davis, A column pre-ordering strategy for the unsymmetric-pattern multifrontal method ACM Transactions on Mathematical Software. ,vol. 30, pp. 165- 195 ,(2004) , 10.1145/992200.992205