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.

In a minimum-cost flow problem, a directed graph has arc flows $f_{ij}$, unit costs $c_{ij}$, lower and upper capacities ${\ell }_{ij},u_{ij}$, and net supplies $b_i$ summing to zero. The linear program minimizes ${\sum }_{ij}{c}_{ij}{f}_{ij}$ subject to the flow balances ${\sum }_j{f}_{ij}-{\sum }_j{f}_{ji}=b_i$ and ${\ell }_{ij}\le f_{ij}\le u_{ij}$.

Give each graph vertex a network dual potential ${\pi }_i$. With the outgoing-minus-incoming oriented incidence matrix $B$, the optimization Lagrangian isMinimizing over the capacity intervals is separable. A candidate feasible flow minimizes this optimization Lagrangian if it takes its lower bound whenever the network reduced cost is positive, its upper bound whenever that network reduced cost is negative, and any allowed value when that network reduced cost is zero. Equivalently, for arcs with distinct lower and upper bounds,For every other feasible flow $g$, these conditions give $c^{T}f=L(f,\pi )\le L(g,\pi )=c^{T}g$. This proves the Lagrangian sufficiency theorem certificate, rather than merely stating the capacitated flow optimality conditions.

Put $t=f_{23}$. The four flow balances determineIntersecting the four capacity intervals gives $2\le t\le 4$. In particular,is a feasible flow. Write $C=c_{12}+c_{23}+c_{34}+c_{41}$. Its cost along the feasible interval isHence $f(2)$ is optimal precisely when $C\ge 0$. A network dual potential certificate isThe three interior arcs have zero network reduced costs and $r_{23}=C$, which has the required nonnegative sign at its lower capacity.

For the network simplex algorithm, start with the network simplex tree basis consisting of arcs $12,34,41$, and fix nonbasic arc $23$ at its lower bound 2. These are exactly the potentials just found. If $C\ge 0$, no improving pivot is needed. If $C<0$, arc $23$ enters and its fundamental graph cycle increases all four flows by the same amount. At $f(2)$ the remaining upper capacities are $(3,3,2,4)$, so the simplex ratio test allows an increase of 2. Arc $34$ reaches its upper bound and leaves the tree. The new network simplex tree basis has arcs $12,23,41$, with potentialsNow only the nonbasic arc $34$ has a possibly nonzero network reduced cost, namely $r_{34}=C<0$. It is at its upper bound, so the sign is optimal. Thus for all real costs the complete answer isWhen $C=0$, both endpoint basic feasible solutions and every intermediate feasible flow have the same cost.

To count basic solutions, a network simplex tree basis omits one arc of the four-cycle and fixes that arc at either bound. The possibilities areThere are eight tree/bound basic representations, seven distinct basic flow vectors, and two basic feasible solutions. The distinction in the first count matters: the upper bounds on $12$ and $23$ both give the identical flow $(8,5,6,7)$ at $t=5$. Thus if “basic solutions” counts vectors rather than basis representations, the answer to (i) is seven; the frequently used count of basis/bound choices is eight. The answer to (ii) is unambiguously two, since only $t=2,4$ satisfy all capacities.

Use the optimization Lagrangian with the sensitivity sign conventionFor equality constraints the Lagrange multipliers have unrestricted signs. The Lagrangian sufficiency theorem says that if $h(x^{\ast })=b$ and, for some ${\lambda }^{\ast }$, $x^{\ast }$ globally minimizes $L_b(\cdot ,{\lambda }^{\ast })$ over $X$, then $x^{\ast }$ globally minimizes $f$ subject to the constraint. Indeed every feasible $x$ satisfiesThis proves the theorem without a convexity or differentiability assumption. Merely finding a stationary point of the optimization Lagrangian would not establish its required global minimum.

Let $\varphi (u)=\inf \{f(x):x\in X,h(x)=u\}$, with value $+\infty$ when the feasible set is empty, and suppose $\varphi (b)$ is finite. The problem has the Strong Lagrangian property if a finite multiplier $\lambda$ satisfiesThis includes attainment of the dual bound by a multiplier. It does not by itself assert attainment of the primal infimum. For every multiplier, restricting the infimum to feasible $x$ gives ${\inf }_X{L}_b(x,\lambda )\le \varphi (b)$, the relevant weak duality. A non-vertical supporting hyperplane of a value function is a planewith $\varphi (u)\ge \varphi (b)+{\lambda }^T(u-b)$ for every $u$. Its vertical coefficient is nonzero and has been normalized to one; the epigraph lies above it. The two directions of the equivalence are proved in parts (a) and (b).

For the sampling allocation put $A={\sum }_i\sqrt{a_i{v}_i}$. Finite variance requires every $x_i>0$; interpret the objective at a zero coordinate as $+\infty$. An optimum uses all the budget, because scaling every positive $x_i$ up would otherwise reduce the objective while remaining feasible. The Cauchy-Schwarz inequality gives the global boundEquality requires $v_i/x_i$ to be proportional to $a_i{x}_i$. The budget then determines the unique allocation:This is the optimal cost-constrained stratified sampling allocation.

For an inequality ${\sum }_i{a}_i{x}_i\le b$, our sign convention uses $\lambda \le 0$, so $L_b=f-\lambda ({\sum }_i{a}_i{x}_i-b)$ is a lower bound on $f$ at feasible points. Its coordinate stationary equations are $-v_i/x_i^2-\lambda a_i=0$, and the displayed allocation givesThe function $v_i/x_i+(-{\lambda }^{\ast })a_i{x}_i$ has a strict global minimum at $x_i^{\ast }$: its second derivative is $2v_i/x_i^3>0$ and its value diverges at both endpoints of $(0,\infty )$. Thus the multiplier also supplies the Lagrangian sufficiency theorem certificate, with the tight inequality giving complementary slackness.

Finally, for $b+\delta b>0$,Hence the first-order change in minimal variance is $\boxed{{\lambda }^{\ast }\delta b}$. Increased resources decrease the variance. With the alternative convention $L=f+\mu ({\sum }_i{a}_i{x}_i-b)$, the multiplier is $\mu =-{\lambda }^{\ast }>0$ and the sensitivity is $-\mu \delta b$.

For a minimization problem on a domain $D$, write the equality constraints as $h(x)=0$ and the inequality constraints as $g(x)\le 0$. Define the optimization LagrangianThe Lagrangian sufficiency theorem states that a feasible $x^{\ast }$ is globally optimal if it globally minimizes $L(\cdot ,{\lambda }^{\ast },{\mu }^{\ast })$ on $D$ for some multipliers with ${\mu }^{\ast }\ge 0$ and satisfies complementary slackness, ${\mu }_j^{\ast }{g}_j(x^{\ast })=0$ for every $j$. Equality multipliers have unrestricted signs.

For any feasible $x$, the multiplier sign gives $L(x,{\lambda }^{\ast },{\mu }^{\ast })\le f(x)$. Feasibility and complementary slackness at $x^{\ast }$ give $L(x^{\ast },{\lambda }^{\ast },{\mu }^{\ast })=f(x^{\ast })$. HenceThis proves sufficiency. Global Lagrangian minimization, rather than stationarity alone, is the certificate. No convexity or constraint qualification is needed for this implication; convexity is one way to verify the required global minimum.

Use the Lagrange multiplier with the sign conventionFor every $\lambda >0$, this is a strictly convex quadratic in $x$, with unique global minimizerThese formulas follow by setting the three partial derivatives of the optimization Lagrangian to zero; its Hessian is $\mathrm{diag}(2\lambda ,2\lambda ,4)$, which is positive-definite.

Choose $\lambda >0$ to make this minimizer feasible. Its constraint value is $5/(2{\lambda }^2)-\lambda /4$, so the scalar equation isThe left side of the first equation is strictly decreasing on $(0,\infty )$, with limits $+\infty$ and $-\infty$. Thus exactly one positive multiplier exists and can be obtained by a bracketed scalar root search. The Lagrangian sufficiency theorem proves that its associated feasible point is the global optimum; strict Lagrangian convexity makes that optimum unique.

Consequently the unique solution isIts objective value is $-5/\lambda +{\lambda }^2/8$. This scalar multiplier certificate for a quadratic equality constraint does not require finding the multiplier in radicals, and does not mistake the nonconvex equality surface for a convex set.

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.

For a maximization problem with $g_i(u)\le 0$ and $h_j(u)=0$, use the optimization LagrangianThe Lagrangian sufficiency theorem says: if $u^{\ast }$ is feasible, $u^{\ast }$ globally maximizes $L(\cdot ,{\lambda }^{\ast },{\mu }^{\ast })$ over its original domain, and complementary slackness holds, ${\lambda }_i^{\ast }{g}_i(u^{\ast })=0$, then $u^{\ast }$ globally maximizes $f$ over the feasible set. Equality Lagrange multipliers have no sign restriction. For every feasible $u$,which proves the theorem.

For a minimization problem, reverse the signs in the optimization Lagrangian: take $L=f+{\sum }_i{\lambda }_i{g}_i+{\sum }_j{\mu }_j{h}_j$, with ${\lambda }_i\ge 0$. If a feasible $u^{\ast }$ globally minimizes this optimization Lagrangian and satisfies complementary slackness, thenThe hypothesis is a global extremum of the Lagrangian. Merely solving its stationarity equations is insufficient; no convexity assumption is needed when the global extremum itself has been proved.

With $g=2x-y-z-2$ and $h=x^2+y^2-5$, the maximization optimization Lagrangian isA finite unconstrained maximum requires $\lambda =1$ to cancel the coefficient of $z$. With $\mu =1$, completing the square givesThus its global maximizers have $x=-1$ and $y=2$. The equality constraint holds, and complementary slackness with $\lambda =1$ makes $g=0$, giving $z=-6$. The Lagrangian sufficiency theorem certifiesEvery feasible point has objective at most $L\le 12$, so this is a global conclusion rather than just a stationary-point calculation.

For minimization, the optimization Lagrangian isIts coefficient of $z$ is $-1-\lambda <0$, so its infimum over unrestricted $z$ is $-\infty$ for every allowable Lagrange multiplier. There is no finite global minimizer of the optimization Lagrangian to which the Lagrangian sufficiency theorem could apply.

The primal minimization problem is also unbounded: set $x=0$, $y=\sqrt{5}$ and $z=t\ge 0$. These points are feasible, and $3y-z=3\sqrt{5}-t\to -\infty$. Hence

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.

Choose the oriented incidence matrix convention with $+1$ at an edge's tail and $-1$ at its head. Let $b_i$ be net supply, so ${\sum }_i{b}_i=0$. The uncapacitated minimum-cost flow problem on a finite directed graph isor $Bf=b$. Negative $b_i$ denotes net demand. Costs may have either sign; the problem can be infeasible or unbounded.

For vertex network dual potentials $\pi$, the optimization Lagrangian isThe infimum over $f\ge 0$ is finite exactly when every network reduced cost $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$ is nonnegative. Thus the Lagrangian dual problem and complementary slackness areA feasible flow and feasible network dual potentials satisfying these equalities have equal costs and are optimal by weak duality.

If the underlying undirected graph is connected, deleting one redundant balance row makes the oriented incidence matrix have rank $|V|-1$. A set of $|V|-1$ independent edge columns is exactly a spanning tree. Set all non-tree flows to zero, solve the tree balances, and check nonnegativity to obtain a basic feasible solution. Basic tree edges may have zero flow, which is degeneracy in linear programming. Requiring $r_{ij}=0$ on tree edges determines network dual potentials up to a common additive constant. If every non-tree network reduced cost is nonnegative, the tree flow is optimal. This is the basis of the network simplex algorithm. If the graph is disconnected, solve the balances separately in each component; each component must have total net supply zero and uses its own spanning tree.

Separate inactive and active optimization constraints. At an interior feasible point with $h>0$, a differentiable local minimum must satisfy $\nabla f=0$. Retain only solutions lying in the interior.

On the boundary $h=0$, if $\nabla h\ne 0$, apply the Lagrange multiplier condition. Using the optimization Lagrangian $L=f-\lambda h$, the Karush-Kuhn-Tucker conditions areThe sign follows from feasible motion into $h>0$: the directional derivative along $\nabla h$ at a minimum cannot be negative. Thus a boundary candidate has $h=0$ and a nonnegative Lagrange multiplier. Boundary points with $\nabla h=0$ must be examined separately, because the usual constraint qualification fails there.

Solve the interior and boundary systems, check membership in the feasible set, and establish which candidates are minima using second-order tests or a direct global comparison. The Karush-Kuhn-Tucker conditions alone are not sufficient for general nonconvex functions or feasible sets. On an unbounded feasible set, also check whether an infimum is attained and whether escaping sequences can improve the objective.

Use the optimization LagrangianSymmetry gives the gradient equations $2Ax=\lambda 1$ and $2By=\lambda 1$. The positive-definite matrices are invertible, so defineThe affine constraint gives $\lambda =2/D$, henceFor a global certificate, write any other feasible point as $(x_{\ast }+u,y_{\ast }+v)$. Feasibility implies $1^{T}u+1^{T}v=0$. Expansion cancels the cross terms and leavesBy positive definiteness this is positive unless $u=v=0$. Thus the solution is the unique global minimum, not merely a stationary point. This is a two-block instance of positive quadratic minimization under one affine constraint.

Assume $f$ and $g$ are continuously differentiable near the point. At a regular feasible point, meaning $g(x)=0$ and $\nabla g(x)\ne 0$, a differentiable constrained local extremum satisfies the Lagrange multiplier equationsThey arise by differentiating the optimization Lagrangian $L(x,\lambda )=f(x)-\lambda g(x)$ with respect to all coordinates and the multiplier. Geometrically, the objective has zero derivative along the tangent space of the constraint surface, so its gradient must lie in the normal direction.

Solve these equations for candidates, examine feasible points where the regularity condition fails separately, and compare objective values or use a second-order test restricted to feasible directions. The equations locate stationary points; they do not by themselves establish which are minima or whether a global minimum is attained.

A nonconvex primal problem can have a positive duality gap even when both optima are attained. Choose the finite set $X=\{-2,0,2\}$, the objective function values $f(-2)=0$, $f(0)=3$, $f(2)=0$, and the equality optimization constraint $h(x)=x=0$. The only feasible point is $0$, so $p_{\ast }=3$.

With unrestricted equality Lagrange multiplier $\nu$, the three possible optimization Lagrangian values and their minimum areThe concave Lagrange dual function has unique maximizer ${\nu }_{\ast }=0$, with $d_{\ast }=0$. Thus the duality gap is $3$. At the optimal Lagrange multiplier, both inner minimizers $-2$ and $2$ violate the equality; the dual optimum does not recover a primal optimizer.

Why can no slope close the gap? Any affine function $a+bx$ lying below the two endpoint costs obeys $a-2b\le 0$ and $a+2b\le 0$. Adding gives $a\le 0$, so its value at residual zero cannot reach the feasible cost $3$. A convex combination of the endpoint cost-residual pairs with equal weights has residual zero and average cost zero. This averaged pair is unattainable: the actual decision $x=0$ costs $3$. This geometry explains precisely what the dual bounds fail to distinguish. Nonconvexity does not force a positive duality gap: changing only $f(0)$ to $0$ makes both optimal values zero on the same nonconvex domain.

Consider the minimization problemThe objective function is a strictly convex function with its unconstrained optimization minimum at $x=2$. If $b<2$, it decreases throughout the feasible set until the bound $x=b$ is reached. If $b\ge 2$, the feasible set already contains $2$. HenceWith $g(x)=x-b$, the optimization Lagrangian and KKT conditions areSubstituting $x_{\ast }(b)$ gives the unique inequality Lagrange multiplierFor $b<2$, the active constraint has ${\lambda }_{\ast }>0$. For $b>2$, there is strict slack $b-x_{\ast }=b-2$ and ${\lambda }_{\ast }=0$. At $b=2$, the active constraint has zero Lagrange multiplier: the boundary happens to pass through the unconstrained optimum. Feasibility and complementary slackness must both be checked; solving only $2(x-2)+\lambda =0$ would allow infeasible candidates.

An independent certificate follows by completing the square:The Lagrange dual function is a concave function of $\lambda$. Its maximum over $\lambda \ge 0$ occurs at ${\lambda }_{\ast }(b)$ and equals $V(b)$. Thus every case has an explicit lower bound attained by a feasible point; the KKT conditions provide a certificate that can be checked without searching all real numbers.

For $\gamma >0$ and $c\ne 0$, minimize $c^{T}u+\gamma z^2$ subject to $\Vert u{\Vert }^2+z=R$. Adding a positive Lagrange multiplier times the constraint gives a positive-definite quadratic optimization Lagrangian, whose minimizer is $u=-c/(2\lambda )$ and $z=-\lambda /(2\gamma )$. Feasibility is the displayed scalar equation. Its left side strictly decreases from positive infinity to negative infinity on $\lambda >0$, so it has a unique root for every real $R$. The Lagrangian sufficiency theorem certifies a unique global optimum on the possibly nonconvex equality surface.

For a finite constrained optimum value $\varphi (b)=\inf \{f(x):h(x)=b,x\in X\}$ and optimization Lagrangian $L_b(x,\lambda )=f(x)-{\lambda }^T(h(x)-b)$, the strong Lagrangian property means that some finite Lagrange multiplier attains the dual lower bound exactly: ${\inf }_X{L}_b=\varphi (b)$. It includes dual attainment, but need not include primal attainment. It is equivalent to a non-vertical supporting hyperplane of a value function: a supporting slope gives $f(x)\ge \varphi (h(x))\ge \varphi (b)+{\lambda }^T(h(x)-b)$, hence ${\inf }_X{L}_b\ge \varphi (b)$; weak duality gives the opposite inequality. Conversely the infimum identity bounds every $L_b(x,\lambda )$ below by $\varphi (b)$; taking the infimum over $h(x)=u$ gives the supporting inequality. No convexity assumption is needed for this equivalence.