The Relaxation Method for Solving Systems of Linear Inequalities

J. L. Goffin
J. L. Goffin
McGill University, Faculty of Management, 1001 Sherbrooke Street West, Montreal, Quebec, Canada H3A 1G5
Search for more papers by this author

McGill University, Faculty of Management, 1001 Sherbrooke Street West, Montreal, Quebec, Canada H3A 1G5

Published Online:1 Aug 1980https://doi.org/10.1287/moor.5.3.388

Abstract

The relaxation method for solving systems of inequalities is related both to subgradient optimization and to the relaxation methods used in numerical analysis.

The convergence theory depends upon two condition numbers. The first one is used mostly for the study of the rate of geometric convergence. The second is used to define a range of values of the relaxation parameter which guarantees finite convergence. In the case of obtuse polyhedra, finite convergence occurs for any value of the relaxation parameter between one and two.

Various relationships between the condition numbers and the concept of obtuseness are established.

Cited by
- Computational guarantees for restarted PDHG for LP based on “Limiting Error Ratios” and LP sharpness
  26 May 2026 | Mathematical Programming, Vol. 169
- Condition number of a convex cone
  5 August 2024 | Beiträge zur Algebra und Geometrie / Contributions to Algebra and Geometry, Vol. 66, No. 3
- A Greedy Fixed-Point Method for Solving Variational Inequalities over the Fixed-Point Constraints
  20 March 2025 | Numerical Functional Analysis and Optimization, Vol. 46, No. 6
- Efficient randomized block Kaczmarz method for linear feasibility
  7 December 2024 | Calcolo, Vol. 62, No. 1
- A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
  29 April 2023 | Mathematical Programming, Vol. 204, No. 1-2
- Projection and Rescaling Algorithm for Finding Maximum Support Solutions to Polyhedral Conic Systems
  Javier Peña,
  Negar Soheili
  16 February 2022 | Mathematics of Operations Research, Vol. 47, No. 4
- Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
  1 March 2021 | SIAM Journal on Mathematics of Data Science, Vol. 3, No. 1
- A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
  22 June 2020
- Rescaling Algorithms for Linear Conic Feasibility
  Daniel Dadush,
  László A. Végh,
  Giacomo Zambelli
  23 January 2020 | Mathematics of Operations Research, Vol. 45, No. 2
- Computational relaxation method for modeling electrostatic systems with non-trivial geometries
  12 February 2020 | European Journal of Physics, Vol. 41, No. 2
- On-Line Relaxation Versus Off-Line Spectral Algorithm in the Learning of Polynomial Neural Units
  5 November 2020
- A Data-Independent Distance to Infeasibility for Linear Conic Systems
  2 April 2020 | SIAM Journal on Optimization, Vol. 30, No. 2
- Linear Convergence of Projection Algorithms
  Minh N. Dao,
  Hung M. Phan
  19 April 2019 | Mathematics of Operations Research, Vol. 44, No. 2
- Fixed points of polarity type operators
  Journal of Mathematical Analysis and Applications, Vol. 467, No. 2
- Parallel Method of Pseudoprojection for Linear Inequalities
  26 August 2018
- Optimal geospatial volunteer allocation needs realistic distances
- Constraints reordering to speed up successive over-relaxation for constraint-based user interface layouts
- Nonlinearity and solution techniques in reservoir simulation: A review
  Journal of Natural Gas Science and Engineering, Vol. 46
- Measuring centrality and dispersion in directional datasets: the ellipsoidal cone covering approach
  19 September 2016 | Journal of Global Optimization, Vol. 68, No. 2
- A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility
  SIAM Journal on Scientific Computing, Vol. 39, No. 5
- Extending linear relaxation for non-square matrices and soft constraints
  Journal of Computational and Applied Mathematics, Vol. 308
- Central axes and peripheral points in high dimensional directional datasets
  20 January 2015 | Computational Optimization and Applications, Vol. 65, No. 2
- Towards a deeper geometric, analytic and algorithmic understanding of margins
  13 November 2015 | Optimization Methods and Software, Vol. 31, No. 2
- Rescaled Coordinate Descent Methods for Linear Programming
  25 May 2016
- Conic version of Loewner–John ellipsoid theorem
  14 December 2014 | Mathematical Programming, Vol. 155, No. 1-2
- A deterministic rescaled perceptron algorithm
  17 January 2015 | Mathematical Programming, Vol. 155, No. 1-2
- Convergence studies on block iterative algorithms for image reconstruction
  Applied Mathematics and Computation, Vol. 273
- On the von Neumann and Frank--Wolfe Algorithms with Away Steps
  SIAM Journal on Optimization, Vol. 26, No. 1
- A polynomial projection algorithm for linear feasibility problems
  8 October 2014 | Mathematical Programming, Vol. 153, No. 2
- Hildreth’s algorithm with applications to soft constraints for user interface layout
  Journal of Computational and Applied Mathematics, Vol. 288
