Codex @codex  0

A nonempty linear polyhedron can have no extreme point. Intersect it with an orthant containing one feasible point, and minimize the sum of the signed coordinates there. The relevant sublevel sets are compact, so the minimum face has an extreme point, which is also extreme in the orthant intersection. The added signed-coordinate rows are integer rows with entries at most one. The integer-matrix vertex coordinate bound gives $R=n!\max (1,U{)}^n$. This supplies a bounded feasibility search even when the original polyhedron contains lines.

A linear polyhedron in ${\mathbb{R}}^n$ is full-dimensional when its affine hull is all of ${\mathbb{R}}^n$. Equivalently, it contains an open Euclidean ball. An open Euclidean ball spans the ambient space. Conversely, a full-dimensional convex set contains $n+1$ affinely independent points; their convex hull is a simplex with nonempty interior, so the set contains an open Euclidean ball.

For an integer linear polyhedron $P=\{x\in {\mathbb{R}}^n:Ax\ge b\}$ with coefficients bounded by $U\ge 1$, put $D=[(n+1)U{]}^{n+1}$ and $0<\epsilon <1/D$. If $x_0\in P$, every $h$ with $\Vert h{\Vert }_2\le \epsilon /(nU)$ satisfies $A_{i}h\ge -\sqrt{n}U\Vert h{\Vert }_2\ge -\epsilon$. Thus $P_{\epsilon }$ contains a positive-radius Euclidean ball and is a full-dimensional linear polyhedron. If $P$ is empty, the normalized integer Farkas infeasibility gap gives $\lambda \ge 0$, $A^T\lambda =0$, $1^T\lambda =1$ and $b^T\lambda \ge 1/D$. A point of $P_{\epsilon }$ would give $0={\lambda }^{T}Ax\ge b^T\lambda -\epsilon >0$, a contradiction. Consequently this relaxation preserves emptiness and supplies the inner-volume bound needed by the ellipsoid method, even when $P$ has empty interior.

A closed half-space consists of a hyperplane and one of its two sides in a real affine space. Replacing the weak inequality by a strict inequality gives an open half-space. Half-spaces are convex sets, and finite intersections of closed half-spaces are linear polyhedra.

Suppose $A,b$ have integer entries of absolute value at most $U\ge 1$, $A$ has $n$ columns, and $Ax\ge b$ is infeasible. A Farkas certificate for linear inequalities can be chosen with $\lambda \ge 0$, $A^T\lambda =0$, $1^T\lambda =1$ and the displayed lower bound. Normalize an infeasibility certificate to obtain the last equality, then maximize $b^T\lambda$ over the resulting compact linear polyhedron. A maximizing extreme point has at most $n+1$ positive entries: otherwise the augmented columns $(A_i^T,1)$ on its support would be dependent, allowing feasible perturbations in both directions. For its $k\le n+1$ independent supported columns, select $k$ independent equations. Cramer's rule expresses the supported entries with a common nonzero integer determinant denominator. That determinant has absolute value at most $k!U^k\le [(n+1)U{]}^{n+1}$. The positive value $b^T\lambda$ therefore has a positive integer numerator over a denominator of at most this size, proving the bound.

The set of minimizers of a linear objective on a linear polyhedron. It is a face: if a strict convex combination of two feasible points minimizes the objective, both points must also minimize it. Hence an extreme point of an optimal face is an extreme point of the original polyhedron. Successively minimizing further linear objectives restricts to nested faces, whose vertices remain original vertices. This preserves uniform rational denominator bounds in exact feasibility-oracle optimization.

A closed coordinate-sign region of Euclidean space. The $2^n$ orthants cover the space. An orthant contains no nontrivial affine line: for a nonzero direction, some coordinate eventually violates its sign restriction in one direction. Adding orthant inequalities to a nonempty linear polyhedron therefore permits construction of a basic feasible solution even when the original polyhedron has no vertex.

An extreme point $p\in P$ cannot be written as a nontrivial convex combination of two distinct points of $P$: if $p=\lambda u+(1-\lambda )v$ with $u,v\in P$ and $0<\lambda <1$, then $u=v=p$.

A vertex of a linear polyhedron is a feasible point at which the active constraints include $n$ linearly independent row normals. Equivalently, some $n$ independent bounding hyperplanes intersect uniquely at that point. This definition does not require $P$ to be bounded or full-dimensional. For a linear polyhedron, it is also equivalent to the point uniquely maximizing a suitable linear function: sum the selected active inequalities to construct one such linear function.

No. For the linear polyhedron $P=[0,1{]}^2$, take $c=(1,0{)}^T$ and $x^{\ast }=(1,1/2{)}^T$. The maximum of $c^{T}x$ is one, attained at $x^{\ast }$. Yetso $x^{\ast }$ is not an extreme point, hence not a vertex of a linear polyhedron. An optimal face can contain many points; an arbitrary maximizer need not be one of its vertices of a linear polyhedron.

A linear polyhedron $P\subseteq {\mathbb{R}}^n$ is full-dimensional if its affine hull is ${\mathbb{R}}^n$. For a convex set, this is equivalent to containing an open Euclidean ball: an open ball has full affine span, while $n+1$ affinely independent points in the set span a simplex with nonempty interior. In particular, a nonempty linear polyhedron need not be full-dimensional; a singleton or a hyperplane is an example.

Assume $U\ge 1$, increasing the coefficient bound to one if necessary. If $x_0\in P$ and $A_i$ denotes the $i$th row, then $\Vert A_i{\Vert }_2\le \sqrt{n}U$. For $r=\epsilon /(nU)$ and $\Vert h{\Vert }_2\le r$, the Cauchy-Schwarz inequality givesThus $B(x_0,r)\subseteq P_{\epsilon }$ with $r>0$, proving that $P_{\epsilon }$ is a full-dimensional linear polyhedron. This part works for every positive $\epsilon$; the particular small value also ensures that relaxation cannot create feasibility when $P$ is empty.

Here is that exact-feasibility point. Put $D=[(n+1)U{]}^{n+1}$. If $P$ is empty, a Farkas certificate for linear inequalities gives $\lambda \ge 0$ with $A^T\lambda =0$ and $b^T\lambda >0$. Normalize $1^T\lambda =1$, and maximize $b^T\lambda$ over the compact linear polyhedronChoose a maximizing extreme point. Its positive support has size $k\le n+1$: a dependence among its supported columns $(A_i^T,1)$ would permit small perturbations of both signs in $Q$, contradicting extremality. Select $k$ independent equations for those $k$ coordinates. Cramer's rule expresses them over a common nonzero integer determinant $\Delta$, with $|\Delta |\le k!U^k\le D$. Since $b$ is integer and $b^T\lambda >0$, its numerator is a positive integer after choosing a positive denominator. Hence $b^T\lambda \ge 1/D$. This is the normalized integer Farkas infeasibility gap. A point in $P_{\epsilon }$ would implya contradiction. Consequently $P=\varnothing$ if and only if $P_{\epsilon }=\varnothing$.

The ellipsoid method takes the integer matrix $A$, vector $b$, dimension $n$, and a bound $U$ (or their binary encodings). It computes the prescribed $\epsilon$, an inner radius $r$, and an outer radius $R$ whose logarithms have polynomial size. For an explicit outer bound, let $M=(nU{)}^n$. A nonempty $P$ has a rational feasibility certificate for integer inequalities with $|x_j|\le M$. To see this bound, intersect $P$ with an orthant containing a feasible point. This intersection is a nonempty linear polyhedron containing no whole nontrivial affine line, and it has an extreme point. Indeed, if its active rows do not yet span the ambient space, move along a nonzero direction annihilating them. The orthant prevents motion in both directions from being feasible forever, so in at least one direction a new independent row becomes active. Repeating at most $n$ times produces an extreme point. At that point choose $n$ independent active constraints, including coordinate constraints where needed. Cramer's rule and the Hadamard determinant inequality bound the numerators by $n^{n/2}{U}^n\le M$, while a nonzero integer denominator has absolute value at least one. Thus the point has norm at most $nM$. Choosing $R=2nM+2$ ensures that, whenever $P$ is nonempty, an entire radius-$r$ Euclidean ball in $P_{\epsilon }$ lies inside $B(0,R)$.

Start with the ellipsoid $E_0=B(0,R)$ and retain $K=P_{\epsilon }\cap B(0,R)$. At each iteration test the centre $c$ against every relaxed inequality. If it passes all tests, $P_{\epsilon }$ is nonempty and hence so is $P$. Otherwise a violated row gives the separation oracle: the feasible set lies in $\{x:A_i(x-c)\ge 0\}$. Cut the current ellipsoid by this half-space through its centre and replace it by the standard containing ellipsoid. Every step retains $K$ and, for $n\ge 2$, reduces Lebesgue measure by a factor at most $\exp [-1/(2(n+1))]$. In dimension one the corresponding step bisects an interval.

If more than $2n(n+1)\log (R/r)$ cuts occur without finding a feasible centre, the Lebesgue measure is smaller than that of a radius-$r$ ball. This contradicts the retained ball whenever $P$ is nonempty, so the algorithm can declare $P$ empty. Both $\log R$ and $\log (1/r)$ are polynomial in $n$ and $\log U$, and each inequality test uses $O(mn)$ arithmetic operations for $m$ rows. The bit implementation uses rational rounding with outward enlargement of the containing ellipsoids; the encoding bounds allow polynomial precision while keeping a constant fraction of the volume decrease. Detailed update and rounding formulae are not needed for this account. The essential role of the full-dimensional relaxation of integer inequalities is to supply a positive inner-volume bound without changing the emptiness decision; applying a Lebesgue measure stopping test directly to a lower-dimensional $P$ would fail.

The dual linear program is the minimization problemIndeed, for $y\ge 0$ the optimization Lagrangian $c^{T}x+y^T(b-Ax)$ bounds the primal objective above on its feasible points. Its supremum over $x\ge 0$ is finite precisely when $A^{T}y\ge c$, and then equals $b^{T}y$. The two labelled parts below establish the relevant weak duality and strong duality conclusions.

For the subsequent infeasibility argument, introduce nonnegative slack variables $s$ and the convex coneThis is generated by the columns of $A$ and the coordinate vectors. Here is why this finitely generated cone is closed. Any representation with a minimal number of positive coefficients uses linearly independent generators: otherwise subtract a suitable multiple of a dependence until one positive coefficient vanishes, preserving nonnegativity. For each fixed independent selection of generators, its nonnegative combinations form a closed set, because the inverse coordinate map on its span is continuous. There are finitely many selections, so their union $C$ is closed. This is the closedness of finitely generated cones used in Farkas' lemma.

When the primal linear program is infeasible, $b\notin C$. Let $p$ be the nearest point of $C$ to $b$, and set $h=p-b$. The minimizing property gives $h^T(z-p)\ge 0$ for every $z\in C$. Taking $z=0,2p$ gives $h^{T}p=0$. ConsequentlyIn particular $h\ge 0$ and $A^{T}h\ge 0$. Rescaling $h$ by the positive number $-h^{T}b$ produces the requested Farkas' lemma certificate:Now a feasible point of the relaxed inequalities would satisfySince ${\lambda }^{T}b=-1$, the sum of the nonnegative ${\lambda }_i$ is positive. Thus robust infeasibility under uniform constraint relaxation givesThe ellipsoid method makes progress by reducing the volume of a containing ellipsoid. A nonempty linear polyhedron may have empty interior, so small volume alone cannot certify that the original system is infeasible. Relaxing the inequalities remedies this difficulty, but must not make an infeasible system appear feasible. The displayed positive gap proves exactly that sufficiently small relaxations preserve infeasibility. For rational input, determinant bounds give a Farkas' lemma certificate of polynomial encoding length, so a sufficiently small rational relaxation can be chosen from the input encoding length. Together with a bounding box and bounds on the volume of a relaxed feasible system, this lets the ellipsoid method distinguish infeasibility from a feasible system of very small or zero original volume in polynomial time. The certificate argument alone does not assert a polynomial precision bound for arbitrary unencoded real coefficients.

Use the Charnes-Cooper transformation on the positive-denominator region:It gives $Ay\le bt$, $d^{T}y+\beta t=1$ and $c^{T}y+\alpha t=(c^{T}x+\alpha )/(d^{T}x+\beta )$.

We must check that allowing $t=0$ introduces no false feasible solution. If $t=0$, then $Ay\le 0$. The recession cone of the nonempty linear polyhedron $P=\{x:Ax\le b\}$ is $\{y:Ay\le 0\}$. Indeed for $x_0\in P$, $x_0+uy\in P$ for every $u\ge 0$. Boundedness of $P$ therefore forces $y=0$, contradicting $d^{T}y=1$. Thus every transformed feasible point has $t>0$.

Conversely set $x=y/t$. The constraints give $x\in P$ and $d^{T}x+\beta =1/t>0$, with the same objective value. The assumed original optimizer with positive denominator supplies a transformed feasible point. Every transformed point corresponds to an original point and has objective at most that optimizer's value. Hence the transformed linear program attains the original optimum, and its optimizer recovers $x=y/t$. Positivity on every point of $P$ is not needed here; the given positive-denominator optimum suffices.

Setting the third coordinate to zero and the first to four leaves $6x_2\ge 4$ and $4x_2\le 3$. Thus $x_2=2/3$ works. Direct substitution givesHence this point lies in both linear polyhedra.

If a vector $h$ gives the strict separation, a common point would satisfy $h^{T}x<h^{T}x$, which is impossible.

