Fourier–Motzkin elimination

Fourier–Motzkin elimination
Name	Fourier–Motzkin elimination
Class	Linear inequality projection algorithm
Data structure	System of linear inequalities
Invented by	Joseph Fourier (1827), later rediscovered by Theodore Motzkin (1936)
Time complexity	Doubly exponential in worst case
Space complexity	Exponential
Related to	Linear programming, Convex polytope, Projection

Fourier–Motzkin elimination is a fundamental algorithm in linear algebra and optimization theory for eliminating variables from a system of linear inequalities. The procedure, analogous to Gaussian elimination for linear equations, projects a polyhedron defined by inequalities onto a lower-dimensional subspace by systematically removing one variable at a time. Although conceptually simple, the method can suffer from a combinatorial explosion in the number of generated inequalities, a key factor in its computational complexity. Its historical significance lies in providing a constructive proof for the Farkas lemma and establishing foundational results in linear programming and real algebraic geometry.

Description of the method

The algorithm operates on a finite set of linear inequalities with real coefficients. To eliminate a chosen variable, say \(x_n\), each inequality is solved for \(x_n\), yielding three groups: those where \(x_n\) has a positive coefficient (upper bounds), a negative coefficient (lower bounds), and those where it does not appear. For every pair consisting of one lower bound and one upper bound, a new inequality is formed by combining them to eliminate \(x_n\). This new system, together with the inequalities not containing \(x_n\), defines the projection of the original polyhedron onto the space of the remaining variables. The process is repeated iteratively until a desired subset of variables remains. The final set of inequalities provides a description of the projection, which is itself a convex polyhedron.

Historical context and motivation

The method was first described by the French mathematician Joseph Fourier in an 1827 paper addressing problems in linear optimization, predating the formal development of the field. His work was largely overlooked until it was independently rediscovered by the American mathematician Theodore Motzkin in his 1936 doctoral thesis at the University of Basel. Motzkin's rediscovery occurred during a period of intense foundational work in optimization theory, notably preceding the development of the simplex method by George Dantzig. The algorithm provided one of the first systematic techniques for studying the feasible region of linear programs and became a crucial tool for proving fundamental theorems like the Farkas lemma and the Minkowski–Weyl theorem.

Geometric interpretation

Geometrically, the algorithm computes the orthogonal projection of a convex polytope onto a coordinate hyperplane. Each elimination step corresponds to projecting the polyhedron along the axis of the eliminated variable. The pairing of lower and upper bounds represents the construction of the convex hull of the projection of all extreme points and extreme rays. This process reveals that the projection of a polyhedron is always another polyhedron, a key result in the theory of convex sets. The method thus gives a constructive proof that the image of a polyhedron under a linear map is again a polyhedron, a property central to integer programming and parametric optimization.

Complexity and computational considerations

A major drawback of Fourier–Motzkin elimination is its potential for combinatorial explosion. In the worst case, eliminating a single variable can square the number of inequalities, leading to a doubly exponential blow-up in the total number of constraints after eliminating all variables. This severe complexity limits its direct practical use for large-scale problems, especially when compared to efficient methods like the simplex method or interior-point methods for solving linear programs. However, it remains theoretically important for analyzing the structural complexity of polyhedra and is used in specialized tools for quantifier elimination over the real numbers, such as in the Cylindrical algebraic decomposition algorithm.

Applications

Beyond its theoretical role, Fourier–Motzkin elimination finds practical use in several domains. In formal verification and static program analysis, it is used for computing invariants and analyzing reachability in systems with linear constraints. It serves as a core engine in some SMT solvers for the theory of linear real arithmetic. Within operations research, it is applied to problems like parametric linear programming and projection of polytopes. The algorithm also underpins methods in computational geometry for polyhedral computation and is instrumental in quantifier elimination procedures for the first-order theory of the real numbers.

Example

Consider eliminating variable \(x\) from the system: \[ \begin{align*} y - x &\leq 0 \quad \text{(Lower bound: } x \geq y\text{)} \\ x &\leq 3 \quad \text{(Upper bound: } x \leq 3\text{)} \\ x + y &\leq 5 \quad \text{(Upper bound: } x \leq 5 - y\text{)} \end{align*} \] The lower bound is \(x \geq y\). Pairing it with each upper bound yields new inequalities without \(x\): \[ \begin{align*} \text{From } x \geq y \text{ and } x \leq 3: &\quad y \leq 3 \\ \text{From } x \geq y \text{ and } x \leq 5 - y: &\quad y \leq 5 - y \ \Rightarrow\ 2y \leq 5 \ \Rightarrow\ y \leq 2.5 \end{align*} \] The projected system in terms of \(y\) is thus \(y \leq 3\) and \(y \leq 2.5\), which simplifies to \(y \leq 2.5\). This describes the projection of the original feasible region onto the \(y\)-axis.

Category:Linear algebra Category:Algorithms Category:Mathematical optimization