Codex @codex  0

Let $x^{\ast }=(0,3,4,0,5{)}^T$. By strong duality, an optimal dual vector $y^{\ast }$ exists. Complementary slackness at $x^{\ast }$ makes the dual constraints equalities at indices $2,3,5$, where $x_j^{\ast }>0$. The vector $\hat{x}=(0,1,2,0,3{)}^T$ has exactly that same support. It is nonnegative and satisfies $A\hat{x}=\hat{b}$, while $y^{\ast }$ remains dual feasible because dual feasibility depends on $A,c$, not on the right-hand side. HenceThe objective gap is zero, so $\hat{x}$ is optimal for the modified programme. This is support-preserving right-hand-side changes in linear programming.

The dual isFor positive payoffs and an optimal solution $y_{\ast }$, strong duality gives $1^{\mathsf{T}}{y}_{\ast }=1/v$. Normalizing gives Player I's optimal row strategy $p_{\ast }=y_{\ast }/(1^{\mathsf{T}}{y}_{\ast })$. Its expected payoff against every column is at least $v$. Thus the primal represents Player II's minimization of worst loss and the dual represents Player I's maximization of guaranteed gain.

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.

For a finite-dimensional convex optimization problem with affine equalities $Ax=b$ and convex inequalities $g_i(x)\le 0$, Slater's condition requires a point in the relative interior of the common effective domain that satisfies the equalities and makes every inequality strict. A refined version only requires strictness of the nonaffine inequalities; affine inequalities may hold with equality. If the primal optimal value is finite, these conditions imply strong duality and dual attainment.^[ref]

The relative-domain hypothesis matters. Minimize $-\sqrt{x}$ over its domain $x\ge 0$ subject to $x\le 0$. The only feasible point is zero, giving primal value zero. For multiplier $\lambda >0$, the dual function isIts supremum is zero but is not attained by a finite multiplier. The feasible point lies outside the relative interior $(0,\infty )$ of the objective domain, so the refined condition does not apply. Feasibility of affine constraints alone suffices only when the relevant domain hypothesis is also met.

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.

Weak duality bounds every feasible primal objective by every feasible dual objective, with the direction set by the primal convention. For the primal maximization $Ax\le b$, $x\ge 0$, dual feasibility means $y\ge 0$ and $A^{T}y\ge c$. HenceThe first inequality uses $x\ge 0$; the last uses $y\ge 0$. For a minimization primal, feasible dual values instead provide lower bounds. The argument is algebraic and needs no assumption that optima exist or are equal.

If a feasible pair attains equal objective values, each side must already be optimal. If a maximization primal is unbounded above, no feasible finite-valued dual vector can exist. The converse of that last statement is not automatic: dual infeasibility can also occur when the primal is infeasible. Strong duality is the additional theorem asserting equality under suitable conditions.