The Relaxation Method for Solving Systems of Linear Inequalities
From MaRDI portal
Publication:3885509
DOI10.1287/moor.5.3.388zbMath0442.90051DBLPjournals/mor/Goffin80OpenAlexW2170166494WikidataQ29304815 ScholiaQ29304815MaRDI QIDQ3885509
Publication date: 1980
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.5.3.388
relaxation methodfinite convergencesystems of linear inequalitiessubgradient optimizationobtuse polyhedrarate of geometric convergence
Linear programming (90C05) Iterative numerical methods for linear systems (65F10) Rate of convergence, degree of approximation (41A25) Polytopes and polyhedra (52Bxx)
Related Items (64)
Computational relaxation method for modeling electrostatic systems with non-trivial geometries ⋮ About geometrical convergence of general iterative methods applied to nonunique solvable convex problems. II ⋮ About geometrical convergence of general iterative methods applied to nonunique solvable convex problems. I ⋮ Block-iterative surrogate projection methods for convex feasibility problems ⋮ The MIN PFS problem and piecewise linear model estimation ⋮ Geometrically convergent projection method in matrix games ⋮ Rescaled Coordinate Descent Methods for Linear Programming ⋮ Error estimates and Lipschitz constants for best approximation in continuous function spaces ⋮ Primal-dual row-action method for convex programming ⋮ On some optimization techniques in image reconstruction from projections ⋮ Central axes and peripheral points in high dimensional directional datasets ⋮ Fixed points of polarity type operators ⋮ Nonnegative Moore--Penrose inverses of Gram operators ⋮ Measuring centrality and dispersion in directional datasets: the ellipsoidal cone covering approach ⋮ On the behavior of a block-iterative projection method for solving convex feasibility problems ⋮ Inradius and circumradius of various convex cones arising in applications ⋮ On Chubanov's Method for Linear Programming ⋮ Asymptotics for some proximal-like method involving inertia and memory aspects ⋮ Rescaling Algorithms for Linear Conic Feasibility ⋮ A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility ⋮ A conjugate gradient algorithm for sparse linear inequalities ⋮ Finite convergence of a subgradient projections method with expanding controls ⋮ A condition-based algorithm for solving polyhedral feasibility problems ⋮ On highly eccentric cones ⋮ Some preconditioners for systems of linear inequalities ⋮ Robust smoothed analysis of a condition number for linear programming ⋮ Convergence studies on block iterative algorithms for image reconstruction ⋮ Monotone Gram matrices and deepest surrogate inequalities in accelerated relaxation methods for convex feasibility problems ⋮ A simple polynomial-time rescaling algorithm for solving linear programs ⋮ Normality and modulability indices. I: Convex cones in normed spaces ⋮ Coverage processes on spheres and condition numbers for linear programming ⋮ A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF ⋮ Convergence of the cyclical relaxation method for linear inequalities ⋮ Reflection-projection method for convex feasibility problems with an obtuse cone ⋮ Piecewise linear retractions by reflexion ⋮ On properties of different notions of centers for convex cones ⋮ Obtuse cones and Gram matrices with non-negative inverse ⋮ On the von Neumann and Frank--Wolfe Algorithms with Away Steps ⋮ Partial inverse of a monotone operator ⋮ The Kaczmarz algorithm, row action methods, and statistical learning algorithms ⋮ Conic version of Loewner-John ellipsoid theorem ⋮ A deterministic rescaled perceptron algorithm ⋮ A Data-Independent Distance to Infeasibility for Linear Conic Systems ⋮ Unnamed Item ⋮ Extending linear relaxation for non-square matrices and soft constraints ⋮ The sharp Lipschitz constants for feasible and optimal solutions of a perturbed linear program ⋮ Towards a deeper geometric, analytic and algorithmic understanding of margins ⋮ A polynomial projection algorithm for linear feasibility problems ⋮ Linear Convergence of Projection Algorithms ⋮ On the convergence properties of Hildreth's quadratic programming algorithm ⋮ Relaxed outer projections, weighted averages and convex feasibility ⋮ A class of methods for solving large convex systems ⋮ On strata of degenerate polyhedral cones. I: Condition and distance to strata ⋮ A projection method for least-squares solutions to overdetermined systems of linear inequalities ⋮ Conditioning of random conic systems under a general family of input distributions ⋮ Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin ⋮ On the non-polynomiality of the relaxation method for systems of linear inequalities ⋮ A primal-dual projection method for solving systems of linear inequalities ⋮ An automatic relaxation method for solving interval linear inequalities ⋮ Variable metric relaxation methods, part II: The ellipsoid method ⋮ Projection and Rescaling Algorithm for Finding Maximum Support Solutions to Polyhedral Conic Systems ⋮ Hildreth's algorithm with applications to soft constraints for user interface layout ⋮ A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix ⋮ Surrogate methods for linear inequalities
This page was built for publication: The Relaxation Method for Solving Systems of Linear Inequalities
