Stable modification of explicit LU factors for simplex updates
This paper presents a method for modifying an LU factorization of a matrix A when a simplex update is performed on A. At each stage of the algorithm, two options are allowed, and in one of these a row permutation of L is made so that the LU structure is always maintained. The expanding file of operators used in other methods is not required. The result of an error analysis is presented in which the error is bounded by the growth in the partial sums of LU. Various pivotal strategies which minimize a growth bound are discussed and an example is given in which the worst case for growth occurs repeatedly. Numerical results from experiments on ill-conditioned problems show no tendency for error growth.
- An efficient simplex LU factorization update
- An efficient approach to updating simplex multipliers in the simplex algorithm
- On the efficient update of rectangular LU-factorizations subject to low rank modifications
- A fast LU update for linear programming
- Stable algorithm for updating denseLUfactorization after row or column exchange and row and column addition or deletion
- scientific article; zbMATH DE number 3852785
- Novel update techniques for the revised simplex method
- A Stable Algorithm for Updating Triangular Factors Under a Rank One Change
- A numerically stable form of the simplex algorithm
- A stabilization of the simplex method
- A Stable Algorithm for Updating Triangular Factors Under a Rank One Change
- scientific article; zbMATH DE number 3744430 (Why is no real title available?)
- scientific article; zbMATH DE number 3538745 (Why is no real title available?)
- scientific article; zbMATH DE number 3408799 (Why is no real title available?)
- Large-scale linear programming: Geometry, working bases and factorizations
- The elimination form of the inverse and its application to linear programming
- The simplex method of linear programming using LU decomposition
- Triangular factors of modified matrices
- Updated triangular factors of the basis of maintain sparsity in the product form simplex method
- On error growth in the Bartels-Golub and Fletcher-Matthews algorithms for updating matrix factorizations
- Degeneracy in the presence of roundoff errors
- On the use of dense matrix techniques within sparse simplex
- Sensitivity method for basis inverse representation in multistage stochastic linear programming problems
- A splitting-free vorticity redistribution method
- A reduced proximal-point homotopy method for large-scale non-convex BQP
- A pivoting algorithm for linear programming with linear complementarity constraints
- A Stable Algorithm for Updating Triangular Factors Under a Rank One Change
- An efficient simplex LU factorization update
- Updating LU Factorizations for Computing Stationary Distributions
- scientific article; zbMATH DE number 3980363 (Why is no real title available?)
- Stable algorithm for updating denseLUfactorization after row or column exchange and row and column addition or deletion
- qpOASES: a parametric active-set algorithm for~quadratic programming
- Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates
- A simplex method algorithm using a double basis
- The greedy simplex algorithm for double sparsity constrained optimization problems
- An efficient approach to updating simplex multipliers in the simplex algorithm
This page was built for publication: Stable modification of explicit LU factors for simplex updates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3692731)