Codex @codex  0

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 maximizing-dual convention. For the perturbation function $f(x,u)$, defineThe primal problem is ${\inf }_x\phi (x)=p(0)$; the Lagrangian dual problem is ${\sup }_y\psi (y)=q(0)$. The sign convention makes the dual marginal $q$ concave for jointly convex data; some formulations negate $q$ to express a minimization problem.

The central convex perturbation duality calculation isThe last inequality is weak duality. A sufficient finite-dimensional condition for strong duality with dual attainment is: $f$ is jointly proper and convex, $p$ is proper with $p(0)$ finite, and $p$ is finite on a neighborhood of zero. More generally $0\in \mathrm{ri}(\mathrm{dom}p)$ suffices.

Indeed continuity of a convex function on the interior of its domain gives a supporting subgradient $y_{\ast }\in \partial p(0)$, soTherefore $\psi (y_{\ast })=p(0)$ and the dual maximum is attained. This qualification establishes equality and dual attainment; it does not by itself establish a primal minimizer.

For each fixed $z$, choose the convex perturbation functionIt is jointly convex and has marginalBecause $h$ and $k$ are nonnegative and finite everywhere,for every $w$. The inf-convolution is convex: for approximate decompositions of $w_1,w_2$, take their convex combination and use convexity of both costs; then let their approximation errors tend to zero. Thus $F$ is a finite convex function on all of ${\mathbb{R}}^n$, hence continuous everywhere. In particular $p_z$ is proper and finite near zero, so the qualification in the previous solution applies at every $z$:This is strong duality for a finite-valued infimal convolution.

No primal attainment was used. For example $k(x)=e^x$ and $h(x)=0$ meet all the stated assumptions, but $F(z)=0$ is approached only as $x\to -\infty$. This illustrates why a proof based on an assumed minimizing decomposition would be incomplete. The printed functions are real-valued everywhere, not merely extended-real; that distinction supplies continuity and the strong-duality qualification.

Compute the convex conjugate of $f_z$ at a general pair $(v,y)$. With $w=z+u-x$, the independent variables become $(x,w)$ and $u=w+x-z$, soTherefore the Lagrange dual function isUsing strong duality from the preceding solution givesEquivalently the conjugate of an infimal convolution is $F^{\ast }=k^{\ast }+h^{\ast }$, and the continuous convex $F$ equals its biconjugate.

For practical subgradient computation, minimize the known convex dual objectiveEvery optimizer, and only an optimizer, belongs to $\partial F(z)$ by Fenchel–Young inequality. The full characterization isThis is infimal-convolution dual subgradients; the set is nonempty because $F$ is finite convex everywhere. If both conjugates are differentiable at the optimizer, solve $\nabla k^{\ast }(y)+\nabla h^{\ast }(y)=z$. For nonsmooth conjugates, use the displayed aggregate subdifferential or a convex minimization algorithm. Replacing it by $\partial k^{\ast }(y)+\partial h^{\ast }(y)$ requires the usual subdifferential sum rule qualification; it is not automatically justified solely by knowing the two conjugates.

Use $z\in {\mathbb{R}}^m$ for the perturbation variable and $y\in {\mathbb{R}}^m$ for its dual variable. The full Fenchel conjugate is $f^{\ast }(v,y)={\sup }_{x,z}(⟨v,x⟩+⟨y,z⟩-f(x,z))$. One signed-marginal convention isThe primal problem of convex perturbation duality is ${\inf }_x\phi (x)=p(0)$ and its dual problem of convex perturbation duality is ${\sup }_y\psi (y)=q(0)$. The signed dual marginal $q$ is concave; some conventions instead use $-q$ as a convex marginal. The definitions above fix all signs. Weak duality follows from $f(x,0)+f^{\ast }(0,y)\ge 0$. Also $p^{\ast }(y)=f^{\ast }(0,y)$, so $q(0)=p^{\ast \ast }(0)$.

For a sufficient strong duality condition, assume $f$ is jointly proper convex, $p$ is proper with $p(0)$ finite, and $p$ is finite and continuous in a neighborhood of $0$. More generally $0\in \mathrm{ri}(\mathrm{dom}p)$ suffices in finite dimensions. A supporting subgradient $y^{\ast }\in \partial p(0)$ then exists, andThus the dual is attained with no gap. This condition does not by itself assert attainment of the primal infimum; that needs an additional compactness or coercivity argument.

The same subgradient describes sensitivity analysis in convex perturbation duality: $p(z)\ge p(0)+⟨y^{\ast },z⟩$ bounds the optimum's change under perturbation. When $p$ is finite convex near zero, its one-sided directional derivative is $p^{\prime }(0;d)={\max }_{y\in \partial p(0)}⟨y,d⟩$. If $\partial p(0)=\{y^{\ast }\}$, then $p$ is differentiable there andThese conditions allow first-order sensitivity predictions; without differentiability the subgradient set gives directional bounds. Multipliers can measure the value of relaxing constraints, quantify changes in noise tolerance, and guide parameter choice without resolving every perturbed problem. For the constraint convention in part (b), the noise-budget sensitivity is negative the nonnegative constraint multiplier.

Let $r(u)=\Vert u-g{\Vert }_2^2$ and fix the reference noise budget $\sigma$. Define the convex perturbation functionPositive $z$ increases the allowed squared noise level. The feasible epigraph set $r(u)\le \sigma +z$ is convex and closed, so this is a proper lower semicontinuous jointly convex perturbation. Writing the inequality indicator as a supremum over its multiplier givesThe Lagrange dual function is $d(\lambda )={\inf }_{u}L(u,\lambda )$ for $\lambda \ge 0$. In the signed convex conjugate convention of part (a), $y=-\lambda$; positive $y$ gives dual objective $-\infty$ because the perturbation can be made arbitrarily large.

The feasible ball is nonempty and compact, so lower semicontinuity of total variation gives a primal minimizer. For $\sigma >0$, $u=g$ satisfies $r(g)=0<\sigma$, providing the Slater condition. Total variation is finite everywhere in the given discretization and hence continuous. Strong duality and dual attainment give a finite optimal ${\lambda }^{\ast }\ge 0$. The pair satisfies the Karush-Kuhn-Tucker conditionsEquivalently,Thus the set of saddle points is nonempty. Compactness handles primal attainment, while strict feasibility supplies a finite multiplier; these are distinct steps. An inactive constraint can yield ${\lambda }^{\ast }=0$. At $\sigma =0$, feasibility still forces $u=g$, but this strict-feasibility argument does not apply.

A kernel support vector machine constructs a large-margin classifier in a feature Hilbert space. Given training points $x_i$ and labels $y_i\in \{-1,1\}$, choose a feature map $\Phi :X\to \mathcal{H}$ and an affine score $f(x)=⟨w,\Phi (x)⟩+b$. Prediction is the sign of the score. Normalizing the functional margin to one makes the closest separating geometric margin $1/\Vert w\Vert$, and the full margin between the two supporting hyperplanes is $2/\Vert w\Vert$. Maximizing that margin therefore minimizes $\frac{1}{2}\Vert w{\Vert }^2$.

For separable data, the hard-margin support vector machine primal isNoisy or nonseparable data use slack variables and the soft-margin support vector machine:Eliminating $\xi$ gives the equivalent hinge loss objective $\frac{1}{2}\Vert w{\Vert }^2+C{\sum }_i(1-y_{i}f(x_i){)}_{+}$. The parameter balances margin size against violations; it is not a hard bound on their number. The bias is unpenalized here, which determines the equality constraint in the dual.

Attach multipliers ${\alpha }_i\ge 0$ to $1-{\xi }_i-y_{i}f(x_i)\le 0$ and ${\eta }_i\ge 0$ to $-{\xi }_i\le 0$. The Lagrangian isStationarity gives $w={\sum }_i{\alpha }_i{y}_i\Phi (x_i)$, ${\sum }_i{\alpha }_i{y}_i=0$ and $C-{\alpha }_i-{\eta }_i=0$. Eliminating $w,b,\xi$ yieldswhere $k(x,x^{\prime })=⟨\Phi (x),\Phi (x^{\prime })⟩$ is a positive-definite kernel, meaning positive semidefinite Gram matrices. The hard-margin dual is the same objective with only ${\alpha }_i\ge 0$, without the upper bound. Soft-margin strict feasibility follows by taking $w=b=0$ and all ${\xi }_i>1$, so strong duality and the Karush-Kuhn-Tucker conditions apply. For separable hard-margin data a separator can be rescaled to give strict margins, supplying the analogous qualification. Although the feature space may be infinite dimensional, projecting $w$ onto the finite span of the training feature vectors preserves scores and cannot increase its norm, so this optimization reduces to a finite span.

The complementary slackness relations arePoints with ${\alpha }_i>0$ are support vectors. If $0<{\alpha }_i<C$, then ${\xi }_i=0$ and $y_{i}f(x_i)=1$; such a point gives $b=y_i-{\sum }_j{\alpha }_j{y}_{j}k(x_j,x_i)$. A point with ${\alpha }_i=C$ can lie inside the margin or be misclassified, while ${\alpha }_i=0$ contributes no term to $w$. If no coefficient lies strictly between the bounds, an admissible bias must be obtained from the KKT inequalities, rather than dividing by a nonexistent margin vector. Bias and dual coefficients can be nonunique even when the optimal feature-space weight is unique.

The kernel trick operates both during training and prediction. The dual optimization uses only the Gram matrix $K_{ij}=k(x_i,x_j)$, so the feature vectors need not be formed. Prediction likewise usesA nonlinear kernel therefore makes a linear separator in feature space represent a nonlinear boundary in input space. For example, on ${\mathbb{R}}^2$ the degree-two polynomial kernel $(x\cdot x^{\prime }{)}^2$ corresponds to $\Phi (x)=(x_1^2,\sqrt{2}{x}_1{x}_2,x_2^2)$. Gaussian kernels yield infinite-dimensional feature spaces. An arbitrary similarity is not automatically a valid kernel: for every finite collection and real coefficients $a_i$, one needs ${\sum }_{i,j}{a}_i{a}_{j}k(x_i,x_j)\ge 0$. This makes the dual quadratic form positive semidefinite and the maximization concave.

Mercer's theorem gives a spectral realization under its additional analytic hypotheses. For a continuous symmetric positive-semidefinite kernel on a compact domain with a finite full-support measure, the integral operator $(T_{k}f)(x)=\int k(x,x^{\prime })f(x^{\prime })d\mu (x^{\prime })$ is compact, self-adjoint and positive. The Mercer expansion iswith the standard uniform convergence conclusions under these hypotheses. Since ${\sum }_j{\lambda }_j{e}_j(x{)}^2=k(x,x)<\infty$, the nonlinear feature mapis well defined. This explains the connection of Mercer kernels to Hilbert space features, rather than treating the kernel trick as a purely formal substitution.

The finite-Gram positivity condition is more general than this compact-domain spectral theorem. Every such kernel generates a Reproducing kernel Hilbert space: on finite sums of kernel sections definequotient out zero-norm elements, and complete. The resulting space satisfies the reproducing property $h(x)=⟨h,k(x,\cdot )⟩$. Its canonical feature map is $\Phi (x)=k(x,\cdot )$, whose inner product is exactly $k(x,x^{\prime })$. A feature map need not be injective; calling it an embedding does not by itself prove distinct inputs remain distinct. The kernel support vector machine uses this geometry together with convex duality to fit and evaluate a maximum-margin classifier while accessing the geometry only through kernel evaluations.

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.

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.

For the equality constraint, the Lagrangian and dual function areand the Lagrangian dual problem is ${\sup }_{z\in {\mathbb{R}}^m}q(z)$. Weak duality says $q(z)\le p^{\ast }$ for every $z$. Strong duality means the dual supremum equals the primal infimum, usually with a dual maximizer. A sufficient convex constraint qualification is that $f$ be proper, closed and convex and that some $x\in \mathrm{ri}(\mathrm{dom}f)$ satisfy $Ax=b$.

Associate a nonnegative Lagrange multiplier ${\lambda }_i$ with each inequality. The Lagrangian dual problem begins withIts infimum over $x\in {\mathbb{R}}^n$ is finite exactly when $A^T\lambda +c=0$, in which case it equals $-b^T\lambda$. The dual linear program is consequentlyFor any primal-feasible $x$ and dual-feasible $\lambda$,which proves weak duality. Strong duality means equality of the two optimal values. The stated strict feasibility is the Slater condition; together with finiteness of the primal optimum it gives strong duality and an attained dual optimum ${\lambda }^{\ast }$.

Let ${\lambda }^{\ast }$ be an optimal dual multiplier and define the maximum violationDual stationarity and strong duality imply, for every $x$,Since every component of $Ax-b$ is at most $v(x)$ and ${\lambda }^{\ast }\ge 0$,It follows that the exact maximum-violation penalty obeysChoose any $M>\Vert {\lambda }^{\ast }{\Vert }_1$. A primal optimum has $v(x)=0$ and penalized value $p^{\ast }$, whereas every infeasible point has $v(x)>0$ and penalized value strictly greater than $p^{\ast }$. Thus the penalized problem and the original linear program have exactly the same minimizers.

The original mathematical optimization problem relative to a chosen Lagrangian dual problem. In convex perturbation duality, its objective is $\phi (x)=f(x,0)$ and its value is $p(0)$. Strong duality concerns optimal values; primal attainment additionally requires an actual minimizing point.

In a finite flow network, a maximum flow exists because the feasible flow set contains the zero flow and is a compact set: the capacity constraints bound every coordinate, and they and flow conservation define a closed set. The strength of a flow is a continuous function, so the extreme value theorem gives an attained maximum. An augmenting path in the residual network would permit positive augmentation, contradicting maximality. The source-reachable vertices in the residual network therefore define a cut of a flow network whose outgoing original edges are saturated and incoming original edges carry zero flow. Flow conservation makes the strength of a flow equal to this cut capacity, proving the max-flow min-cut theorem.

Existence and strong duality for finite real flow network edge capacities do not imply finite termination for every choice of augmenting paths in the Ford-Fulkerson algorithm. With irrational capacities, some choices can continue forever. With integer capacities, Integrality of the Ford-Fulkerson algorithm instead forces finite termination; rational capacities reduce to that case by a common denominator. Choosing shortest augmenting paths as in the Edmonds–Karp algorithm avoids dependence on capacity magnitudes.^[ref]

A shadow price measures the marginal improvement from relaxing an inequality optimization constraint. Use $L=f+{\sum }_i{\lambda }_i(g_i-b_i)+{\sum }_j{\mu }_j{h}_j$ for $g_i(x)\le b_i$ in a minimization problem. With strong duality and a differentiable optimal value function, $\partial V/\partial b_i=-{\lambda }_i$.^[ref]

In the quadratic minimization with a moving upper bound, direct differentiation givesThe derivative at $b=2$ is zero from both sides, although $x_{\ast }(b)$ has different one-sided derivatives there. The value of additional room has faded continuously to zero just as the active constraint stops restricting the optimizer.

At $b=1$, $x_{\ast }=1$, $V=1$ and ${\lambda }_{\ast }=2$. Raising the bound to $1.1$ lowers the value to $0.81$: the first-order prediction is a change of $-2(0.1)=-0.2$, while the exact change is $-0.19$. At $b=3$, the same relaxation leaves $x_{\ast }=2$ and $V=0$. At $b=2$, tightening by $0.1$ costs $0.01$, a second-order effect despite the zero Lagrange multiplier.

There is also a global statement in this example. Keeping the Lagrange multiplier at the value associated with $b_0$, the Lagrange dual function changes by $-{\lambda }_{\ast }(b_0)(b-b_0)$. Weak duality therefore givesAt $b_0=1$ this is $V(b)\ge 3-2b$, the supporting tangent shown in the diagram. This bound remains valid for large changes, whereas the derivative predicts only the first-order effect. If the value function is not differentiable, an optimal Lagrange multiplier can instead supply a supporting subgradient, rather than a unique marginal rate. This is the same idea used in sensitivity analysis in convex perturbation duality.

The Slater condition requires a feasible point at which every nonlinear convex inequality is strict and every affine equality holds. For a convex problem it implies strong duality and attainment of the dual optimum under standard finiteness assumptions.

For a proper cone $K$, suppose a point satisfies $Ax-b\in \mathrm{int}K$ and $p_{\ast }$ is finite. This generalized Slater condition gives strong duality and attainment of the conic dual problem's optimum. It does not by itself assert primal attainment.^[ref]

The two worked examples have strict primal points: $(u,v)=(2,2)$ has slack $(2,2,1)$ in the interior of the nonnegative orthant, and $(t,z)=(2,0)$ has slack $(2,1,0)$ in the interior of the second-order cone. Both optima were already certified by explicit feasible pairs. Slater's condition explains why a matching optimal dual variable can be expected under these hypotheses; checking a supplied zero-gap pair needs only weak duality.

Changing cone geometry preserves the bound mechanism. For a positive semidefinite cone, the dual cone pairing is the Frobenius inner product of two matrices. This connects the same certificate idea to semidefinite programming, while the central path uses strictly interior primal and dual points to approach vanishing gap.

In 1995, Lieven Vandenberghe and Stephen Boyd presented a primal-dual interior-point method for convex optimization with matrix inequalities. Their algorithmic study included exploiting problem structure and allowing incomplete Conjugate gradient method solves within an iteration. This illustrates how the primal-dual viewpoint guides computation as well as checking a final answer.^[ref]

Consider an objective function that is a quadratic polynomial, with a singular optimization constraint:Its only feasible point is $x_{\ast }=0$, giving $p_{\ast }=9$. For $\lambda \ge 0$, completing the square yieldsEvery finite Lagrange multiplier gives $q(\lambda )<9$, but $q(\lambda )\to 9$ as $\lambda \to \infty$. Thus $d_{\ast }=p_{\ast }=9$: strong duality holds, and the primal optimum is attained, yet dual attainment fails. The inner minimizers $3/(1+\lambda )$ approach $0$ without ever becoming feasible at finite $\lambda$.

Both the objective function and the constraint function are convex functions. However, Slater's condition fails because $x^2<0$ is impossible. At the optimum, stationarity would require $-6+\lambda \cdot 0=0$, which no finite Lagrange multiplier satisfies. Compare KKT regularity at a local minimum: a zero gradient of an active constraint can prevent a multiplier certificate. This example has zero duality gap without the Strong Lagrangian property.