- From cutting planes algorithms to compression schemes and active learning
- A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF
  27 February 2015 | Forum of Mathematics, Sigma, Vol. 3
- A condition-based algorithm for solving polyhedral feasibility problems
  Journal of Complexity, Vol. 30, No. 6
- Some preconditioners for systems of linear inequalities
  9 January 2014 | Optimization Letters, Vol. 8, No. 7
- On highly eccentric cones
  22 October 2013 | Beiträge zur Algebra und Geometrie / Contributions to Algebra and Geometry, Vol. 55, No. 2
- On Chubanov's Method for Linear Programming
  Amitabh Basu,
  Jesús A. De Loera,
  Mark Junod
  3 December 2013 | INFORMS Journal on Computing, Vol. 26, No. 2
- Extending Linear Relaxation for User Interface Layout
- A Novel Subblock Linear Combination Scheme for Peak-to-Average Power Ratio Reduction in OFDM Systems
  IEEE Transactions on Broadcasting, Vol. 58, No. 3
- A Scalable Algorithm to Explore the Gibbs Energy Landscape of Genome-Scale Metabolic Networks
  21 June 2012 | PLoS Computational Biology, Vol. 8, No. 6
- Robust smoothed analysis of a condition number for linear programming
  21 April 2010 | Mathematical Programming, Vol. 131, No. 1-2
- Introduction
  16 July 2012
- Algorithmic Operators
  16 July 2012
- Convergence of Iterative Methods
  16 July 2012
- Algorithmic Projection Operators
  16 July 2012
- Projection Methods
  16 July 2012
- A Coordinate-Free Condition Number for Convex Programming
  SIAM Journal on Optimization, Vol. 22, No. 3
- A Smooth Perceptron Algorithm
  SIAM Journal on Optimization, Vol. 22, No. 2
- Finite Convergence of a Subgradient Projections Method with Expanding Controls
  8 June 2011 | Applied Mathematics & Optimization, Vol. 64, No. 2
- Zhang dynamics solving scalar-valued time-varying linear inequalities using different activation functions
- Asymptotics for Some Proximal-like Method Involving Inertia and Memory Aspects
  11 June 2010 | Set-Valued and Variational Analysis, Vol. 19, No. 1
- Inradius and Circumradius of Various Convex Cones Arising in Applications
  25 August 2010 | Set-Valued and Variational Analysis, Vol. 18, No. 3-4
- Random projection algorithms for convex set intersection problems
- On Properties of Different Notions of Centers for Convex Cones
  30 December 2009 | Set-Valued and Variational Analysis, Vol. 18, No. 2
- Coverage processes on spheres and condition numbers for linear programming
  The Annals of Probability, Vol. 38, No. 2
- On strata of degenerate polyhedral cones I: Condition and distance to strata
  European Journal of Operational Research, Vol. 198, No. 1
- Conditioning of Random Conic Systems Under a General Family of Input Distributions
  23 August 2008 | Foundations of Computational Mathematics, Vol. 9, No. 3
- A simple polynomial-time rescaling algorithm for solving linear programs
  27 February 2007 | Mathematical Programming, Vol. 114, No. 1
- Normality and modulability indices. Part I: Convex cones in normed spaces
  Journal of Mathematical Analysis and Applications, Vol. 338, No. 1
- A Condition Number for Multifold Conic Systems
  SIAM Journal on Optimization, Vol. 19, No. 1
- Nonnegative Moore–Penrose inverses of Gram operators
  Linear Algebra and its Applications, Vol. 422, No. 2-3
- Projective Pre-Conditioners for Improving the Behavior of a Homogeneous Conic Linear System
  SSRN Electronic Journal, Vol. 17
- Boundedness Theorems for the Relaxation Method
  Edoardo Amaldi,
  Raphael Hauser,
  1 November 2005 | Mathematics of Operations Research, Vol. 30, No. 4
- On an Extension of Condition Number Theory to Nonconic Convex Optimization
  Robert M. Freund,
  Fernando Ordóñez,
  1 February 2005 | Mathematics of Operations Research, Vol. 30, No. 1
- Randomized Relaxation Methods for the Maximum Feasible Subsystem Problem
- Tail Decay and Moment Estimates of a Condition Number for Random Linear Conic Systems
  SIAM Journal on Optimization, Vol. 15, No. 4
- Reflection-Projection Method for Convex Feasibility Problems with an Obtuse Cone
  Journal of Optimization Theory and Applications, Vol. 120, No. 3
- On the Primal-Dual Geometry of Level Sets in Linear and Conic Optimization
  SIAM Journal on Optimization, Vol. 13, No. 4
- On an Extension of Condition Number Theory to Non-Conic Convex Optimization
  SSRN Electronic Journal, Vol. 12
- The MIN PFS problem and piecewise linear model estimation
  Discrete Applied Mathematics, Vol. 118, No. 1-2
- Obtuse cones and Gram matrices with nonnegative inverse
  Linear Algebra and its Applications, Vol. 335, No. 1-3
