2021/01/27 by Wim Vanroose, Vanroose, Wim, J. Cornelis +1
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Numerical Methods and Algorithms #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2101.11416
openalex publication_date 2021/01/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The paper presents two variants of a Krylov-Simplex iterative method that combines Krylov and simplex iterations to minimize the residual r = b-Ax. The first method minimizes ‖r‖_∞, i.e. maximum of the absolute residuals. The second minimizes ‖r‖1, and finds the solution with the least absolute residuals. Both methods search for an optimal solution xk in a Krylov subspace which results in a small linear programming problem. A specialized simplex algorithm solves this projected problem and finds the optimal linear combination of Krylov basis vectors to approximate the solution. The resulting simplex algorithm requires the solution of a series of small dense linear systems that only differ by rank-one updates. The QR factorization of these matrices is updated each iteration. We demonstrate the effectiveness of the methods with numerical experiments.