Randomized Projection Methods for Convex Feasibility: Conditioning and Convergence Rates

DOI10.1137/18M1167061zbMath1430.90463OpenAlexW2985739199WikidataQ126830335 ScholiaQ126830335MaRDI QIDQ5242933

Ion Necoara, Peter Richtárik, Andrei T. Patrascu

Publication date: 8 November 2019

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/18m1167061

zbMATH Keywords

convergence ratescondition numberconvex feasibilityrandomized projection methodsstochastic reformulations

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Stochastic programming (90C15)

Related Items (17)

A fully stochastic primal-dual algorithm ⋮ Stochastic quasi-subgradient method for stochastic quasi-convex feasibility problems ⋮ Stochastic block projection algorithms with extrapolation for convex feasibility problems ⋮ A Computational Framework for Solving Nonlinear Binary Optimization Problems in Robust Causal Inference ⋮ On the Convergence of Stochastic Primal-Dual Hybrid Gradient ⋮ The method of randomized Bregman projections for stochastic feasibility problems ⋮ Distributed algorithms for computing a fixed point of multi-agent nonexpansive operators ⋮ Worst-case complexity of cyclic coordinate descent: \(O(n^2)\) gap with randomized version ⋮ Randomized Extended Average Block Kaczmarz for Solving Least Squares ⋮ New nonasymptotic convergence rates of stochastic proximal point algorithm for stochastic convex optimization ⋮ General convergence analysis of stochastic first-order methods for composite optimization ⋮ Faster Randomized Block Kaczmarz Algorithms ⋮ On maximum residual block and two-step Gauss-Seidel algorithms for linear least-squares problems ⋮ Minibatch stochastic subgradient-based projection algorithms for feasibility problems with convex inequalities ⋮ Distributed optimization for degenerate loss functions arising from over-parameterization ⋮ Distributed constrained consensus for discrete multi-agent systems with additive noises ⋮ Linear Convergence of Random Dual Coordinate Descent on Nonpolyhedral Convex Problems

Uses Software

• ART3+

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Gradient methods for minimizing composite functions
• On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints
• Random algorithms for convex minimization problems
• Hilbertian convex feasibility problem: Convergence of projection methods
• The rate of convergence for the cyclic projections algorithm. I: Angles between convex sets
• A randomized Kaczmarz algorithm with exponential convergence
• Linear convergence of first order methods for non-strongly convex optimization
• A fast algorithm for solving a linear feasibility problem with application to intensity-modulated radiation therapy
• Extrapolation algorithm for affine-convex feasibility problems
• A Linearly Convergent Algorithm for Solving a Class of Nonconvex/Affine Feasibility Problems
• Weak Sharp Minima in Mathematical Programming
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• Randomized Iterative Methods for Linear Systems
• Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization
• Energy-based sensor network source localization via projection onto convex sets
• Convergence rate analysis and error bounds for projection algorithms in convex feasibility problems
• On Projection Algorithms for Solving Convex Feasibility Problems
• On cluster points of alternating projections
• The method of projections for finding the common point of convex sets
• Functional Operators (AM-22), Volume 2
• The Relaxation Method for Linear Inequalities
• Proximity function minimization using multiple Bregman projections, with applications to split feasibility and Kullback--Leibler distance minimization

This page was built for publication: Randomized Projection Methods for Convex Feasibility: Conditioning and Convergence Rates