- Convergence Rate of Incremental Subgradient Algorithms
- Incomplete projection algorithms for solving the convex feasibility problem
  Numerical Algorithms, Vol. 18, No. 2
- Monotone gram matrices and deepest surrogate inequalities in accelerated relaxation methods for convex feasibility problems
  Linear Algebra and its Applications, Vol. 252, No. 1-3
- A Unified Analysis of Hoffman’s Bound via Fenchel Duality
  SIAM Journal on Optimization, Vol. 6, No. 2
- Error estimates and Lipschitz constants for best approximation in continuous function spaces
  Computers & Mathematics with Applications, Vol. 30, No. 3-6
- Primal-dual row-action method for convex programming
  Journal of Optimization Theory and Applications, Vol. 86, No. 1
- Geometrically convergent projection method in matrix games
  Journal of Optimization Theory and Applications, Vol. 85, No. 2
- Approximations to Solutions to Systems of Linear Inequalities
  SIAM Journal on Matrix Analysis and Applications, Vol. 16, No. 2
- Block-iterative surrogate projection methods for convex feasibility problems
  Linear Algebra and its Applications, Vol. 215
- About geometrical convergence of general iterative methods applied to nonunique solvable convex problems, Part II
  Journal of Computational and Applied Mathematics, Vol. 54, No. 2
- About geometrical convergence of general iterative methods applied to nonunique solvable convex problems, Part I
  Journal of Computational and Applied Mathematics, Vol. 54, No. 1
- Exposing Constraints
  SIAM Journal on Optimization, Vol. 4, No. 3
- Perturbation Analysis of a Condition Number for Linear Systems
  SIAM Journal on Matrix Analysis and Applications, Vol. 15, No. 2
- On the Complexity of a Column Generation Algorithm for Convex or Quasiconvex Feasibility Problems
- Projection onto an acute cone and convex feasibility problem
  23 June 2005
- Sharp Lipschitz Constants for Basic Optimal Solutions and Basic Feasible Solutions of Linear Programs
  SIAM Journal on Control and Optimization, Vol. 32, No. 1
- The sharp Lipschitz constants for feasible and optimal solutions of a perturbed linear program
  Linear Algebra and its Applications, Vol. 187
- The foundations of set theoretic estimation
  Proceedings of the IEEE, Vol. 81, No. 2
- A Convergence Acceleration of the Relaxation Algorithm in Convex Minimization
- On the Convergence of the Products of Firmly Nonexpansive Mappings
  SIAM Journal on Optimization, Vol. 2, No. 3
- Surrogate methods for linear inequalities
  Journal of Optimization Theory and Applications, Vol. 72, No. 2
- A conjugate gradient algorithm for sparse linear inequalities
  Journal of Computational and Applied Mathematics, Vol. 30, No. 3
- Relaxed outer projections, weighted averages and convex feasibility
  BIT, Vol. 30, No. 2
- On the convergence properties of Hildreth's quadratic programming algorithm
  Mathematical Programming, Vol. 47, No. 1-3
- A class of methods for solving large convex systems
  Operations Research Letters, Vol. 9, No. 3
- Cellular neural networks: Dynamic properties and adaptive learning algorithm
  8 June 2005
- On the behavior of a block-iterative projection method for solving convex feasibility problems
  International Journal of Computer Mathematics, Vol. 34, No. 1-2
- Neural network design using linear programming and relaxation
- On some optimization techniques in image reconstruction from projections
  Applied Numerical Mathematics, Vol. 3, No. 5
- A projection method for least-squares solutions to overdetermined systems of linear inequalities
  Linear Algebra and its Applications, Vol. 86
- A primal-dual projection method for solving systems of linear inequalities
  Linear Algebra and its Applications, Vol. 65
- Variable metric relaxation methods, part II: The ellipsoid method
  Mathematical Programming, Vol. 30, No. 2
- Convergence of the cyclical relaxation method for linear inequalities
  Mathematical Programming, Vol. 30, No. 2
- Partial inverse of a monotone operator
  Applied Mathematics & Optimization, Vol. 10, No. 1
- On the non-polynomiality of the relaxation method for systems of linear inequalities
  Mathematical Programming, Vol. 22, No. 1
- CONVERGENCE RESULTS IN A CLASS OF VARIABLE METRIC SUBGRADIENT METHODS11This research was supported in part by the D.G.E.S. (Quebec), the N.S.E.R.C. of Canada under grant A 4152, and the S.S.H.R.C. of Canada.

cover image Mathematics of Operations Research

Volume 5, Issue 3

August 1980

Pages 321-479

Article Information

Metrics

Information

Published Online:August 01, 1980

Cite as

J. L. Goffin, (1980) The Relaxation Method for Solving Systems of Linear Inequalities. Mathematics of Operations Research 5(3):388-414.

https://doi.org/10.1287/moor.5.3.388

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

The Relaxation Method for Solving Systems of Linear Inequalities

Abstract

Volume 5, Issue 3

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News