Robust linear algebra

Dimitris Bertsimas and Thodoris Koukouvinos

European Journal of Operational Research, 2024, vol. 314, issue 3, 1174-1184

Abstract: We propose a robust optimization (RO) framework that immunizes some of the central linear algebra problems in the presence of data uncertainty. Namely, we formulate linear systems, matrix inversion, eigenvalues–eigenvectors and matrix factorization under uncertainty, as robust optimization problems using appropriate descriptions of uncertainty. The resulting optimization problems are computationally tractable and scalable. We show in theory that RO improves the relative error of the linear system by reducing the condition number of the underlying matrix. Moreover, we provide empirical evidence showing that the proposed approach outperforms state of the art methods for linear systems and matrix inversion, when applied on ill-conditioned matrices. We show that computing eigenvalues–eigenvectors under RO, corresponds to solving linear systems that are better conditioned than the nominal and illustrate with numerical experiments that the proposed approach is more accurate than the nominal, when perturbing ill-conditioned matrices. Finally, we demonstrate empirically the benefit of the robust Cholesky factorization over the nominal.

Keywords: Robustness and sensitivity analysis; Linear systems; Matrix inversion; Eigenvalues; Choleksy (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723008779
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:314:y:2024:i:3:p:1174-1184

DOI: 10.1016/j.ejor.2023.11.036

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().