Fact-checked by Grok 2 weeks ago

Linear inequality

A linear inequality is a mathematical statement that relates two linear expressions using one of the inequality symbols: less than (<), greater than (>), less than or equal to (≤), or greater than or equal to (≥).^[1] Unlike linear equations, which seek exact equality, linear inequalities describe ranges of values satisfying the relation, forming the basis for modeling constraints in various fields. Linear inequalities can involve one or more variables and are solved using methods analogous to those for linear equations, with the key adjustment of reversing the inequality direction when multiplying or dividing both sides by a negative number.^[2] For a single linear inequality in one variable, such as ax + b < c where a \neq 0, the solution is an interval on the real number line, which can be represented using interval notation or graphed on a number line. In two variables, linear inequalities like ax + by \leq c are graphed as half-planes bounded by the line ax + by = c, with the solution set consisting of all points on one side of the boundary, shaded to indicate the feasible region.^[3] Systems of linear inequalities, comprising multiple such constraints, define polyhedral regions in the plane or higher dimensions, which are central to linear programming—a technique for optimizing linear objective functions subject to these constraints.^[4] Applications span economics, engineering, and operations research, including inventory control, production planning, pricing strategies, and resource allocation, where businesses and scientists use these models to identify optimal solutions within real-world limitations. The study of linear inequalities also underpins advanced topics in optimization and control theory, with foundational results like Farkas's lemma providing conditions for the solvability of such systems.^[5]

Fundamentals of Linear Inequalities

Definition and Notation

A linear inequality in n real variables x_1, \dots, x_n is an inequality of the form a_1 x_1 + \dots + a_n x_n \leq b, where the coefficients a_1, \dots, a_n, b \in \mathbb{R} and not all a_i = 0.^[3] Equivalent forms use the relations <, \geq, or > in place of \leq. This expression involves a linear combination of the variables compared to a constant, distinguishing it from nonlinear inequalities that include higher-degree terms or products of variables.^[6] The distinction between strict and non-strict inequalities affects the nature of the solution set: non-strict forms \leq and \geq define closed half-spaces, which include the bounding hyperplane, while strict forms < and > define open half-spaces, excluding the boundary.^[7] In Euclidean space \mathbb{R}^n, a half-space is the set of all points satisfying such an inequality, partitioned by the hyperplane where equality holds.^[6] Standard notation employs vector and matrix forms for conciseness, especially in higher dimensions. A single inequality is written as \mathbf{a}^T \mathbf{x} \leq b, where \mathbf{a} \in \mathbb{R}^n is the row vector of coefficients and \mathbf{x} \in \mathbb{R}^n is the column vector of variables.^[8] For a system of m such inequalities, the compact affine form is A \mathbf{x} \leq \mathbf{b}, with A an m \times n matrix and \mathbf{b} \in \mathbb{R}^m. This notation highlights the affine nature of the inequalities, as they can be rewritten as \mathbf{a}^T (\mathbf{x} - \mathbf{x_0}) \leq 0 for some point \mathbf{x_0}. The origins of linear inequalities trace to 18th-century analytic geometry, where Euler and contemporaries applied them in studying geometric constraints and systems of equations.^[9] The first systematic treatment appeared in Joseph Fourier's 1827 work on solving systems of linear inequalities, which introduced an elimination method later refined by Theodore Motzkin in 1936 and known as Fourier-Motzkin elimination.^[10]

Basic Properties and Operations

Linear inequalities over the real numbers satisfy several fundamental properties that allow for algebraic manipulation while preserving the truth of the statement. For any real numbers a, b, and c, if a < b, then a + c < b + c and a - c < b - c, meaning addition or subtraction of the same constant to both sides preserves the direction of the inequality.^[11] Similarly, if a < b and c > 0, then a \cdot c < b \cdot c and \frac{a}{c} < \frac{b}{c}, so multiplication or division by a positive scalar also preserves the inequality direction.^[12] However, if c < 0, the inequality reverses: a \cdot c > b \cdot c and \frac{a}{c} > \frac{b}{c}.^[11] These properties extend to combining inequalities through transitivity: if a \leq b and b \leq c, then a \leq c for real numbers a, b, and c.^[11] Equivalence under scaling holds for positive multipliers; multiplying both sides of a linear inequality by a positive constant yields an equivalent inequality with the same solution set.^[12] For instance, starting from $2x + 3 \leq 7, subtracting 3 from both sides gives $2x \leq 4, and dividing by 2 (positive) yields x \leq 2, preserving the solution.^[13] In contrast, for -3x + 1 \geq 5, subtracting 1 gives -3x \geq 4, and dividing by -3 (negative) reverses the inequality to x \leq -\frac{4}{3}.^[14] Degenerate cases arise when the coefficient of the variable is zero, reducing the inequality to a constant comparison independent of the variable. For example, $0 \cdot x + b \leq d simplifies to b \leq d; if b > 0 and d \geq b, the inequality holds for all real x, while if b > d, it holds for no x.^[2] These properties form the basis for manipulating linear inequalities without altering their validity over the reals.

Linear Inequalities in Low Dimensions

Inequalities in One Variable

A linear inequality in one variable takes the form ax + b < c, ax + b \leq c, ax + b > c, or ax + b \geq c, where a \neq 0 and a, b, c are real constants.^[2] The solution consists of all values of x that satisfy the inequality. To solve such an inequality, perform algebraic operations to isolate the variable on one side, treating it similarly to solving an equation but reversing the inequality direction when multiplying or dividing both sides by a negative number.^[2] For instance, consider $2x - 5 \leq 7: add 5 to both sides to get $2x \leq 12, then divide by 2 to obtain x \leq 6. If the coefficient is negative, as in -3x + 4 > 10, subtract 4 to yield -3x > 6, then divide by -3 and reverse the sign: x < -2.^[2] The solution set is an interval on the real number line, such as (-\infty, k), (-\infty, k], [k, \infty), or (k, \infty), depending on whether the inequality is strict or inclusive.^[15] For the earlier example x \leq 6, the interval is (-\infty, 6].^[2] In practical contexts, linear inequalities model constraints like budgets. For example, if items cost $5 each and the budget is $100, the inequality $5x \leq 100 simplifies to x \leq 20, indicating at most 20 items can be bought.^[16] Absolute value inequalities in linear form, such as |x - a| \leq b with b > 0, translate to compound inequalities -b \leq x - a \leq b, or equivalently a - b \leq x \leq a + b.^[17] Solving |x - 3| \leq 4 yields -1 \leq x \leq 7, an interval of length 8 centered at 3.^[17] For strict inequalities like |x - a| < b, the solution is the open interval (a - b, a + b).^[18]

Graphical Solutions in Two Dimensions

To graphically represent a linear inequality in two variables, such as ax + by \leq c, where a, b, and c are constants and not both a and b are zero, first plot the corresponding boundary line given by the equation ax + by = c.^[19] This line divides the Cartesian plane into two regions known as half-planes.^[20] The solution set, or feasible region, consists of one of these half-planes, determined by which side satisfies the original inequality.^[21] The graphing process begins by finding the intercepts of the boundary line: set y = 0 to solve for the x-intercept and set x = 0 to solve for the y-intercept, then plot these points and connect them with a straight line.^[20] Use a solid line if the inequality includes equality (≤ or ≥), indicating that points on the boundary are part of the solution set; use a dashed line for strict inequalities (< or >), excluding the boundary.^[19] To identify the correct half-plane for shading, select a test point not on the line, such as the origin (0,0), and substitute its coordinates into the inequality.^[21] If the inequality holds true for the test point, shade the half-plane containing that point; if false, shade the opposite half-plane.^[20] This method works reliably unless the line passes through the test point, in which case choose another point, like (1,1).^[19] For vertical or horizontal lines, which are parallel to the axes, the process remains the same but simplifies due to the line's orientation.^[20] A vertical line like x = k divides the plane into left and right half-planes, while a horizontal line like y = k divides it into upper and lower half-planes; testing a point determines the shading direction accordingly.^[21] Consider the example x + y \leq 4. The boundary line is x + y = 4, with intercepts at (4,0) and (0,4), plotted as a solid line.^[19] Testing (0,0): $0 + 0 \leq 4 is true, so shade the half-plane below and including the line, forming the feasible region.^[20] For the strict inequality x + y < 4, use a dashed line and shade the same half-plane but exclude the boundary.^[21] Another example is $2x - 3y \geq 6. The boundary $2x - 3y = 6 has intercepts at (3,0) and (0,-2), plotted solid. Testing (0,0): $2(0) - 3(0) \geq 6 is false, so shade the opposite half-plane, above and including the line.^[19] The feasible region for a single linear inequality is always an unbounded half-plane, providing a visual representation of all points (x,y) satisfying the condition.^[20] This graphical approach emphasizes the geometric interpretation of linear inequalities as dividing the plane into solution and non-solution areas.^[21]

Linear Inequalities in Higher Dimensions

General Form and Solution Sets

In the context of n-dimensional real space, a linear inequality takes the general form \mathbf{a} \cdot \mathbf{x} \leq b, where \mathbf{x} \in \mathbb{R}^n is the variable vector, \mathbf{a} \in \mathbb{R}^n is a fixed nonzero coefficient vector (the normal vector), and b \in \mathbb{R} is a constant scalar determining the offset.^[22] This form generalizes the concept from lower dimensions and represents a constraint that defines one side of a separating boundary in \mathbb{R}^n.^[22] The solution set of this inequality, denoted H = \{\mathbf{x} \in \mathbb{R}^n \mid \mathbf{a} \cdot \mathbf{x} \leq b\}, is known as a closed half-space in \mathbb{R}^n.^[22] Half-spaces possess key geometric properties: they are convex, meaning that the line segment connecting any two points in H lies entirely within H, as established by the fact that if \mathbf{a} \cdot \mathbf{y} \leq b and \mathbf{a} \cdot \mathbf{z} \leq b, then for $0 \leq t \leq 1, \mathbf{a} \cdot (t\mathbf{y} + (1-t)\mathbf{z}) = t(\mathbf{a} \cdot \mathbf{y}) + (1-t)(\mathbf{a} \cdot \mathbf{z}) \leq t b + (1-t) b = b.^[23] Additionally, half-spaces are unbounded, extending infinitely in directions orthogonal to \mathbf{a} or away from the boundary, unless the inequality is inconsistent (resulting in the empty set) or tautological (the entire space).^[22] In specific dimensions, these solution sets take familiar forms that illustrate the abstraction. For n=1, where \mathbf{x} = x \in \mathbb{R}, the half-space is a closed interval of the form (-\infty, b/a] if a > 0, or [b/a, \infty) if a < 0, representing a ray on the real line.^[22] For n=2, the solution set is a closed half-plane in the plane, bounded by a line and extending infinitely in one direction, which can be visualized using graphical techniques as discussed in two-dimensional representations.^[22] The boundary of the half-space is the hyperplane defined by the equality \mathbf{a} \cdot \mathbf{x} = b, which forms an (n-1)-dimensional affine subspace of \mathbb{R}^n.^[24] This hyperplane acts as the separating surface, with the half-space consisting of all points on one side including the boundary itself.^[24]

Systems of Linear Inequalities

A system of linear inequalities consists of a finite collection of inequalities of the form Ax \leq b, where A is an m \times n matrix with real entries, x \in \mathbb{R}^n is the vector of variables, and b \in \mathbb{R}^m is a vector of constants.^[25] Each row of the system defines a half-space in \mathbb{R}^n, and the inequalities collectively constrain the feasible region for x. The solution set of the system, denoted P = \{x \in \mathbb{R}^n \mid Ax \leq b\}, is the intersection of these m half-spaces, forming a polyhedron in \mathbb{R}^n.^[26] This set P is feasible if it is non-empty, meaning there exists at least one x satisfying all inequalities; otherwise, the system is infeasible and P = \emptyset.^[27] One method for determining the feasibility of such a system is the Fourier-Motzkin elimination algorithm, which eliminates variables sequentially to reduce the problem to a single inequality. The steps are as follows: (1) select a variable x_k to eliminate; (2) classify the inequalities based on the coefficient of x_k: those with positive coefficients provide upper bounds on x_k, those with negative coefficients provide lower bounds, and those with zero coefficients are retained unchanged; (3) for each pair consisting of a lower bound x_k \geq L_i and an upper bound x_k \leq U_j (where L_i and U_j are affine functions of the remaining variables), generate the new inequality L_i \leq U_j, which eliminates x_k; (4) combine these new inequalities with the unchanged ones to form a system in n-1 variables; (5) repeat until only one variable remains, then check if its bounds are consistent (i.e., the greatest lower bound is at most the least upper bound).^[28] The algorithm has exponential complexity, with the number of inequalities potentially growing as O(2^m) in the worst case due to the pairwise combinations generated during elimination.^[29] Redundancy in a system arises when an inequality does not affect the solution set, meaning P remains unchanged if that inequality is removed. To identify a redundant inequality a_i^T x \leq b_i (the i-th row of Ax \leq b), solve the linear programming problem \max \{ a_i^T x \mid A_j x \leq b_j, \, j \neq i \}; the inequality is redundant if the optimal value is at most b_i. This check can be applied to each inequality, though computational efficiency improves when integrated with simplex-based solvers for the overall system.

Applications of Linear Inequalities

Polyhedra and Convex Sets

The solution set of a finite system of linear inequalities in \mathbb{R}^n defines a polyhedron, which is the intersection of the corresponding half-spaces [ \web:6](https://www.math.ucdavis.edu/~deloera/TEACHING/MATH168/notesconvexity.pdf). Polyhedra may be bounded, in which case they are called polytopes, or unbounded; a polytope can equivalently be expressed as the convex hull of a finite set of points [ \web:6](https://www.math.ucdavis.edu/~deloera/TEACHING/MATH168/notesconvexity.pdf). Polyhedra admit two primary representations: the H-representation, given by a finite collection of linear inequalities Ax \leq b where A is an m \times n matrix and b \in \mathbb{R}^m, and the V-representation, consisting of the convex hull of finitely many vertices along with rays and lines for unbounded directions [ \web:5](https://people.inf.ethz.ch/fukudak/Doc_pub/polyfaq220115c.pdf). Each half-space defined by a linear inequality is convex, and the intersection of any collection of convex sets is convex, so every polyhedron is a convex set [ \web:24](https://www.damtp.cam.ac.uk/user/hf323/L22-III-OPT/lecture2.pdf). For bounded polyhedra, the Minkowski-Weyl theorem establishes the precise equivalence between the H- and V-representations: a set is a polytope if and only if it is the convex hull of finitely many points, and conversely, every such convex hull can be expressed as the solution set to a finite system of linear inequalities [ \web:12](https://people.inf.ethz.ch/fukudak/polyfaq/node14.html). A representative example in three dimensions is the standard 3-simplex (a tetrahedron), defined by the inequalities x \geq 0, y \geq 0, z \geq 0, and x + y + z \leq [1](/page/1), whose vertices are the origin and the points (1,0,0), (0,1,0), and (0,0,1) [ \web:6](https://www.math.ucdavis.edu/~deloera/TEACHING/MATH168/notesconvexity.pdf). Similarly, the unit cube in \mathbb{R}^3 is the intersection of the six inequalities \pm x \leq [1](/page/1), \pm y \leq [1](/page/1), and \pm z \leq [1](/page/1), forming a polytope with eight vertices at the points where three pairwise perpendicular faces meet [ \web:6](https://www.math.ucdavis.edu/~deloera/TEACHING/MATH168/notesconvexity.pdf). In the H-representation of a polyhedron, each inequality corresponds to a supporting hyperplane whose intersection with the polyhedron forms a facet (a maximal face of codimension one); vertices arise as the intersection points of at least n linearly independent inequalities that are tight, while edges connect pairs of such vertices lying on the same facet [ \web:35](https://people.inf.ethz.ch/fukudak/lect/pclect/notes2013/ch5-14.pdf). This structure reflects a form of duality, where the facets of the primal polyhedron (defined by inequalities) correspond to vertices in the polar dual polyhedron, and vice versa, preserving the combinatorial incidence of edges [ \web:35](https://people.inf.ethz.ch/fukudak/lect/pclect/notes2013/ch5-14.pdf).

Linear Programming and Optimization

Linear programming represents a fundamental application of linear inequalities to optimization problems, where the goal is to minimize or maximize a linear objective function subject to a system of linear constraints. The feasible solutions form the intersection of half-spaces defined by the inequalities, resulting in a convex polyhedron known as the feasible region. Optimal solutions, if they exist, occur at vertices of this polyhedron. The standard formulation of a linear program is to minimize \mathbf{c}^\top \mathbf{x} (or equivalently, maximize -\mathbf{c}^\top \mathbf{x}) subject to \mathbf{A} \mathbf{x} \leq \mathbf{b} and \mathbf{x} \geq \mathbf{0}, where \mathbf{c} \in \mathbb{R}^n, \mathbf{A} \in \mathbb{R}^{m \times n}, \mathbf{b} \in \mathbb{R}^m, and \mathbf{x} \in \mathbb{R}^n. Here, the feasible region is a polyhedron, and the problem is feasible if this region is nonempty and bounded below for minimization (or above for maximization) to ensure optimality. This formulation captures a wide range of decision problems by modeling constraints as linear inequalities and objectives as linear combinations of decision variables. The simplex algorithm, introduced by George Dantzig in 1947, provides an efficient method to solve linear programs by iteratively pivoting between basic feasible solutions—corresponding to vertices of the polyhedron—along edges that improve the objective value. Starting from an initial basic feasible solution, the algorithm selects a variable to enter the basis (pivoting in) based on reduced costs and updates the basis by solving a system of equations, effectively traversing the boundary of the feasible region toward the optimum. Degeneracy arises when multiple bases yield the same basic feasible solution, potentially causing cycling, though anti-cycling rules like Bland's rule mitigate this issue. In practice, the simplex method exhibits excellent average-case performance despite its exponential worst-case complexity.^[30] Central to linear programming theory is the duality theorem, which associates each primal problem \min \{\mathbf{c}^\top \mathbf{x} \mid \mathbf{A} \mathbf{x} \geq \mathbf{b}, \mathbf{x} \geq \mathbf{0}\} with a dual \max \{\mathbf{b}^\top \mathbf{y} \mid \mathbf{A}^\top \mathbf{y} \leq \mathbf{c}, \mathbf{y} \geq \mathbf{0}\}. The weak duality theorem guarantees that any feasible primal objective value is at least the corresponding dual value, establishing an upper bound for minimization. Strong duality holds under feasibility and boundedness (or by Slater's condition for strict inequalities), equating the optimal primal and dual values and providing complementary slackness conditions that characterize optimality: for optimal \mathbf{x}^* and \mathbf{y}^*, (\mathbf{b} - \mathbf{A} \mathbf{x}^*)^\top \mathbf{y}^* = 0 and (\mathbf{c} - \mathbf{A}^\top \mathbf{y}^*)^\top \mathbf{x}^* = 0. This framework, originating from John von Neumann's work on game theory around 1947, enables sensitivity analysis and economic interpretations of shadow prices. Linear programming finds extensive applications in resource allocation, such as optimizing production mixes under limited inputs like labor and materials, and in transportation problems, where it minimizes shipping costs from multiple sources to destinations subject to supply and demand constraints. For instance, the transportation problem can be modeled as \min \sum_{i,j} c_{ij} x_{ij} subject to row and column sum inequalities representing supplies and demands, with x_{ij} \geq 0. Regarding computational complexity, while the simplex method is not polynomial-time in the worst case, Leonid Khachiyan's ellipsoid method from 1979 demonstrated that linear programming is solvable in polynomial time by iteratively shrinking an ellipsoid containing a feasible point using subgradient information from violated constraints. This theoretical breakthrough, running in O(n^6 L) time where L is the bit length, paved the way for interior-point methods that are now competitive in practice.^[31]^[32]

