Exact Matrix Factorization Updates for Nonlinear Programming

DOI10.1287/IJOC.2021.0331arXiv2202.00520OpenAlexW4386482574MaRDI QIDQ6202346FDOQ6202346

Authors: Adolfo R. Escobedo 

Publication date: 26 March 2024

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Abstract: LU and Cholesky matrix factorization algorithms are core subroutines used to solve systems of linear equations (SLEs) encountered while solving an optimization problem. Standard factorization algorithms are highly efficient but remain susceptible to the accumulation of roundoff errors, which can lead solvers to return feasibility and optimality claims that are actually invalid. This paper introduces a novel approach for solving sequences of closely related SLEs encountered in nonlinear programming efficiently and without roundoff errors. Specifically, it introduces rank-one update algorithms for the roundoff-error-free (REF) factorization framework, a toolset built on integer-preserving arithmetic that has led to the development and implementation of fail-proof SLE solution subroutines for linear programming. The formal guarantees of the proposed algorithms are established through the derivation of theoretical insights. Their advantages are supported with computational experiments, which demonstrate upwards of 75x-improvements over exact factorization run-times on fully dense matrices with over one million entries. A significant advantage of the methodology is that the length of any coefficient calculated via the proposed 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.

Full work available at URL: https://arxiv.org/abs/2202.00520

Recommendations

• Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates
• Roundoff-error-free algorithms for solving linear systems via Cholesky and LU factorizations
• Solution of dense linear systems via roundoff-error-free factorization algorithms. Theoretical connections and computational comparisons
• Exactly solving sparse rational linear systems via roundoff-error-free Cholesky factorizations
• Exact solution of sparse linear systems via left-looking roundoff-error-free Lu factorization in time proportional to arithmetic work

zbMATH Keywords

nonlinear optimizationmatrix factorizationsexact mathematical programminglow-rank modifications

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

This page was built for publication: Exact Matrix Factorization Updates for Nonlinear Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202346)