Lagrangian dual problem

For a minimization problem with inequalities $g_i(x)\le 0$, the Lagrangian is $L(x,\lambda )=f(x)+{\sum }_i{\lambda }_i{g}_i(x)$ with ${\lambda }_i\ge 0$. The Lagrangian dual maximizes the concave dual function $q(\lambda )={\inf }_{x}L(x,\lambda )$.

The Lagrange dual function is the infimum of a Lagrangian over its primal variables. It is concave in the multipliers, even before convexity of the primal problem is assumed. Maximizing it over sign-compatible multipliers gives a lower bound on a minimization problem by weak duality; appropriate convex qualifications give strong duality.

A Lagrangian relaxation moves selected constraints into the objective with appropriately signed Lagrange multipliers. Maximizing the relaxed objective over a larger easy set gives an upper bound for a constrained maximization problem. Optimizing that bound need not solve the original integer problem.

For binary knapsack optimization, $U(\lambda )$ is an upper bound for every $\lambda \ge 0$. Its minimum is computable from the finitely many profit-to-weight breakpoints and agrees with the fractional knapsack problem optimum. Zero-weight positive-profit terms are added independently.