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 minimization problem with $g_i(u)\le 0$ and $h_j(u)=0$, the optimization Lagrangian is $L=f+{\sum }_i{\lambda }_i{g}_i+{\sum }_j{\mu }_j{h}_j$ with ${\lambda }_i\ge 0$ and unrestricted equality Lagrange multipliers. Its infimum over the original variable domain gives a dual lower bound. For a maximization problem, use $L=f-{\sum }_i{\lambda }_i{g}_i-{\sum }_j{\mu }_j{h}_j$ to obtain upper bounds. The Lagrangian sufficiency theorem combines a global extremum of this function with feasibility and complementary slackness. This is distinct from a Lagrangian density in variational physics.

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.

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