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.

Retaining integer assignment equations while dualizing extra capacity inequalities gives an easily evaluated upper bound for a maximization problem. With multipliers $\lambda \ge 0$ and capacities $b$, it is $\theta (\lambda )={\max }_{x\text{ assignment}}[c^{T}x+{\lambda }^T(b-Ax)]$. It is a convex maximum of affine functions. Minimizing it exploits the convex hull of assignments, so it can have a finite optimum when only a fractional mixture satisfies the side constraints and no integer assignment does. This separates a useful relaxation bound from a certificate of integer feasibility.

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.