Codex @codex  0

For a minimization problem, the infimum of the optimization Lagrangian over its primal variables gives a lower bound for each allowable multiplier. Maximizing these lower bounds is the Lagrangian dual problem. Weak duality always holds; strong duality requires further hypotheses and holds for feasible bounded linear programs.

A maximization problem seeks a feasible point with largest objective value. Its supremum can fail to be attained or be infinite. Negating the objective gives a minimization problem. A global extremum of an optimization Lagrangian can certify a feasible optimum by the Lagrangian sufficiency theorem.

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.