advanced29 min studyLesson 45 in Mathematics

Lagrangian duality

Construct lower bounds using constraint prices and distinguish weak duality from conditions that close the gap.

Before you begin

On this page

The question for today

What you’ll understand

Construct a Lagrangian using a consistent inequality sign convention.
Derive a dual function by minimizing over primal variables.
State a constraint qualification that supports strong duality in convex problems.

A feasible decision gives an upper bound on the minimum cost: the optimum cannot cost more than an option we can already implement. Duality constructs bounds from the other side. By attaching nonnegative prices to inequality violations, we create an unconstrained expression whose infimum cannot exceed any feasible objective value. When the upper and lower bounds meet, we have an optimality certificate that is often more informative than a long sequence of improving iterates.

Prices create a lower bound

Use the standard minimization convention $f_i(x)\leq0$ for inequalities and $h_j(x)=0$ for equalities. The Lagrangian adds each constraint multiplied by a coefficient. Inequality coefficients must be nonnegative: at a feasible point their contributions are then nonpositive. Equality coefficients may have either sign because their feasible contributions vanish. Reversing the sign of a constraint without adjusting the convention can destroy the claimed lower bound.

The dual function is the infimum of the Lagrangian over its primal domain, with the multipliers held fixed. It may equal negative infinity, which is a valid but useless lower bound. For every allowed multiplier choice, the infimum is at most the Lagrangian at a feasible candidate, which in turn is at most that candidate's objective. This weak-duality argument does not require the primal problem to be convex.

\mathcal L(x,\lambda,\nu)=f_0(x)+\sum_i\lambda_i f_i(x)+\sum_j\nu_jh_j(x),\quad q(\lambda,\nu)=\inf_x\mathcal L(x,\lambda,\nu),\quad\lambda\geq0

Minimization in x is over the common primal domain. Nonnegative λ makes q a lower bound on every feasible objective value, regardless of primal convexity.↔ Scroll wide equations horizontally.

Optimize the certificate

The dual problem maximizes the lower bound over admissible multipliers. Its objective is concave because it is a pointwise infimum of affine functions of those multipliers. Thus the dual has convex optimization structure even if the original primal is nonconvex. This structural fact does not make it equivalent to the primal: the best dual bound can remain strictly below the true minimum, leaving a duality gap.

For a convex primal with convex inequality functions and affine equalities, a standard Slater condition asks for a point in the relative interior of the common domain that satisfies equalities and makes all inequalities strict. Under the usual finite-optimum assumptions this is a sufficient route to strong duality and dual attainment. It is not necessary in every problem, and it is not a theorem that arbitrary nonconvex problems become exact merely because one strictly feasible point exists.

d_* = \sup_{\lambda\geq0,\nu}q(\lambda,\nu)\leq p_*,\qquad 0\leq f_0(\widehat x)-p_*\leq f_0(\widehat x)-q(\widehat\lambda,\widehat\nu)

The second bound assumes a feasible primal candidate and admissible multipliers with finite q. Their computed gap bounds suboptimality even without knowing the exact optimum.↔ Scroll wide equations horizontally.

Interpret a price with care

Optimal multipliers can describe sensitivity to a changed constraint bound when the value function and regularity conditions support that interpretation. A large multiplier suggests that a small relaxation could substantially improve the objective. It does not prescribe a finite budget change without re-solving the problem: active constraints, differentiability, and the relevant local regime can change. When multiple optimal multipliers exist, sensitivity may require subgradients rather than one derivative.

In the lab, the quadratic gradient path shows how an unconstrained minimization can progress; it is only a conceptual ingredient of evaluating a dual function. No multiplier, constraint, or dual objective is being evolved there. Ask how changing η affects convergence of that fixed inner problem, then return to the symbolic example for the actual lower-bound calculation. This separation prevents mistaking a single gradient path for a primal-dual optimization algorithm.

Work it through

Match a price to a hard lower limit

Minimize $x^2$ subject to $x\geq1$ . Form the dual using $1-x\leq0$ and find matching primal and dual values.

The Lagrangian is $x^2+\lambda(1-x)$ for $\lambda\geq0$ . Minimizing over all real x gives $2x-\lambda=0$ , hence $x=\lambda/2$ and $q(\lambda)=\lambda-\lambda^2/4$ .
The concave parabola q has derivative $1-\lambda/2$ , which vanishes at $\lambda_*=2$ . This admissible multiplier gives $q(2)=2-1=1$ .
The feasible candidate $x_*=1$ has objective one. Its value equals the dual lower bound, so both are optimal. Slater also holds, since x=2 makes $1-x<0$ , but equality of the explicit bounds already certifies this instance.

The result

The multiplier 2 supports an exact lower bound of 1, matching the feasible primal cost. The sign convention is essential to the certificate.

The living notebook

Explore the model

Interactive lab

Interactive lab · optimization

An inner minimization is only one ingredient

For the fixed unconstrained f(x)=x²/2, compare η=0.5 and 1.5 from the same initial point. Predict the objective after two steps. This illustrates numerical minimization only; it does not expose constraints, multipliers, dual values, or a primal-dual gap.

ObjectiveDiscrete iterate

Position x0: 2
Objective x²/2: 2
Iteration behavior: Stable step

Step size η0.3Initial position x₀2

n = 0 · t = 0 s

Gradient descent on f(x) = x²/2: xₙ = (1 − η)ⁿx₀. Playback advances two discrete iterations per second. Values outside |x| ≤ 4 are explicitly reported. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forEvaluating or maximizing a dual bound requires additional mathematical structure beyond an ordinary gradient path.

Pause & reason

Check your understanding

Interactive checks need JavaScript. You can still read the explanation.

Read the checkpoint explanation

For a feasible point, λᵢfᵢ(x)≤0 when λᵢ≥0. This sign makes the Lagrangian and then its infimum lower bounds on the feasible objective.

Your turn

Try it yourself

A feasible solution costs 7.4 and admissible multipliers yield a dual lower bound of 7.1. What can you conclude about the optimum and the feasible solution's suboptimality?

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

Place the unknown optimum between the lower certificate and the feasible upper bound. Do not assume either bound is attained at the true optimum.

Compare with the solution

Weak duality gives $7.1\leq p_*\leq7.4$ . The feasible candidate is therefore at most $7.4-7.1=0.3$ above the optimum. You cannot conclude that its actual error equals 0.3, that strong duality holds, or that the unknown optimal decision is close in Euclidean distance without additional curvature assumptions.

Keep the idea

Take it with you

Weak duality comes from signs and infima, without requiring convexity.
Strong duality needs additional structure; Slater is a useful sufficient condition for convex problems.
A feasible primal value and admissible dual bound provide a measurable optimality gap.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.