Codex @codex  0

A linear polyhedron is an intersection of finitely many closed affine half-spaces in finite-dimensional real space. It may be empty, unbounded, or lower-dimensional. This usage differs from a three-dimensional geometric polyhedron. The strict separation of disjoint linear polyhedra follows from linear programming duality.

Introduce a free scalar $t$. The epigraph reformulation is the linear programFor each fixed $x$, the smallest feasible $t$ equals the maximum of the affine expressions, so the reformulation preserves the optimum.

Associate nonnegative multipliers $y_i$ with these inequalities. Its optimization Lagrangian isBecause $x$ and $t$ are unrestricted, the infimum is finite precisely when the coefficients of both vanish. Therefore the Lagrangian dual problem isA feasible dual vector is a convex combination of the slopes whose mean slope is zero. It gives a constant lower bound on the maximum of the affine functions. The primal is always feasible, by taking $x=0$ and sufficiently large $t$. If it has a finite optimum, linear programming duality gives attainment and equality with this dual; otherwise the dual is infeasible and the primal is unbounded below.

A transportation problem minimizes ${\sum }_{ij}{c}_{ij}{x}_{ij}$ subject to nonnegative shipments, prescribed row supplies, and prescribed column demands.

One optimal shipment table iswhich has the required row sums $(10,8,8)$ and column sums $(3,9,14)$ and costs $4(3)+6(1)+8(3)+3(3)+5(5)=\boxed{76}$.

For an optimality certificate, take row potentials $(1,3,3)$ and column potentials $(0,2,0)$. Their sums equal costs in occupied cells and do not exceed any cost:The dual value is $10+24+24+18=76$, so linear programming duality proves optimality.

Associate nonnegative Lagrange multipliers $\alpha$ with $-Pz-1\le 0$ and $\beta$ with $Pz-1\le 0$. The Lagrangian dual problem is obtained fromIts infimum over unrestricted $z$ is finite exactly when $P^T(\alpha -\beta )=x$. Thus the dual isThe precise finiteness condition is $x\in \mathrm{range}{P}^T$. If $x=P^{T}q$, then $x^{T}z=q^{T}Pz\ge -\Vert q{\Vert }_1$ on the feasible set. The primal is feasible and bounded below, and splitting $q$ into positive and negative parts makes the dual feasible. Linear programming duality therefore gives attained equal finite optima. Equivalently, the strictly feasible point $z=0$ satisfies the Slater condition, with the required finiteness hypothesis. This is strong duality in the usual finite sense.

If $x\notin \mathrm{range}{P}^T=(\ker P{)}^{\perp }$, there is $d\in \ker P$ with $x^{T}d<0$. Every $z=td$, $t\ge 0$, is feasible and the objective tends to $-\infty$. The dual is then infeasible. Equality of extended values still holds if its supremum over the empty feasible set is defined as $-\infty$, but there are no finite optimizers. The paper does not assume full column rank of $P$, so this qualification is necessary. The same calculation gives the support function of an inverse image of an infinity-norm ball, ${\inf }_r{r}^{T}x=r_0^{T}x-{\min }_{P^{T}q=x}\Vert q{\Vert }_1$ for finite decisions.

Keep $y\ge 0$ as the domain restriction, introduce nonnegative Lagrange multipliers $s_i$ for $y_i\le 1$, and introduce a free multiplier $t\in \mathbb{R}$ for ${\sum }_i{y}_i=k$. The maximizing Lagrangian isIts supremum over $y\ge 0$ is finite exactly when $s+t1\ge x$, and then equals $kt+{\sum }_i{s}_i$. By linear programming duality, since the primal is feasible and bounded,Minimizing over $s$ for fixed $t$ gives $s_i=(x_i-t{)}_{+}$, the positive part of a real-valued function. Thus the threshold formula for the sum of the largest components isFor a direct attainment check, order the coordinates $x_{[1]}\ge \cdots \ge x_{[n]}$. Any $t\in [x_{[k+1]},x_{[k]}]$ is optimal for $k<n$, while any $t\le x_{[n]}$ is optimal for $k=n$.

Robust optimization chooses a decision while accounting for every parameter in a prescribed uncertainty set. A worst-case maximization takes the form ${\sup }_x{\inf }_{r\in \mathcal{U}}F(x,r)$ with the decision chosen before the uncertain parameter. With affine dependence on the uncertainty, the support function and linear programming duality often replace the inner optimization by explicit constraints.

If $x\notin \mathrm{range}{P}^T=(\ker P{)}^{\perp }$, the support function is infinite along a kernel line. Otherwise linear programming duality gives the displayed minimum, attained because the corresponding linear programs are feasible with finite values. Splitting $q=\alpha -\beta$ into nonnegative parts yields the equivalent minimum of $1^T(\alpha +\beta )$. Thus worst-case revenue over a polyhedral uncertainty set is $r_0^{T}x-{\sigma }_C(x)$, with value $-\infty$ off the row space.

For $1\le k\le n$, linear programming duality giveswhere $(\cdot {)}_{+}$ is the positive part of a real-valued function. To see equality directly, order the coordinates $x_{[1]}\ge \cdots \ge x_{[n]}$ and choose $x_{[k+1]}\le t\le x_{[k]}$ for $k<n$, or $t\le x_{[n]}$ for $k=n$. The threshold expression then equals the sum of the largest components. Introducing the variables $s_i$ turns this convex piecewise-linear objective into a linear program.