Generalizations and Extensions

Inequalities over Ordered Fields

An ordered field is a field F equipped with a total order \leq that is compatible with the field operations. Specifically, the order is defined via a subset P \subseteq F of positive elements satisfying: (1) $0 \notin P; (2) for every a \in F, exactly one of a \in P, a = 0, or -a \in P holds (trichotomy); (3) P is closed under addition; and (4) P is closed under multiplication.^[33] The order is then given by a \leq b if and only if b - a \in P \cup \{0\}. Classic examples include the rational numbers \mathbb{Q} and the real numbers \mathbb{R}, both of which satisfy these properties.^[34] In an ordered field F, a linear inequality takes the form a_1 x_1 + \cdots + a_n x_n \leq b, where a_i, b \in F and x_i \in F are variables. The solution set consists of all points x = (x_1, \dots, x_n) \in F^n satisfying the inequality, which defines a half-space in the ordered vector space F^n. This generalizes the real case, where such sets are convex regions bounded by hyperplanes, but in F^n, the geometry depends on the field's order structure rather than Euclidean topology.^[33] Key properties of inequalities in ordered fields follow from the order axioms. Addition preserves inequalities: if a \leq b and c \leq d, then a + c \leq b + d. Multiplication by positives preserves direction: if a \leq b and $0 \leq c, then [a c](/page/Multiplication) \leq [b c](/page/Multiplication); multiplication by negatives reverses it. These ensure that manipulations of linear inequalities, such as adding terms or scaling coefficients, remain valid without altering the solution set's order relations.^[33] However, not all ordered fields share the completeness of \mathbb{R}, where every nonempty subset bounded above has a least upper bound. For instance, \mathbb{Q} lacks this property, as the set \{ q \in \mathbb{Q} \mid q^2 < 2 \} is bounded above but has no least upper bound in \mathbb{Q}. This incompleteness affects solution sets of inequalities in \mathbb{Q}^n, potentially leading to "gaps" not present in \mathbb{R}^n.^[34] Beyond \mathbb{Q} and \mathbb{R}, ordered fields include constructions like formal power series fields. For an ordered field K and ordered abelian group G, the field K((G)) of formal Laurent series \sum_{g \in G} a_g t^g (with a_g \in K, finitely many negative powers) can be ordered by declaring a series positive if its leading coefficient (lowest g with a_g \neq 0) is positive in K. Linear inequalities in such fields yield solution half-spaces in K((G))^n, often non-Archimedean, illustrating extensions beyond familiar number systems.^[35]

Linear Inequalities in Abstract Settings

In abstract algebraic structures beyond the real numbers, linear inequalities generalize to settings where order is defined via cones, lattices, or semirings, allowing the study of solution sets in non-traditional domains. These frameworks extend classical notions by incorporating partial orders compatible with vector space operations or lattice meet/join structures, enabling applications in optimization, logic, and combinatorial geometry without relying on metric properties.^[36] Partially ordered vector spaces provide a foundational abstract setting for linear inequalities, where the order is induced by a convex cone. In a real vector space V, a nonempty convex cone K \subseteq V defines a partial order by x \leq_K y if and only if y - x \in K, making V a partially ordered vector space with K as the positive cone.^[36] Linear inequalities in this context take the form \langle a_i, x \rangle \leq b_i for i = 1, \dots, m, where the solution set is an order ideal if it is downward closed under the partial order, meaning if x satisfies the inequalities and y \leq_K x, then y does too.^[37] Order ideals play a central role in decomposing spaces and analyzing positive operators, as they correspond to subspaces stable under the order. Seminal work by Kantorovich established that such spaces admit extensions of positive linear functionals, analogous to Hahn-Banach for ordered settings.^[38] Integer linear inequalities arise in the study of Diophantine approximations and integer polyhedra, where solutions are restricted to lattice points in \mathbb{Z}^n. The set \{x \in \mathbb{Z}^n \mid A x \leq b\}, with A \in \mathbb{Q}^{m \times n} and b \in \mathbb{Q}^m, forms an integer polyhedron, whose vertices and facets are governed by totally unimodular matrices or Gomory-Chvátal closures for integrality. These structures capture Diophantine approximations, such as bounding \|A x - b\|_\infty for integer x, with applications to simultaneous approximation theorems like Dirichlet's, where the existence of good approximations follows from pigeonhole principles on polyhedral tilings. Schrijver's comprehensive theory shows that integer polyhedra can be described by their Hilbert basis of extreme rays, ensuring finite generation under certain boundedness conditions. In lattice theory, linear inequalities manifest through order relations in distributive lattices and Boolean algebras, where the partial order is the lattice order defined by meets (\wedge) and joins (\vee). Distributive lattices satisfy a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c), allowing inequalities like x \leq y to be interpreted as x = x \wedge y, with solution sets forming down-sets or filters. Birkhoff's representation theorem establishes that every finite distributive lattice is isomorphic to the lattice of order ideals of a poset, where inequalities define the ideals as subsets closed under meets. In Boolean algebras, a complemented distributive lattice, inequalities correspond to subset inclusions, with linear-like constraints arising in Dedekind's theory of free distributive lattices, bounding the size by the number of join-irreducibles. Tropical geometry reframes linear inequalities in max-plus algebras, where addition is replaced by maximum and multiplication by addition, turning constraints into min/max operations over the tropical semiring (\mathbb{R} \cup \{\infty\}, \max, +). A tropical linear inequality \max_i (a_{ij} + x_j) \leq b_i defines a tropical polytope as the solution set, whose vertices are determined by tight constraints forming a tropical basis.^[39] In this setting, systems of such inequalities model piecewise-linear functions and amoebas of algebraic varieties in the limit, with duality theorems ensuring strong optimality conditions analogous to Farkas' lemma. Mikhalkin's foundational work links these to enumerative invariants, where the number of solutions to tropical systems counts complex curve intersections via stable intersections.^[39]

