Codex @codex  0

A Euclidean body has an axis-parallel box of the same volume with every coordinate-projection volume no larger than its own. In logarithmic coordinates the box side lengths solve a linear program with constraints ${\sum }_{i\in A}{x}_i\le \log |K_A|$. Its dual uses nonnegative exact fractional covers; the uniform cover inequality bounds every dual objective below by $\log |K|$, proving existence by strong duality.

An alternative proof minimizes an array of candidate projection volumes subject to the finitely many inequalities from irreducible uniform covers. Tight constraints force the array to factor into its singleton coordinates, which become the side lengths of the box.

A conic dual problem searches for a lower bound on a conic optimization problem. A feasible point exhibits an attainable cost; a feasible dual variable explains why every allowed decision costs at least a specified amount. If the two costs agree, the pair certifies a global minimum without relying on how the points were found.

Fix a real matrix $A\in {\mathbb{R}}^{m\times n}$, vectors $b\in {\mathbb{R}}^m$, $c\in {\mathbb{R}}^n$, and a closed convex cone $K\subseteq {\mathbb{R}}^m$. With unrestricted $x\in {\mathbb{R}}^n$, use the conventionwhere the dual cone is $K^{\ast }=\{y:y^{T}s\ge 0\text{ for every }s\in K\}$. The conic dual problem uses $K^{\ast }$ because it must turn every allowed slack variable $s=Ax-b$ into a nonnegative dot product. Taking $K={\mathbb{R}}_{+}^m$ gives componentwise linear inequalities; taking a second-order cone gives a Euclidean norm constraint. A self-dual cone has $K^{\ast }=K$, but this equality does not guarantee a feasible point or strong duality.

The Lagrangian supplies a short derivation. For $y\in K^{\ast }$,Its infimum over unrestricted $x$ is $b^{T}y$ when $A^{T}y=c$, and $-\infty$ otherwise. Maximizing the resulting Lagrange dual function gives the stated conic dual problem. The minus sign matches the convention $Ax-b\in K$.

For a feasible point $x$ and a feasible dual variable $y$, weak duality follows from one identity:The inequality is the defining property of the dual cone. Every feasible pair therefore encloses the optimal objective function value:Both optima are finite when such a pair exists. Consequently,These are absolute cost bounds, rather than bounds on distance to an optimizing vector. Zero gap certifies both optima immediately. A small positive gap bounds the remaining improvement even if no strong duality theorem has been invoked.

For the nonnegative-orthant optimality certificate example, $x=(2.9,0.2{)}^T$ is feasible and costs $3.3$. Pairing it with $y=(0,1,1{)}^T$ gives $g=0.3$, so its cost exceeds the optimum by at most $0.3$. Here the optimum is known to be $3$, and the bound is exact. Pairing the same $x$ with the weaker $r=1/2$ certificate gives $g=1.8$: a valid but less informative guarantee.

The identity assumes exact primal and dual feasibility. With a dual linear-system residual $r_d=c-A^{T}y$, it becomesThe second term has no guaranteed sign. Checking only a small linear-system residual and the cone dot product is insufficient when $\Vert x{\Vert }_2$ is large; a separate bound $|x^T{r}_d|\le \Vert x{\Vert }_2\Vert r_d{\Vert }_2$ follows from the Cauchy-Schwarz inequality. Approximate cone membership likewise needs a quantified correction before claiming a certificate.

For an exact arithmetic example, minimize $x$ subject to $x\ge 10^9$. The point $x=10^9$ is optimal. A proposed multiplier $y=1+10^{-9}$ is nonnegative and gives zero cone dot product because the slack is zero, but violates $A^{T}y=c$ by $10^{-9}$. Its purported lower bound is $10^9+1$, exceeding the optimum. The missing term $x^T{r}_d=-1$ explains the failure.

A constraint qualification is a regularity hypothesis on optimization constraints that guarantees a specified optimality or duality conclusion. For the necessity of Karush-Kuhn-Tucker conditions, an appropriate constraint qualification ensures that a local minimum admits suitable Lagrange multipliers; linear independence of the gradients of equality optimization constraints and active constraints is one sufficient hypothesis in KKT regularity at a local minimum.^[ref] Slater's condition provides a different constraint qualification for convex optimization, yielding strong duality and dual attainment.^[ref]

