On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints

DOI10.1007/S10589-011-9401-7zbMath1244.90155arXiv0912.4367OpenAlexW2066333552MaRDI QIDQ429491

Gabor T. Herman, Ran Davidi, Yair Censor, Patrick L. Combettes, Wei Chen

Publication date: 19 June 2012

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0912.4367

zbMATH Keywords

optimizationsparse matricesprojection methodslinear inequalitiesnumerical evaluationconvex feasibility problems

Mathematics Subject Classification ID

Linear programming (90C05)

Related Items (65)

Finding a best approximation pair of points for two polyhedra ⋮ Hybrid projection methods for equilibrium problems with non‐Lipschitz type bifunctions ⋮ New subgradient extragradient methods for common solutions to equilibrium problems ⋮ Fundamentals of cone regression ⋮ Common Solutions to Variational Inequality Problem via Parallel and Cyclic Hybrid Inertial CQ-Subgradient Extragradient Algorithms in (HSs) ⋮ Conic optimization via operator splitting and homogeneous self-dual embedding ⋮ Feasibility-based fixed point networks ⋮ A non-interior continuation algorithm for solving the convex feasibility problem ⋮ Weak and strong convergence adaptive algorithms for generalized split common fixed point problems ⋮ Projection methods: an annotated bibliography of books and reviews ⋮ Strong convergence theorem for common zero points of inverse strongly monotone mappings and common fixed points of generalized demimetric mappings ⋮ Stochastic block projection algorithms with extrapolation for convex feasibility problems ⋮ A proximal point algorithm based on decomposition method for cone constrained multiobjective optimization problems ⋮ Cyclic subgradient extragradient methods for equilibrium problems ⋮ An asynchronous inertial algorithm for solving convex feasibility problems with strict pseudo-contractions in Hilbert spaces ⋮ Single-projection procedure for linear optimization ⋮ A new self-adaptive accelerated method for generalized split system of common fixed-point problem of averaged mappings ⋮ On the convergence of general projection methods for solving convex feasibility problems with applications to the inverse problem of image recovery ⋮ Split equality monotone variational inclusions and fixed point problem of set-valued operator ⋮ A real-time iterative projection scheme for solving the common fixed point problem and its applications ⋮ Parallel and cyclic hybrid subgradient extragradient methods for variational inequalities ⋮ Optimization of triangular networks with spatial constraints ⋮ The optimal error bound for the method of simultaneous projections ⋮ Can linear superiorization be useful for linear optimization problems? ⋮ Bounded perturbation resilience and superiorization techniques for the projected scaled gradient method ⋮ Computerized tomography with total variation and with shearlets ⋮ Speedup of lexicographic optimization by superiorization and its applications to cancer radiotherapy treatment ⋮ Distance majorization and its applications ⋮ Asynchronous sequential inertial iterations for common fixed points problems with an application to linear systems ⋮ Convergence and perturbation resilience of dynamic string-averaging projection methods ⋮ Bounded perturbation resilience and superiorization techniques for a modified proximal gradient method ⋮ Split common fixed point problem for demimetric mappings and Bregman relatively nonexpansive mappings ⋮ Inertial self-adaptive parallel extragradient-type method for common solution of variational inequality problems ⋮ How good are extrapolated bi-projection methods for linear feasibility problems? ⋮ Convex feasibility modeling and projection methods for sparse signal recovery ⋮ Unnamed Item ⋮ Common solutions to variational inequalities ⋮ Algorithms for the split variational inequality problem ⋮ Choosing the relaxation parameter in sequential block-iterativemethods for linear systems ⋮ A strongly polynomial-time algorithm for the strict homogeneous linear-inequality feasibility problem ⋮ A relaxed projection method for split variational inequalities ⋮ Zero-convex functions, perturbation resilience, and subgradient projections for feasibility-seeking methods ⋮ On the existence of minimizers of proximity functions for split feasibility problems ⋮ A novel low-cost method for generalized split inverse problem of finite family of demimetric mappings ⋮ An explicit algorithm for solving monotone variational inequalities ⋮ General alternative regularization methods for split equality common fixed-point problem ⋮ New nonasymptotic convergence rates of stochastic proximal point algorithm for stochastic convex optimization ⋮ Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization ⋮ Projected subgradient minimization versus superiorization ⋮ A new modified hybrid steepest-descent by using a viscosity approximation method with a weakly contractive mapping for a system of equilibrium problems and fixed point problems with minimization problems ⋮ On the Finite Convergence of the Douglas--Rachford Algorithm for Solving (Not Necessarily Convex) Feasibility Problems in Euclidean Spaces ⋮ String-averaging projected subgradient methods for constrained minimization ⋮ Tomography ⋮ A generalized projection-based scheme for solving convex constrained optimization problems ⋮ Faster Randomized Block Kaczmarz Algorithms ⋮ Reconstruction of functions from prescribed proximal points ⋮ On the method of reflections ⋮ Unnamed Item ⋮ A stochastic approximation method for approximating the efficient frontier of chance-constrained nonlinear programs ⋮ Strong convergence of over-relaxed multi-parameter proximal scaled gradient algorithm and superiorization ⋮ Dykstra's splitting and an approximate proximal point algorithm for minimizing the sum of convex functions ⋮ The hybrid projection algorithm for finding the common fixed points of nonexpansive mappings and the zeroes of maximal monotone operators in Banach spaces ⋮ Randomized Projection Methods for Convex Feasibility: Conditioning and Convergence Rates ⋮ Shrinking extragradient method for pseudomonotone equilibrium problems and quasi-nonexpansive mappings ⋮ Strict Fejér monotonicity by superiorization of feasibility-seeking projection methods

Uses Software

• Mosek
• SNARK09
• SNARK93
• TwIST
• ART3+

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monotone Gram matrices and deepest surrogate inequalities in accelerated relaxation methods for convex feasibility problems
• Hilbertian convex feasibility problem: Convergence of projection methods
• Strong convergence of projection-like methods in Hilbert spaces
• Iterative algorithms for large partitioned linear systems, with applications to image reconstruction
• Projection and proximal point methods: Convergence results and counterexamples.
• Block-iterative projection methods for parallel computation of solutions to convex feasibility problems
• The approximation of fixed points of compositions of nonexpansive mappings in Hilbert space
• How good are projection methods for convex feasibility problems?
• A fast algorithm for solving a linear feasibility problem with application to intensity-modulated radiation therapy
• Extrapolation algorithm for affine-convex feasibility problems
• Mathematical Methods in Image Reconstruction
• Fundamentals of Computerized Tomography
• Efficient controls for finitely convergent sequential algorithms
• The Split Bregman Method for L1-Regularized Problems
• On the behavior of a block-iterative projection method for solving convex feasibility problems
• General Projective Splitting Methods for Sums of Maximal Monotone Operators
• On the string averaging method for sparse common fixed‐point problems
• Perturbation‐resilient block‐iterative projection methods with application to image reconstruction from projections
• Perturbation resilience and superiorization of iterative algorithms
• A discrete spherical x-ray transform of orientation distribution functions using bounding cubes
• Decomposition through formalization in a product space
• On the use of Cimmino's simultaneous projections method for computing a solution of the inverse problem in radiation therapy treatment planning
• Row-Action Methods for Huge and Sparse Systems and Their Applications
• On solving linear complementarity problems as linear programs
• Surrogate Projection Methods for Finding Fixed Points of Firmly Nonexpansive Mappings
• Accelerating the convergence of the method of alternating projections
• Fast image recovery using dynamic load balancing in parallel architectures, by means of incomplete projections
• Energy-based sensor network source localization via projection onto convex sets
• Pairwise Optimal Weight Realization—Acceleration Technique for Set-Theoretic Adaptive Parallel Subgradient Projection Algorithm
• Convergence of String-Averaging Projection Schemes for Inconsistent Convex Feasibility Problems
• On Projection Algorithms for Solving Convex Feasibility Problems
• Demosaicking by Alternating Projections: Theory and Fast One-Step Implementation
• The method of projections for finding the common point of convex sets
• A Weak-to-Strong Convergence Principle for Fejér-Monotone Methods in Hilbert Spaces
• On a relaxation method of solving systems of linear inequalities
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities
• Best approximation in inner product spaces
• Inherently parallel algorithms in feasibility and optimization and their applications. Research workshop, Haifa, Israel, March 13--16, 2000

This page was built for publication: On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints