Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
From MaRDI portal
Publication:2176283
Abstract: The Sampling Kaczmarz Motzkin (SKM) algorithm is a generalized method for solving large scale linear systems of inequalities. Having its root in the relaxation method of Agmon, Schoenberg, and Motzkin and the randomized Kaczmarz method, SKM outperforms the state of the art methods in solving large-scale Linear Feasibility (LF) problems. Motivated by SKM's success, in this work, we propose an Accelerated Sampling Kaczmarz Motzkin (ASKM) algorithm which achieves better convergence compared to the standard SKM algorithm on ill conditioned problems. We provide a thorough convergence analysis for the proposed accelerated algorithm and validate the results with various numerical experiments. We compare the performance and effectiveness of ASKM algorithm with SKM, Interior Point Method (IPM) and Active Set Method (ASM) on randomly generated instances as well as Netlib LPs. In most of the test instances, the proposed ASKM algorithm outperforms the other state of the art methods.
Recommendations
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- An accelerated randomized Kaczmarz algorithm
- A greedy block Kaczmarz algorithm for solving large-scale linear systems
- Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
Cites work
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 1943822 (Why is no real title available?)
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A randomized Kaczmarz algorithm with exponential convergence
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- An accelerated randomized Kaczmarz algorithm
- An inexact accelerated proximal gradient method and a dual Newton-CG method for the maximal entropy problem
- An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP
- Choosing the Forcing Terms in an Inexact Newton Method
- Convergence analysis of an inexact feasible interior point method for convex quadratic programming
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Faster least squares approximation
- Fundamentals of Computerized Tomography
- Generalized affine scaling algorithms for linear programming problems
- Gradient methods for minimizing composite functions
- Inexact Newton Methods
- Inexact interior-point method
- Optimization models
- Randomized Kaczmarz solver for noisy linear systems
- Randomized extended Kaczmarz for solving least squares
- Randomized methods for linear constraints: convergence rates and conditioning
- Row-Action Methods for Huge and Sparse Systems and Their Applications
- Single projection Kaczmarz extended algorithms
- Smooth minimization of non-smooth functions
- The Relaxation Method for Linear Inequalities
- The Relaxation Method for Linear Inequalities
- Towards a deeper geometric, analytic and algorithmic understanding of margins
Cited in
(15)- A randomized block Douglas-Rachford method for solving linear matrix equation
- Quantile-based iterative methods for corrupted systems of linear equations
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
- On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations
- Block sampling Kaczmarz-Motzkin methods for consistent linear systems
- On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations
- RidgeSketch: a fast sketching based solver for large scale ridge regression
- Splitting-based randomized iterative methods for solving indefinite least squares problem
- Hildreth's algorithm with applications to soft constraints for user interface layout
- A class of pseudoinverse-free greedy block nonlinear Kaczmarz methods for nonlinear systems of equations
- Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- On sampling Kaczmarz-Motzkin methods for solving large-scale nonlinear systems
- Efficient randomized block Kaczmarz method for linear feasibility
This page was built for publication: Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2176283)