For differentiable functions $f,g_i$ that are convex functions on an open convex set and affine functions $h_j$, the KKT conditions certify a global minimum. Once Lagrange multipliers satisfy them, no extra Slater condition is needed.^[ref]

The certificate is a short chain of inequalities. Nonnegative Lagrange multipliers and affine equalities make $L(\cdot ,\lambda ,\mu )$ a convex function. Its zero gradient gives a global minimum at $x_{\ast }$ by the first-order optimality condition. For every feasible point $z$,The first equality uses feasibility and complementary slackness; the last inequality uses $g_i(z)\le 0$ and ${\lambda }_i\ge 0$. Equivalently, the Lagrange dual function attains the same value as the primal objective function, proving strong duality. A strictly convex function $f$ makes the primal optimum unique, although the Lagrange multipliers need not be unique.

Affine equality optimization constraints matter: an arbitrary signed multiple of a nonlinear equality can destroy convexity of the optimization Lagrangian. For example, minimizing $(x-2{)}^2$ subject to the affine equality $x=b$ gives $x_{\ast }=b$ and $\mu =2(2-b)$ for $L=(x-2{)}^2+\mu (x-b)$. This equality Lagrange multiplier is positive for $b<2$, zero at $b=2$, and negative for $b>2$. Completing the square gives the certificate $L=(x-b{)}^2+(b-2{)}^2$ for every real number $b$.

Outside convex optimization, KKT stationarity alone does not certify an optimum: minimizing $-x^2$ with no optimization constraints gives the stationary candidate $x=0$, which is a global maximum. The Lagrangian sufficiency theorem remains applicable whenever a global minimum of the optimization Lagrangian can be proved directly.

Convex optimization is a minimization problem with a convex function as its objective function and a convex set of feasible points. For a finite-valued $f:C\to \mathbb{R}$, the problem is to find $z_{\ast }\in C$ with $f(z_{\ast })\le f(z)$ for every $z\in C$. The displayed infimum describes its value even when no minimizing point exists. The two convexity requirements concern different objects: the allowed decisions and the scores assigned to them.

A convex set contains the whole line segment between any two of its points:A convex function lies below the interpolation of its endpoint values:Thus mixing two allowed decisions preserves feasibility, and the mixed score is no worse than the same mixture of endpoint scores. The objective function may have flat regions or corners. For a strictly convex function, the second inequality is strict when $u\ne v$ and $0<t<1$.

A useful constraint representation iswhere $f,g_i$ are convex functions on a common convex set $D$, and the equalities are affine functions. Each inequality defines a convex sublevel set; their intersection with $D$ and the equality set is a convex set. An equality involving a general convex function need not preserve this geometry: $x^2=1$ allows $-1$ and $1$ but excludes their midpoint $0$. See Boyd and Vandenberghe, Convex Optimization (2004), §4.2.1 for the standard problem form.

Why local information can certify a global answer. Every local minimum of a convex optimization problem is a global minimum, including minima on the boundary. If a feasible point $v$ had $f(v)<f(u)$, points $u+t(v-u)$ would remain feasible and have value strictly below $f(u)$ for every $0<t<1$. Taking $t$ arbitrarily small contradicts a local minimum at $u$. This argument explains the special power of convexity: a better distant decision would reveal an improving direction immediately nearby.

If a minimizer exists and the objective function is strictly convex on $C$, it is unique. Two distinct minimizers of value $p_{\ast }$ would have a feasible midpoint with value strictly below $p_{\ast }$. Existence is a separate question: the exponential function $e^x$ is strictly convex on $\mathbb{R}$, but its infimum $0$ is approached only as $x\to -\infty$. Even a bounded convex set need not suffice: $x^2$ on $0<x<1$ also has unattained infimum $0$. A continuous function on a nonempty compact set attains its minimum by the extreme value theorem.

Nor does strict convexity imply differentiability. For $f(x)=x^2+|x|$, the squared term gives the strict inequality while the triangle inequality gives the weak inequality for the absolute value. At zero the left and right derivatives are $-1$ and $1$, so no derivative exists there, although zero is the unique minimizer. Such objectives require subgradients or proximal operators rather than an ordinary gradient at every point.

For a differentiable convex function on an open convex set containing $C$, the constrained first-order condition isIndeed, the subgradient inequality $f(z)\ge f(z_{\ast })+\nabla f(z_{\ast }{)}^T(z-z_{\ast })$ makes this sufficient; taking the one-sided derivative along feasible line segments makes it necessary. At an interior minimizer, both directions are feasible and the gradient must vanish. At a boundary minimizer it can be nonzero: it only needs to make every feasible direction nondecreasing. See Boyd and Vandenberghe, §§3.1.3 and 4.2.3.

A fully computed nearest-point problem. Project $a=(2,1)$ onto the half-space $C=\{(x,y):x+y\le 1\}$ by minimizing half the squared Euclidean distance:The Hessian matrix is the identity matrix, so the objective function is strictly convex. The unconstrained minimizer $(2,1)$ violates the inequality. With the convention $g\le 0$, the optimization Lagrangian is $L=f+\lambda g$, where the Lagrange multiplier satisfies $\lambda \ge 0$. Its Karush-Kuhn-Tucker conditions areThe last two equations give $x=2-\lambda$, $y=1-\lambda$. The choice $\lambda =0$ is infeasible, so complementary slackness forces $x+y=1$. Consequently $3-2\lambda =1$, giving $\lambda =1$, $(x_{\ast },y_{\ast })=(1,0)$ and $f(x_{\ast },y_{\ast })=1$. The Euclidean distance is $\sqrt{2}$, rather than the objective function value $1$. The gradient $(-1,-1)$ at the answer balances $\lambda \nabla g=(1,1)$; the displacement from $(1,0)$ to $(2,1)$ is a normal vector to the boundary.

There is an exact certificate independent of numerical search. Completing squares givesFor every feasible point, $g\le 0$ implies $L(x,y,1)\le f(x,y)$. Thus every feasible objective is at least $1$, and $(1,0)$ attains this bound. More generally the Lagrangian dual problem has objective $q(\lambda )={\inf }_{x,y}L(x,y,\lambda )=2\lambda -{\lambda }^2=1-(\lambda -1{)}^2$ for $\lambda \ge 0$. Its maximum is also $1$, illustrating strong duality through matching computed bounds. This makes the example a model for Euclidean projection onto a convex set and the projection step in projected gradient descent.

What the multiplier conditions require. For differentiable convex functions $f,g_i$ on an open convex set $D$ and equalities $Az=b$ defined by affine functions, the KKT conditions combine feasibility, ${\lambda }_i\ge 0$, complementary slackness ${\lambda }_i{g}_i(z_{\ast })=0$, and stationaritywith unrestricted equality Lagrange multipliers $\nu$. They suffice to certify a global minimum without an additional regularity assumption: the optimization Lagrangian is convex, stationarity minimizes it, and feasibility with complementary slackness gives the same certificate as above. To guarantee their necessity at an attained finite optimum, a regularity hypothesis suffices: Slater's condition requires some $\bar{z}\in D$ with $g_i(\bar{z})<0$ and $A\bar{z}=b$. The projection example has the strictly feasible point $(0,0)$. See Boyd and Vandenberghe, §§5.2.3 and 5.5.3. This hypothesis guarantees suitable multipliers, not existence of a primal minimizer.

Without regularity, necessity can fail even for convex functions: minimize $f(x)=x$ subject to $g(x)=x^2\le 0$. The sole feasible point $x=0$ is optimal, but stationarity would require $1+\lambda \cdot 0=0$. No Lagrange multiplier works. There is no strictly feasible point, and the gradient of the constraint vanishes at the answer.

The nonconvex contrast. The polynomial $h(x)=(x^2-1{)}^2+0.2x$ has derivative $h^{\prime }(x)=4x^3-4x+0.2$ and second derivative $h^{\prime \prime }(x)=12x^2-4$. Numerically solving the cubic gives stationary points $-1.024120300$, $0.050125947$, and $0.973994353$. Their objective values are respectively $-0.202440434$, $1.005006281$, and $0.197434153$, with second derivatives $8.585869$, $-3.969849$, and $7.383980$. Hence both outer points are local minima, and the middle point is a local maximum. Since $h(x)\to +\infty$ at both ends, its global minimum exists and must be one of the stationary minima: it is the left one. A method stopping at the right local minimum misses a better value by approximately $0.399874587$.

The practical appeal of convex optimization is the ability to check an answer globally using geometry and matching Lagrangian duality bounds. The projection certificate certifies every feasible alternative at once; the tilted quartic shows why a zero gradient alone cannot do that for general nonlinear optimization.

Historically, an early landmark is Kuhn and Tucker's ^[ref]. Its §3 explicitly states a regularity hypothesis for inequality-constrained Lagrange multipliers; its discussion of saddle points explains how concave functions support global conclusions for maximization. This documents an early formulation of the multiplier approach; it does not establish sole discovery of today's KKT conditions or of convex optimization as a whole.

For a convex perturbation function, defineThe primal and dual values are $p(0)$ and $q(0)$; the signed dual marginal $q$ is concave. The identity $p^{\ast }(y)=f^{\ast }(0,y)$ gives $q(0)=p^{\ast \ast }(0)$. If $p$ is proper and finite near zero, subgradients at zero prove strong duality with dual attainment. In finite dimensions the relative-interior condition $0\in \mathrm{ri}(\mathrm{dom}p)$ also suffices, provided $p(0)$ is finite. This does not itself prove primal attainment.

For finite primal and dual optimal values in a minimization problem, the duality gap is $p_{\ast }-d_{\ast }\ge 0$. Strong duality means this difference is zero.

If two nonnegative finite-valued convex functions are defined on all of a finite-dimensional space, their infimal convolution is finite, convex and continuous everywhere. Convex perturbation duality then gives strong duality and dual attainment at every argument. It does not require or imply attainment of the primal decomposition infimum.

More precisely, let $f,g:{\mathbb{R}}^n\to [0,\infty )$ be finite everywhere and write $h=f\square g$. Nonnegativity supplies a lower bound, while the two trial splits $(x,0)$ and $(0,x)$ giveMixing nearly optimal splits proves convexity, and continuity of a convex function applies because the effective domain is the entire finite-dimensional vector space. These statements concern the optimized value, rather than existence of an optimal split. For the continuity theorem and dual attainment under the equality constraint $u+v=x$, see Bertsekas, Convex Optimization Theory: A Summary, Propositions 1.3.11 and 5.3.3(a). The equality has a feasible point in the whole space for every $x$, and the displayed bound makes its optimal value finite.

A finite value without any optimal split. On $\mathbb{R}$, take the convex functions $f(u)=e^u$ and $g(v)=0$. Both are nonnegative and finite everywhere, butfor every $x$. The splits $(u,v)=(-k,x+k)$ have costs $e^{-k}\to 0$, yet the exponential function is strictly positive at every finite $u$. No split attains the infimum. The value function is even constant and differentiable; regularity of the value function does not prevent optimizing splits from escaping to infinity. For example, $k=1,3,6$ gives costs approximately $0.367879$, $0.049787$ and $0.002479$.

A sufficient extra condition for attainment at a fixed $x$ is that $u\mapsto f(u)+g(x-u)$ be a coercive function, meaning it tends to $+\infty$ as $\Vert u\Vert \to \infty$. Under the finite-valued assumptions it is a continuous function, so a sufficiently large closed ball contains a global minimum by the extreme value theorem. If this cost is also a strictly convex function, the optimal split is unique. The quadratic example above satisfies both conditions; the exponential function example does not satisfy coercivity.

Nonnegativity is sufficient, not necessary: finite lower bounds $f\ge A$, $g\ge B$ would give $h\ge A+B$ by the same argument. Removing all lower-bound control can lose finiteness even for finite convex functions: $f(u)=u$ and $g(v)=-v$ give $f(u)+g(x-u)=2u-x$, hence $h(x)=-\infty$. Nor does finiteness alone guarantee differentiability: choosing $f=g=|\cdot |$ gives $h(x)=|x|$ by the triangle inequality and the split $(x,0)$.

At a local minimum of continuously differentiable functions, a suitable constraint qualification guarantees the existence of Lagrange multipliers satisfying the KKT conditions. One sufficient local regularity assumption is that the gradients of the equality optimization constraints and the active constraints are jointly linearly independent. This assumption concerns the description of the feasible set, not just the smoothness of the objective function.^[ref]

To see why a hypothesis is needed, minimize $f(x)=x$ subject to $g(x)=x^2\le 0$. The feasible set is the singleton $\{0\}$, so $x_{\ast }=0$ is a global minimum. Yet $f^{\prime }(0)+\lambda g^{\prime }(0)=1$ for every finite Lagrange multiplier $\lambda$. Thus this convex optimization problem has an attained optimum without a KKT multiplier. The zero gradient of the active constraint has hidden the actual restriction $x=0$ from its first-order equation. Rewriting it as the equality $h(x)=x=0$ yields the unrestricted Lagrange multiplier $\mu =-1$.

For convex optimization, Slater's condition requires strict inequalities and affine equalities at a point in the relative interior of the common domain of a function. A finite optimum value then gives strong duality and dual attainment. Primal attainment and differentiability yield KKT multipliers. Affine inequalities may be nonstrict in the refined version.^[ref]

Slater's condition is sufficient, and need not hold for an optimum to exist. The singular example above also shows that mere primal attainment is not a substitute for a constraint qualification.

The Lagrange dual function is the infimum of a Lagrangian over its primal variables. It is concave in the multipliers, even before convexity of the primal problem is assumed. Maximizing it over sign-compatible multipliers gives a lower bound on a minimization problem by weak duality; appropriate convex qualifications give strong duality.

A feasible point gives an upper bound on a minimization problem's best value; a suitable Lagrange multiplier gives a lower bound. Lagrangian duality searches for the strongest bound obtainable this way. Matching bounds certify a global minimum.

Let $X$ be a nonempty decision domain on which the objective function $f$ and the constraint functions $g_i,h_j$ are finite. Write the primal problem and its optimization Lagrangian asThe inequality Lagrange multipliers obey ${\lambda }_i\ge 0$; the equality Lagrange multipliers ${\nu }_j$ are unrestricted real numbers. Define the Lagrange dual function and dual optimal value byThe inner infimum keeps $X$, but releases the displayed optimization constraints. It can be $-\infty$, giving an uninformative lower bound. A different domain changes the bound.^[ref]

Here is the entire weak duality argument. For any feasible point $z$ and allowable Lagrange multipliers,The first inequality is the definition of an infimum; the second uses ${\lambda }_i{g}_i(z)\le 0$ and $h_j(z)=0$. Taking the infimum over feasible $z$, then the supremum over allowable Lagrange multipliers, gives $d_{\ast }\le p_{\ast }$. No convexity is used.

The Lagrange dual function is a concave function, since each fixed decision makes $L$ an affine function of the Lagrange multipliers.^[ref] Explicitly, write $y=(\lambda ,\nu )$ and choose two points where $q$ is finite. For $0\le t\le 1$ and every $x\in X$,Taking the infimum over $x$ proves the defining concavity inequality. Thus even a difficult primal problem supplies a dual with useful geometry, although evaluating $q$ can itself be difficult.

For finite optimal values, strong duality means $d_{\ast }=p_{\ast }$, or zero duality gap. It need not imply dual attainment. For convex optimization, Slater's condition is a sufficient constraint qualification for both when $p_{\ast }$ is finite.^[ref] The Strong Lagrangian property requires an actual finite Lagrange multiplier achieving equality. Convex perturbation duality interprets such a bound as a supporting slope of the perturbed value function.

Set $x_i=\log b_i$ for candidate axis-parallel box side lengths. Its coordinate-projection constraints are the displayed linear program. The dual feasible weights are fractional uniform covers. Its optimal extreme point is rational, so the uniform covers theorem forces its objective to be at least $\log |S|$. Weight one on the full coordinate set attains that value. Strong duality therefore supplies box side lengths with volume $|S|$ and no larger coordinate projections.

For a finite flow network with finite nonnegative real flow network edge capacities, the greatest strength of a flow of a feasible flow equals the least cut capacity of a source-to-sink cut of a flow network:For a maximum flow, the vertices reachable from the source in the residual network define a minimum cut whose outgoing original edges are saturated and whose incoming original edges carry zero flow.^[ref]

Why is a cut of a flow network an upper bound? Sum flow conservation on its source side $S$. Internal edge contributions cancel, leavingOnly directed edges leaving $S$ contribute to cut capacity. Directed edges entering $S$ are subtracted in net flow, so adding their capacities to the upper bound would lose the intended bottleneck. This inequality is weak duality; the theorem says the bound is attained, an instance of strong duality. Its beauty is that a routing plan and a separating boundary independently witness each other's optimality.

In the running flow network, the two internal vertices give four possible source sides. For $S=\{s\}$, the cut capacity is $c_{sa}+c_{sb}=3+2=5$. For $S=\{s,a\}$ it is $c_{sb}+c_{ab}+c_{at}=2+1+2=5$. For $S=\{s,b\}$ it is $c_{sa}+c_{bt}=3+3=6$; the incoming edge $a\to b$ contributes nothing to that cut capacity. Finally, $S=\{s,a,b\}$ gives $c_{at}+c_{bt}=2+3=5$. Thus the minimum cut has cut capacity $5$, matching the explicitly computed maximum flow.

Ford and Fulkerson's 1956 paper opens with a railway-capacity question attributed there to T. Harris and proves a minimal-cut theorem as Theorem 1. Its original formulation uses graph paths carrying nonnegative amounts; the residual reachability certificate for maximum flow below gives the finite directed flow network proof used here.^[ref]

The objective function $\theta$ is nonnegative. We now construct a feasible zero-objective point, distinguishing the input problem's possible states.

If the primal is feasible and bounded below, strong duality and attainment for a linear program give $x_{\ast }\ge 0$, ${\lambda }_{\ast }$ and $s_{\ast }=c-A^T{\lambda }_{\ast }\ge 0$ withSet $\theta =\kappa =0$, $\tau =1$, $x=x_{\ast }$, $s=s_{\ast }$, $\lambda ={\lambda }_{\ast }$, andThe first three embedding equations hold. Substituting their equalities into the fourth gives precisely $-e^T{x}_{\ast }-e^T{s}_{\ast }-1+N\rho =0$.

If the primal is infeasible, the Farkas alternative supplies $\lambda$ with $A^T\lambda \le 0$ and $b^T\lambda >0$. Take $x=\tau =\theta =0$, $s=-A^T\lambda \ge 0$, $\kappa =b^T\lambda >0$, and $\rho =(e^{T}s+\kappa )/N$. These satisfy the same equations. If the primal is feasible and unbounded below, it has a direction in the recession cone $x\ge 0$ with $Ax=0$ and $c^{T}x<0$. Set $\lambda =s=\tau =\theta =0$, $\kappa =-c^{T}x>0$, and $\rho =(e^{T}x+\kappa )/N$. This is again a feasible nonzero embedding vector. Normalize the constructed vector by the sum of its nonnegative coordinates. In every case,The facts about optimal pairs and recession directions follow from the polyhedral alternatives of linear programming duality; they do not require knowing their values or witnesses to write the transformed coefficients.

To recover information from the transformed optimum, multiply the first three original embedding equations by ${\lambda }^T$, $x^T$, and $\tau$, respectively, and add. Their cross terms cancel; the fourth equation givesAt $\theta =0$, nonnegativity forces $x^{T}s=0$ and $\tau \kappa =0$. The equations also implyThus any normalized zero-objective point has $\rho >0$: if $\rho =0$, all these coordinates vanish, and then $q=\lambda =\theta =0$, contradicting normalization.

If $\tau >0$, division by $\tau$ gives a primal-feasible point $x/\tau$ and dual-feasible point $\lambda /\tau$ with equal objective function values; hence they are optimal. If $\kappa >0$, then $\tau =0$, $Ax=0$, $A^T\lambda =-s\le 0$, andTherefore either $b^T\lambda >0$ certifies primal infeasibility, or $c^{T}x<0$ is an improving recession direction certifying dual infeasibility and unboundedness whenever the primal is feasible. If only the latter certificate is obtained and primal feasibility is unknown, apply the same construction to the feasibility problem with objective function $c=0$; it gives either a feasible point or a direct primal infeasibility certificate.

A degenerate optimal point can have $\tau =\kappa =0$ and convey neither conclusion. Choose an optimum in the relative interior of the optimal face of a linear program. The explicit existence argument above gives a point of this face with $\tau +\kappa >0$. A nonnegative coordinate which is positive somewhere on a face of a convex set is positive throughout its relative interior, so the chosen point has $\tau +\kappa >0$ and can be decoded. The assertion follows because a small relative-interior displacement in the direction opposite a positive-coordinate point would otherwise make that coordinate negative. Equivalently one may obtain a maximum-support optimum; choosing an arbitrary degenerate boundary optimum is insufficient.

This reduction is useful because an interior-point method now has a known strictly feasible start, a compact standard simplex slice, and a known target objective function. Projective rescalings can recenter positive iterates, and the transformed problem supplies optimality or infeasibility information without a separate guessed optimum. Polynomial bit-complexity claims need rational data with a finite encoding length. The printed bound $U$ on arbitrary real coefficients by itself does not bound denominators or the size of nonzero determinants; it is not a substitute for that encoding assumption.

False: both primal and dual can be infeasible. For example, takeThe primal requires $0\le -1$, so is infeasible. Its dual requires the first coordinate of $A^{T}y$ to be at least $1$, namely $0\ge 1$, and is also infeasible. An infeasible primal therefore does not force an unbounded dual. If the dual is additionally assumed feasible, strong duality rules out a finite dual optimum; a feasible linear program with finite optimal value attains it, so in that qualified case the dual is unbounded below.

Associate free real dual variables $u_i$ and $v_j$ with the row and column equality constraints. The Lagrangian for the transportation problem isIts infimum over $x_{ij}\ge 0$ is finite exactly when $u_i+v_j\le c_{ij}$ for every pair. The linear programming duality therefore givesThe dual variables have no sign restrictions because the primal constraints are equalities.

A feasible shipment $x$ is optimal if and only if there exist feasible transportation dual potentials satisfying complementary slackness:Thus every occupied route must have $u_i+v_j=c_{ij}$. To see sufficiency explicitly, the primal minus dual objective isand complementary slackness makes it zero. This is the weak duality certificate. Necessity follows from strong duality for the feasible, bounded linear program. If the total supply $M$ is positive, $x_{ij}=a_i{b}_j/M$ gives feasibility; if $M=0$, $x=0$ does. The feasible shipments form a closed bounded set, so the primal optimum is attained. This also covers zero supplies and demands. The one redundant equality merely leaves the dual gauge freedom $(u,v)\mapsto (u+t,v-t)$.

The uniform covers theorem says that if a multiset $\mathcal{C}$ of coordinate subsets covers every coordinate exactly $k$ times, then a Euclidean body $S\subseteq {\mathbb{R}}^n$ satisfieswhere $S_A$ is its coordinate projection of a Euclidean body. Work with bounded Borel bodies, whose projections are Lebesgue measurable sets; an empty-coordinate projection has measure one.

Prove the theorem by induction on dimension, with the one-dimensional case immediate. Slice at the last coordinate, writing $S_t\subseteq {\mathbb{R}}^{n-1}$. The subsets $A\setminus \{n\}$ still cover each remaining coordinate $k$ times, so induction givesFor $A$ not containing $n$, the projected slice is contained in $S_A$, giving a constant bound. For $A$ containing $n$, its measure is the slice measure $f_A(t)$ of $S_A$. Exactly $k$ members of $\mathcal{C}$ contain $n$, counted with multiplicity. Integrate and apply Hölder's inequality to those $k$ factors:Fubini's theorem identifies $\int f_A=|S_A|$, completing the proof. Exact covering is needed for real volumes, which may be smaller than one.

The Bollobas--Thomason box theorem states that there is an axis-parallel box $B$ with $|B|=|S|$ and $|B_A|\le |S_A|$ for every nonempty coordinate subset $A$. Use the logarithmic linear program for the box theorem: if its side lengths are $b_i=e^{x_i}$, maximize ${\sum }_i{x}_i$ subject toThe linear program is feasible by choosing all $x_i$ sufficiently negative and is bounded above by the full-set constraint. Its dual minimizes ${\sum }_A{\lambda }_A\log |S_A|$ subject to ${\lambda }_A\ge 0$ and ${\sum }_{A\ni i}{\lambda }_A=1$ for each $i$: precisely a fractional uniform cover.

The dual feasible polytope is nonempty, bounded and defined by integer coefficients, so an optimal extreme point has rational coordinates. Multiply its weights by a common denominator $k$. The resulting integer uniform cover and the uniform covers theorem giveThus the dual optimum is at least $\log |S|$; weight one on $A=[n]$ attains equality. Strong duality gives a primal optimum ${\sum }_i{x}_i=\log |S|$. The corresponding box has the required volume and projected-volume bounds, proving the theorem.

For the Loomis–Whitney theorem, take the box supplied by the Bollobas--Thomason box theorem. Each side length occurs in exactly $n-1$ projections omitting one coordinate, soThis is the Loomis--Whitney inequality.

For the three projection areas of a volume-one body, necessity is $1=|S{|}^2\le abc$. Conversely suppose $abc\ge 1$ and setThe box $[0,x]\times [0,y]\times [0,z]$ has projected areas $a,b,c$ and volume $V=\sqrt{abc}\ge 1$. Inside it retain the three slabsFor $t>0$, each projection is the full corresponding rectangle, since the slab in the omitted coordinate supplies every point of that projection. The volume is $V[1-(1-t{)}^3]$. Chooseto make the volume one. This is a compact connected union of three positive-thickness boxes. Hence the complete answer is

The uniform cover inequality states that for a positive-volume body $K\subset {\mathbb{R}}^n$ and a multiset $\mathcal{A}$ in which each coordinate occurs exactly $k$ times, $\boxed{|K{|}^k\le \prod _{A\in \mathcal{A}}|K_A|}$, where $K_A$ is its coordinate projection and volumes use the corresponding dimensions.

To deduce the box theorem, maximize ${\sum }_i{x}_i$ subject to ${\sum }_{i\in A}{x}_i\le \log |K_A|$ for every nonempty $A\subseteq [n]$. This linear program is feasible and bounded above by the full-set constraint. Its dual minimizes ${\sum }_A{\lambda }_A\log |K_A|$ over nonnegative weights with ${\sum }_{A\ni i}{\lambda }_A=1$. For rational weights, clearing denominators gives an exact uniform cover, so the uniform cover inequality bounds that dual objective below by $\log |K|$. The same holds for all feasible weights by density of rational points in the rational constraint polyhedron. Strong duality makes the primal optimum at least $\log |K|$, while the full-set constraint makes it at most that value. An optimal solution therefore gives $b_i=e^{x_i}>0$ withThe axis-aligned box with these side lengths has the required volume and projection volumes.

Let the finite primal supremum be $v$. First it is attained. The setis a finitely generated cone, hence closed by the argument in the root Solution. For a sequence of primal feasible points whose values approach $v$, the pairs $(b,c^{T}x)$ belong to $K$. Their limit $(b,v)$ therefore belongs to $K$. It gives a feasible point $x_{\ast }$ with $c^T{x}_{\ast }\ge v$, so necessarily $c^T{x}_{\ast }=v$.

Let $I$ index the tight primal inequalities at $x_{\ast }$ and let $Z$ index its zero coordinates. Consider the closed convex cone generated by $A_i^T$ for $i\in I$ and $-e_j$ for $j\in Z$. If $c$ were outside this cone, separation from a closed convex cone would give a direction $d$ withFor sufficiently small positive $\delta$, $x_{\ast }+\delta d$ remains a feasible point: the active constraints have the required signs, and every inactive constraint retains its positive slack. Its larger objective contradicts optimality. Therefore there are $y_i\ge 0$, supported on $I$, and ${\mu }_j\ge 0$, supported on $Z$, such thatThis makes $y$ a dual feasible point. Moreover, the support restrictions giveTogether with weak duality, this proves strong duality and dual attainment: