Lagrangian duality · aiwiki.page

Lagrangian duality is a framework in mathematical optimization that associates a constrained problem, called the primal problem, with a dual problem whose variables weight the original constraints. For a minimization problem, dual feasible points provide lower bounds on the primal optimal value. Under suitable conditions, the best bound equals that value. The framework connects optimization bounds, optimality conditions, and algorithms, including methods for nonconvex problems. (mit.edu)

Primal problem and dual construction

Consider the primal problem

p^\star=\inf_{x\in D} f_0(x) \quad\text{subject to}\quad f_i(x)\leq0,\quad h_j(x)=0,

where $i=1,\ldots,m$ , $j=1,\ldots,r$ , and $D$ is the common domain of the functions. The objective function is $f_0$ ; the constraints determine the feasible set. Its Lagrangian is

L(x,\lambda,\nu) =f_0(x)+\sum_{i=1}^{m}\lambda_i f_i(x) +\sum_{j=1}^{r}\nu_j h_j(x).

The Lagrange multipliers satisfy $\lambda_i\geq0$ , while equality multipliers $\nu_j$ are unrestricted. These signs correspond specifically to inequalities written as $f_i(x)\leq0$ . (mit.edu)

The dual function and dual optimal value are

g(\lambda,\nu)=\inf_{x\in D}L(x,\lambda,\nu), \qquad d^\star=\sup_{\lambda\geq0,\nu}g(\lambda,\nu).

The inner minimization retains the domain $D$ , but removes the constraints incorporated into $L$ . The dual function can equal $-\infty$ , so its effective domain consists of multiplier choices giving finite values. It is concave even when the primal problem is nonconvex: it is a pointwise infimum of functions affine in the multipliers. Thus maximizing it is a convex optimization problem, although evaluating it may remain difficult. (mit.edu)

Weak duality and bounds

For any primal feasible $x$ and multipliers with $\lambda\geq0$ ,

g(\lambda,\nu)\leq L(x,\lambda,\nu)\leq f_0(x).

The second inequality follows because equality terms vanish and inequality terms are nonpositive. Taking the supremum over multipliers and infimum over feasible points establishes weak duality:

d^\star\leq p^\star.

This requires neither convexity nor differentiability. (mit.edu)

When the optimal values are finite, $p^\star-d^\star$ is the duality gap. More practically, a primal feasible point and dual feasible multipliers give

0\leq f_0(x)-p^\star \leq f_0(x)-g(\lambda,\nu).

Their objective difference therefore certifies an upper bound on suboptimality. Equality of their objective values proves that both are optimal, without requiring a separate computation of the unknown optimum. (mit.edu)

Strong duality and constraint qualifications

Strong duality means $d^\star=p^\star$ . It does not hold automatically, even for every convex problem. For convex optimization, the objective and inequality functions are convex functions, equality functions are affine, and the domain is a convex set. Additional assumptions called constraint qualifications can guarantee equality of the optimal values. (stanford.edu)

A central sufficient condition is Slater’s condition: there exists a point in the relative interior of the common domain satisfying the equalities and all inequalities strictly. With a finite primal optimum, this also guarantees attainment of the dual optimum. Refined versions do not require affine inequalities to hold strictly. Strong duality itself concerns optimal values and should be distinguished from whether either optimum is attained. (stanford.edu)

Optimality conditions and saddle points

For differentiable functions on an open domain, the Karush–Kuhn–Tucker conditions comprise primal feasibility, dual feasibility, complementary slackness,

\lambda_i f_i(x)=0,

and stationarity,

\nabla f_0(x)+\sum_i\lambda_i\nabla f_i(x) +\sum_j\nu_j\nabla h_j(x)=0.

Stationarity sets the gradient of the Lagrangian with respect to the primal variable to zero. Complementary slackness means a strictly satisfied inequality has zero multiplier. (stanford.edu)

For convex problems, these conditions are sufficient for global optimality; under Slater’s condition they also characterize optimal solutions through the existence of suitable multipliers. More generally, primal and dual optima with zero gap form a saddle point:

L(x^\star,\lambda,\nu) \leq L(x^\star,\lambda^\star,\nu^\star) \leq L(x,\lambda^\star,\nu^\star),

for admissible $x,\lambda,\nu$ . (stanford.edu)

Example

For $\min x^2$ subject to $x\geq1$ , write the constraint as $1-x\leq0$ . Direct calculation gives

L(x,\lambda)=x^2+\lambda(1-x), \qquad g(\lambda)=\lambda-\frac{\lambda^2}{4}.

The infimum over $x$ occurs at $x=\lambda/2$ . Maximizing over $\lambda\geq0$ gives $\lambda^\star=2$ and $d^\star=1$ , matching $x^\star=1$ and $p^\star=1$ . This illustrates the quadratic dual construction and an exact optimality certificate. (stanford.edu)

Sensitivity and computation

Dual multipliers support sensitivity analysis. If inequalities are perturbed to $f_i(x)\leq u_i$ , and strong duality holds at $u=0$ , optimal multipliers imply

p^\star(u)\geq p^\star(0)-(\lambda^\star)^Tu.

When the optimal-value function is differentiable at zero, its derivative is $-\lambda^\star$ . The multiplier thus measures marginal sensitivity to relaxing the corresponding bound. (stanford.edu)

In dual decomposition, multipliers separate a problem with a separable objective and coupling constraints into smaller optimization subproblems. A coordinating algorithm updates the multipliers using constraint residuals. This supports distributed computing, but minimizing the Lagrangian at optimal multipliers does not necessarily recover a feasible primal point; primal recovery may require additional procedures. (see.stanford.edu)