References

[1]
[PDF] Linear Inequalities | Regent University
• Linear Inequality: A linear inequality is a linear relation that uses one of the four inequality symbols instead of the equals sign used in linear equations.
[2]
Algebra - Linear Inequalities - Pauls Online Math Notes
Nov 16, 2022 · means that a a is some number that is either strictly bigger than b b or is exactly equal to b b . Likewise, it is assumed that you know how to ...
[3]
Tutorial 24: Graphing Linear Inequalities - West Texas A&M University
Jul 31, 2011 · In this tutorial we will be looking at linear inequalities in two variables. It will start out exactly the same as graphing linear equations ...
[4]
[PDF] 9.4 SYSTEMS OF LINEAR INEQUALITIES; LINEAR PROGRAMMING
The solution set for a linear inequality, such as ax 1 by , c, consists of all points on one side of the defining line, ax 1 by 5 c. The graph of the linear.
[5]
[PDF] ON THE DEVELOPMENT OF OPTIMIZATION THEORY 1 Introduction
In that paper Farkas's fundamental theorem on linear inequalities was used to derive necessary conditions for optimality for the nonlinear programming problem.
[6]
Systems of Inequalities - Department of Mathematics at UTSA
Nov 5, 2021 · In mathematics a linear inequality is an inequality which involves a linear function. A linear inequality contains one of the symbols of ...
[7]
[PDF] 1. CONVEX SETS - Dartmouth Mathematics
A closed half space is the truth set of an inequality of the form Aix ≤ b₁. (An inequality of the form Ax ≥ b₁ can be converted into one of this form by ...
[8]
[PDF] MATH 340 Standard Inequality Form Richard Anstee Linear ...
Our standard inequality form can now be written in matrix notation: max c · x. Ax ≤ b x. ≥ 0 . Note that we cannot directly deal with strict inequalities.
[9]
[PDF] A Brief History of Linear Algebra - University of Utah Math Dept.
Linear algebra evolved from early Babylonian and Chinese work, with Euler's work, Gauss's method, and Cayley's matrix work, and is used in many applications.Missing: inequalities | Show results with:inequalities
[10]
[PDF] Fourier-Motzkin Elimination Projects
In 1827 Fourier published a method for solving linear inequalities in the real case. This method is known as Fourier-Motzkin elimination.
[11]
[PDF] Inequalities - Purdue Math
I2: (Transitivity) If a<b and b<c, then a<c. I3: (Additivity) If a<b and c is any real number, then a+c < b + c. I4: (Multiplicativity) If a<b and c > 0, then ...
[12]
[PDF] Axioms and properties of the real numbers
The basic axioms of inequalities: There is an ordering < on real numbers, satisfying the following, for all real numbers a, b, and c: (Transitivity) If a<b and ...
[13]
Real Numbers:Inequalities - Department of Mathematics at UTSA
Nov 6, 2021 · An inequality is an expression that states that two quantities are unequal or not equivalent to one another.Definition of Inequalities · Possible Relationships · Properties · Solving Inequalities
[14]
[PDF] 1.7 Inequalities
Properties of Inequality. For real numbers a, b and c: 1. If a < b, then a + c < b + c,. 2. If a < b and if c > ...
[15]
Tutorial 22: Linear Inequalities - West Texas A&M University
Dec 17, 2009 · The absolute value is always positive, and any positive number is greater than any negative number, therefore all real numbers would work.
[16]
ORCCA Modeling with Equations and Inequalities - Index of
Hana wants to use car2go and has a maximum budget of $300. $ 300 . Write a linear inequality representing this scenario, where the unknown quantity is the ...<|control11|><|separator|>
[17]
Algebra - Absolute Value Inequalities - Pauls Online Math Notes
Nov 16, 2022 · In this section we want to look at inequalities that contain absolute values. We will need to examine two separate cases.
[18]
Absolute Value Inequalities - UMSL
Step 1: Isolate the absolute value. |3x – 4| + 9 > 5. |3x – 4| > -4 ; Step 2: Is the number on the other side a negative number? Yes, it's a negative number, -4.
[19]
[PDF] Graphs of Linear Inequalities - Finite Mathematics Section 1.4
A Linear Inequality and its Graph A linear inequality has the same form as a linear equation, except that the equal symbol is replaced with any one of ≤, ≥, <, ...Missing: definition | Show results with:definition
[20]
Linear Inequations with two Variables
Graph the region in the plane that represents the solution of any linear inequation of any two variables. Introduction. An inequation with two variables is an ...
[21]
Tutorial 17: Graphing Linear Inequalities. - West Texas A&M University
Jul 5, 2011 · In this tutorial we will be looking at linear inequalities in two variables. It will start out exactly the same as graphing linear equations ...
[22]
None
Below is a merged summary of the halfspace definition and properties from "Convex Optimization" by Boyd & Vandenberghe, consolidating all information from the provided segments into a single, comprehensive response. To maximize detail and clarity, I will use a table in CSV format for key properties and details, followed by a narrative summary that includes additional context and relevant URLs. This approach ensures all information is retained while maintaining readability and density.
[23]
None
### Extracted Theorem and Proof: Closed Half-Space is Convex
[24]
[PDF] An Introduction to Hyperplane Arrangements - UPenn CIS
To make sure that the definition of a hyperplane arrangement is clear, we define a linear hyperplane to be an (n − 1)-dimensional subspace H of V , i.e., H = { ...
[25]
https://www.seas.ucla.edu/~vandenbe/ee236a/lectures/polyhedra.pdf
[26]
[PDF] CLASS NOTES: Math 168 POLYHEDRAL CONVEXITY
May 14, 2012 · A polyhedron is the set of solutions to a system of linear inequalities, and a polytope is the convex hull of a finite set of points.
[27]
[PDF] EE464 Fourier-Motzkin Elimination
linear programming we can also use Farkas lemma to solve linear programs! formulate the standard LP as the feasibility problem. cT x ≤ t. Ax ≤ b and do a ...
[28]
[PDF] Lecture 20: Fourier–Motzkin Elimination 1 The feasibility problem 2 ...
Mar 13, 2020 · However, it is more straightforward to see that every inequality we get is a linear combination of the original inequalities. Let's rewrite our ...
[29]
[1811.01510] Complexity Estimates for Fourier-Motzkin Elimination
Nov 5, 2018 · In this paper, we propose a new method for removing all the redundant inequalities generated by Fourier-Motzkin elimination.<|separator|>
[30]
[PDF] LINEAR PROGRAMMING
Linear programming is a tool to state general goals and lay out detailed decisions to achieve them in complex situations, using mathematical models.
[31]
[PDF] Transportation Problem: A Special Case for Linear Programming ...
The transportation problem aims to minimize the cost of shipping goods to meet needs and ensure capacity, and is a special case of linear programming.
[32]
The Ellipsoid Method - PubsOnLine
In February 1979 a note by L. G. Khachiyan indicated how an ellipsoid method for linear programming can be implemented in polynomial time. This result has ...
[33]
https://math.libretexts.org/Bookshelves/Analysis/Introduction_to_Mathematical_Analysis_I_(Lafferriere_Lafferriere_and_Nguyen)/01%3A_Tools_for_Analysis/1.04%3A_Ordered_Field_Axioms
[34]
[PDF] 1.3. The Completeness Axiom.
Dec 1, 2023 · The rational numbers Q are not a complete ordered field: A = {x ∈ Q | x2 < 2} is bounded above (by, say, 2) but there is no least upper bound of ...
[35]
[PDF] Formal power series
Nov 7, 2012 · If R is an ordered field, we can order. R((G)) by setting any element to have the same sign as its leading coefficient, defined as the least ...
[36]
[PDF] Duality Theory on Vector Spaces - arXiv
Given a vector space Y and a nonempty convex cone C ⊂ Y , we define a relation on. Y by z1 ≤C z2 if and only if z2 − z1 ∈ C. This defines a partial ordering on.
[37]
[PDF] Vector lattice covers of ideals and bands in pre-Riesz spaces - arXiv
Nov 8, 2018 · In the analysis of partially ordered vector spaces, subspaces as ideals and bands play a central role. In vector lattices, problems involving ...
[38]
[PDF] THE PATH AND SPACE OF KANTOROVICH S. S. Kutateladze June ...
Jun 18, 2003 · Therefore, Kantorovich selected the class of K-spaces, now named after him, in his first article on ordered vector spaces. He tied the study ...
[39]
[math/0601041] Tropical Geometry and its applications - arXiv
Jan 3, 2006 · These notes outline some basic notions of Tropical Geometry and survey some of its applications for problems in classical (real and complex) geometry.