Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
From MaRDI portal
Publication:2176283
DOI10.1007/S10898-019-00850-6zbMATH Open1442.90123arXiv1902.03502OpenAlexW3100892251WikidataQ126984751 ScholiaQ126984751MaRDI QIDQ2176283FDOQ2176283
Authors: Md Sarowar Morshed, Md Saiful Islam, Md. Noor-E-Alam 
Publication date: 4 May 2020
Published in: Journal of Global Optimization (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1902.03502
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
Convex programming (90C25) Linear programming (90C05) Randomized algorithms (68W20) Iterative numerical methods for linear systems (65F10) Linear inequalities of matrices (15A39)
Cites Work
- A randomized Kaczmarz algorithm with exponential convergence
- Fundamentals of Computerized Tomography
- Smooth minimization of non-smooth functions
- Title not available (Why is that?)
- Gradient methods for minimizing composite functions
- A Newton-CG augmented Lagrangian method for semidefinite programming
- Faster least squares approximation
- Row-Action Methods for Huge and Sparse Systems and Their Applications
- An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Randomized methods for linear constraints: convergence rates and conditioning
- The Relaxation Method for Linear Inequalities
- The Relaxation Method for Linear Inequalities
- Inexact Newton Methods
- Choosing the Forcing Terms in an Inexact Newton Method
- Inexact interior-point method
- Convergence analysis of an inexact feasible interior point method for convex quadratic programming
- Randomized extended Kaczmarz for solving least squares
- Single projection Kaczmarz extended algorithms
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- Randomized Kaczmarz solver for noisy linear systems
- An inexact accelerated proximal gradient method and a dual Newton-CG method for the maximal entropy problem
- Generalized affine scaling algorithms for linear programming problems
- Title not available (Why is that?)
- An accelerated randomized Kaczmarz algorithm
- Optimization models
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- Towards a deeper geometric, analytic and algorithmic understanding of margins
Cited In (15)
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- A class of pseudoinverse-free greedy block nonlinear Kaczmarz methods for nonlinear systems of equations
- Quantile-based iterative methods for corrupted systems of linear equations
- A randomized block Douglas-Rachford method for solving linear matrix equation
- On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations
- On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
- Hildreth's algorithm with applications to soft constraints for user interface layout
- Efficient randomized block Kaczmarz method for linear feasibility
- On sampling Kaczmarz-Motzkin methods for solving large-scale nonlinear systems
- RidgeSketch: a fast sketching based solver for large scale ridge regression
- Splitting-based randomized iterative methods for solving indefinite least squares problem
- Block sampling Kaczmarz-Motzkin methods for consistent linear systems
- Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
Uses Software
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)