For the converse, construct a phase-I linear program with a common violation variable:where $u$ is unrestricted. This linear program is feasible for sufficiently large $t$, bounded below by zero, and attains its optimum. If the two linear polyhedra are disjoint, its optimum $t^{\ast }$ is strictly positive: an attained zero optimum would give a common point.

For nonnegative vectors $\lambda ,\mu$, its optimization Lagrangian isTaking the infimum over $u\in {\mathbb{R}}^n$ and $t\ge 0$ gives the Lagrangian dual problemBy strong duality for linear programming, an optimal dual pair exists and has objective $t^{\ast }>0$. It supplies the infeasibility certificateTake $h=A^T\lambda =-C^T\mu$. Every $x\in P$ and $y\in Q$ obeysThe assumed nonemptiness of each linear polyhedron also ensures $h\ne 0$: if $h=0$, their feasibility would force both ${\lambda }^{T}b$ and ${\mu }^{T}d$ to be nonnegative. This proves the strict separation of disjoint linear polyhedra using Lagrangian duality.

A nonempty linear polyhedron with integer inequality coefficients and right sides bounded by $U\ge 1$ contains a point $x_i=p_i/q_i$ with the displayed bounds. Intersect with an orthant containing a feasible point. Moving along directions annihilating the active constraints, until another constraint becomes active, produces a vertex: the orthant prevents a whole nontrivial line from remaining feasible. At that vertex, choose $n$ independent active inequalities, including coordinate constraints as necessary. Cramer's rule and the Hadamard determinant inequality bound both determinants by $n^{n/2}{U}^n\le (nU{)}^n$. The resulting rational witness has polynomial binary length and is verifiable in polynomial time, proving that integer linear feasibility is in NP.

The recession cone of a nonempty convex set $C$ consists of directions $d$ for which $x+td\in C$ for every $x\in C$ and $t\ge 0$. For a linear polyhedron $P=\{x:Ax\le b\}$ it is exactly $\{d:Ad\le 0\}$. A nonzero recession direction gives an unbounded ray, so a bounded nonempty polyhedron has recession cone $\{0\}$. This excludes spurious zero-scale feasible points in the Charnes-Cooper transformation.

Nonempty disjoint linear polyhedra $P=\{x:Ax\le b\}$ and $Q=\{y:Cy\le d\}$ admit $h$ with a strictly positive separation gap. A phase-I linear program minimizing common constraint violation has positive attained optimum. Its Lagrangian dual problem gives nonnegative $\lambda ,\mu$ with $A^T\lambda +C^T\mu =0$ and ${\lambda }^{T}b+{\mu }^{T}d<0$. Then $h=A^T\lambda$ satisfies $h^{T}x\le {\lambda }^{T}b<-{\mu }^{T}d\le h^{T}y$. The polyhedral hypothesis matters; arbitrary disjoint closed convex sets need not have a positive separation gap.

A system of linear inequalities requires several linear inequalities to hold simultaneously. The notation $Ax\le b$ compares coordinates componentwise, giving one inequality per row of the matrix $A$. Its solution set is the intersection of the corresponding half-spaces. For non-strict inequalities it is a linear polyhedron, which may be empty. For example, $x\ge 1$, $y\ge 1$, $x+y\le 1$ are inconsistent: adding their equivalent forms $-x\le -1$, $-y\le -1$, $x+y\le 1$ gives $0\le -1$. A Farkas certificate for linear inequalities generalizes this cancellation.

For a linear polyhedron $P=\{x\in {\mathbb{R}}^n:Ax\le b\}$, a vertex of a linear polyhedron is a feasible point $p$ at which the normals of the active constraints span ${\mathbb{R}}^n$. Equivalently, $n$ linearly independent active constraints uniquely determine $p$. A linear polyhedron may be unbounded or lower-dimensional; the definition applies in those cases as well as to a convex polytope.

Such a point is an extreme point. Indeed, if $p=\lambda u+(1-\lambda )v$ with $u,v\in P$ and $0<\lambda <1$, every active constraint at $p$ must also be an equality at $u$ and $v$. Selecting $n$ independent active rows forces $u=v=p$. Conversely, if the active normals do not span ${\mathbb{R}}^n$, take a nonzero vector $h$ annihilated by all active rows. The finitely many inactive inequalities have positive slack, so both $p+\epsilon h$ and $p-\epsilon h$ remain feasible for sufficiently small $\epsilon >0$. Their midpoint is $p$, so $p$ is not an extreme point. Thus these notions coincide for a linear polyhedron.