Exact Matrix Factorization Updates for Nonlinear Programming
提出一种无舍入误差的秩一更新算法，用于高效求解非线性规划中序列相关的线性方程组，在稠密矩阵上比现有精确分解快75倍以上。
LU and Cholesky matrix factorization algorithms are core subroutines used to solve systems of linear equations (SLEs) encountered when solving an optimization problem. Standard floating-point algorithms are highly efficient but remain susceptible to the accumulation of round-off errors, which can lead solvers to return feasibility and optimality claims that are actually invalid. This paper introduces a novel direct solution approach for solving sequences of closely related SLEs encountered in nonlinear programming efficiently and without round-off errors. Specifically, it introduces rank-one update algorithms for the round-off error–free factorization framework, a tool set built on integer-preserving arithmetic that has led to the development and implementation of extremely reliable subroutines for solving SLEs occurring in linear programming. The formal guarantees of the presented algorithms are established through the derivation of theoretical insights. Their advantages are supported with computational experiments, which demonstrate upward of 75× improvements over exact factorization runtimes on fully dense matrices with more than one million entries. A significant advantage of the featured integer-preserving framework is that the length of any matrix coefficient produced by its algorithms is bounded polynomially in the size of the inputs without having to resort to greatest common divisor operations, which are required by and thereby hinder an efficient implementation of exact rational arithmetic approaches. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0331 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0331 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .