Optimization

Lagrangian Duality

Fold constraints into the objective with multipliers, minimize over the primal variables, and obtain a dual problem of lower bounds.

Building the dual

For a primal problem minimize f0(x) subject to f_i(x) <= 0 and h_j(x) = 0, form the Lagrangian L(x, mu, nu) = f0(x) + sum mu_i f_i(x) + sum nu_j h_j(x). The dual function g(mu, nu) = inf_x L(x, mu, nu) minimizes the Lagrangian over x for fixed multipliers. The dual problem maximizes g subject to mu >= 0.

Weak duality always holds

For any mu >= 0 and any nu, g(mu, nu) is a lower bound on the primal optimum p*. Hence the dual optimum d* satisfies d* <= p*. This holds even for nonconvex problems, so the dual always provides a certified lower bound, useful for bounding hard problems.

Strong duality

When d* = p* the duality gap is zero and the dual solves the primal. For convex problems this holds under a constraint qualification such as Slater's condition (a strictly feasible point exists). Linear programs always have zero gap. Nonconvex problems may have a positive gap, though it is often small.

Why the dual is useful

The dual function is always concave, so the dual is a convex problem even when the primal is not.
The dual can have fewer variables or a simpler structure than the primal.
Optimal multipliers reveal constraint sensitivities and support decomposition of large problems.

Connections

Setting the Lagrangian's gradient to zero recovers the KKT conditions. Dual decomposition splits a large coupled problem into independent subproblems coordinated by shared multipliers, the basis of many distributed and parallel optimization algorithms.

python

# Dual function: g(mu, nu) = inf_x  f0(x) + mu^T f(x) + nu^T h(x)
# Dual problem:  max_{mu>=0, nu}  g(mu, nu)   (always concave)

Dual bounds certify how close a candidate design is to the best possible, and decomposition lets large coupled engineering models be optimized in parallel.