Lagrangian Duality

The primal problem (what we start with)

A standard constrained minimization problem (the primal) is:

Here:

• •$x$ is the decision variable (can be scalar, vector, or structured object).
• •$f(x)$ is the objective.
• •$g_i(x) \le 0$ are inequality constraints.
• •$h_j(x)=0$ are equality constraints.

You already know KKT conditions and Lagrange multipliers. Duality builds on those ideas but changes the emphasis: instead of directly enforcing constraints, we price violations.

The Lagrangian (the key scalar object)

Define the Lagrangian:

• •$\lambda \in \mathbb{R}^m$ are multipliers for inequalities.
• •$\nu \in \mathbb{R}^p$ are multipliers for equalities.
• •For inequality constraints, we restrict $\lambda \ge 0$ (componentwise). This is not cosmetic—it makes the “pricing” consistent.

Intuition:

• •If $g_i(x) \le 0$ is satisfied, then $\lambda_i g_i(x) \le 0$ (since $\lambda_i \ge 0$), so the constraint can only decrease (or leave unchanged) the Lagrangian.
• •If $g_i(x) > 0$ is violated, then $\lambda_i g_i(x) > 0$, so the Lagrangian penalizes that violation.

This mirrors a familiar idea: “soft constraints” with penalties. But duality is more precise: the penalties are variables you optimize.

The dual function: best value of the priced problem

Given multipliers $(\lambda,\nu)$, consider minimizing the Lagrangian over $x$:

This $d$ is called the dual function.

Why is it an infimum (not necessarily a minimum)? Because for some multipliers the Lagrangian might not attain a minimizer, or might go to $-\infty$.

Two important facts (we will prove them carefully soon):

1. 1)For any $\lambda \ge 0$, $d(\lambda,\nu)$ is a lower bound on the primal optimum value $p^*$.
2. 2)$d(\lambda,\nu)$ is concave in $(\lambda,\nu)$, even when the primal problem is not convex.

The dual problem: maximize the best lower bound

If each $(\lambda,\nu)$ gives a lower bound, we should pick the best one:

This is the Lagrange dual problem. Its optimal value is denoted $d^*$.

Why duality is worth learning

Duality is not just “another way to write the same thing.” It gives:

• •Certificates (bounds): Any feasible dual point $(\lambda,\nu)$ immediately certifies a lower bound on $p^*$. This is extremely useful in algorithms and in debugging optimization models.
• •Alternative computation: Sometimes the primal is hard, while the dual is simpler (fewer variables, decomposes, or has a closed form).
• •Structure and insight: Multipliers often have meaning as shadow prices (marginal values of constraints).
• •Algorithms: Dual ascent, subgradient methods on the dual, ADMM, and many distributed optimization methods are built from the dual view.

We’ll proceed slowly: first we’ll make the “lower bound” statement completely concrete; then we’ll talk about when the bound becomes tight; then we’ll turn that into an algorithm.

Step 1: Fix multipliers and look at $L(x,\lambda,\nu)$

For a fixed $(\lambda,\nu)$ with $\lambda\ge 0$, the Lagrangian is just a scalar function of $x$:

Now imagine two categories of $x$:

• •Feasible: satisfies $g_i(x)\le 0$ and $h_j(x)=0$.
• •Infeasible: violates at least one constraint.

For feasible $x$, we can compare $L(x,\lambda,\nu)$ and $f(x)$.

Step 2: For feasible $x$, the Lagrangian never exceeds the objective

If $x$ is feasible, then:

• •Each $g_i(x)\le 0$ and each $\lambda_i\ge 0$ so $\lambda_i g_i(x)\le 0$.
• •Each $h_j(x)=0$ so $\nu_j h_j(x)=0$.

Therefore:

This inequality is the heart of weak duality.

Step 3: Take the best (lowest) Lagrangian value over all $x$

By definition,

The infimum over all $x$ is certainly no larger than the value at any particular feasible $x$:

Now take the infimum over all feasible $x$ on the right-hand side. The best feasible objective value is the primal optimum value $p^*$:

This is weak duality.

Weak duality: For a primal minimization problem, any dual-feasible $(\lambda,\nu)$ gives a lower bound on the primal optimal value.

Pause point #1 (tiny sanity-check)

Before moving on, check that you can literally compute a dual function once.

Consider the 1D problem:

Rewrite the constraint as $g(x)=1-x\le 0$.

• •Lagrangian: $L(x,\lambda)=x^2 + \lambda(1-x)$ with $\lambda\ge 0$.
• •Dual function: $d(\lambda)=\inf_x \big(x^2 + \lambda(1-x)\big)$.

Try computing $d(\lambda)$ by minimizing over $x$ (complete the square or set derivative to zero). Then compare $\max_{\lambda\ge 0} d(\lambda)$ with the primal optimum $p^*=1$.

(We’ll do a closely related worked example later, but you should attempt this now—this is the first “feel” of $\inf_x$.)

The duality gap

Define:

• •Primal optimum value: $p^*$
• •Dual optimum value: $d^*$

Weak duality implies:

The difference $p^* - d^*$ is the duality gap.

• •If $p^* = d^*$, duality is tight and we have strong duality.
• •If $p^* > d^*$, there is a positive gap.

Why the dual function is concave (important for optimization)

This may feel counterintuitive: $d(\lambda,\nu)=\inf_x L(x,\lambda,\nu)$, an infimum of functions linear in $(\lambda,\nu)$. But the infimum of affine functions is concave.

Proof sketch (worth internalizing): for each fixed $x$, define

As a function of $(\lambda,\nu)$, $\phi_x$ is affine (linear + constant) because it is $f(x) + \lambda^T g(x) + \nu^T h(x)$.

Then

The pointwise infimum of affine functions is concave. Concretely, for $0\le t\le 1$:

That inequality step is the key: infimum of a sum is ≥ sum of infima.

Interactive-canvas moment: visualize “lower bound curves”

If your tech tree platform supports an interactive plot, this is the perfect place to attach it.

Suggested interaction:

• •Pick a simple primal (like minimizing a quadratic with a linear inequality).
• •For each $\lambda\ge 0$, compute $d(\lambda)$.
• •Plot the curve $d(\lambda)$ and show the horizontal line at $p^*$.

What you should see:

• •For small $\lambda$, the penalty is weak; the infimum may be far below $p^*$.
• •As $\lambda$ changes, $d(\lambda)$ rises (not necessarily monotonically, but it has a concave “cap” shape).
• •At the maximizing $\lambda^*$, $d(\lambda^*)$ is the best lower bound; in strong-duality cases it meets $p^*$.

This visualization makes the definition $d(\lambda)=\inf_x L(x,\lambda)$ feel less abstract: you are literally pushing up the best guaranteed lower bound by tuning prices.

Weak duality always holds, but strong duality is where duality becomes a solving tool, not just a bounding tool.

Convexity is the enabling assumption

Strong duality is most commonly guaranteed in convex optimization problems of the form:

where:

• •$f$ is convex,
• •each $g_i$ is convex,
• •$Ax=b$ is affine.

(Equality constraints more generally can be affine functions $h_j(x)=0$; writing them as $Ax=b$ is a clean special case.)

Convexity matters because it prevents “hidden” nonconvex geometry that can create a duality gap.

Slater’s condition (the standard constraint qualification)

A widely used sufficient condition for strong duality is Slater’s condition:

For convex problems with inequality constraints $g_i(x)\le 0$ and affine equalities, if there exists a point $\tilde{x}$ such that

• •$g_i(\tilde{x}) < 0$ for all $i$ (strict feasibility),
• •and $A\tilde{x}=b$,

then strong duality holds and KKT conditions are necessary and sufficient.

So Slater is an “interior point exists” condition.

Why do we need it? Intuitively:

• •If the feasible set has nonempty interior (relative to the equality constraints), multipliers behave nicely.
• •If feasible points only exist on the boundary in a fragile way, multipliers may blow up or fail to represent the problem tightly.

What strong duality gives you (operationally)

If strong duality holds:

Moreover, there exist optimal multipliers $(\lambda^*,\nu^*)$ such that:

• •$d(\lambda^*,\nu^*) = p^*$
• •and a primal optimal solution $x^*$ together with $(\lambda^*,\nu^*)$ satisfy the KKT conditions:
• •Primal feasibility
• •Dual feasibility ($\lambda^*\ge 0$)
• •Complementary slackness ($\lambda_i^* g_i(x^*)=0$)
• •Stationarity ($\nabla f(x^*) + \sum_i \lambda_i^* \nabla g_i(x^*) + \sum_j \nu_j^* \nabla h_j(x^*) = 0$)

In other words, duality explains why KKT works: it’s the optimality condition for a saddle point of the Lagrangian.

Saddle-point picture (a unifying mental model)

Think of the Lagrangian as a two-player game:

• •Player X chooses $x$ to minimize $L(x,\lambda,\nu)$.
• •Player Λ chooses $(\lambda,\nu)$ (with $\lambda\ge 0$) to maximize $L(x,\lambda,\nu)$.

The primal problem is like:

The dual problem is:

A saddle point $(x^*,\lambda^*,\nu^*)$ satisfies:

for all feasible multipliers and all $x$.

• •The right inequality says $x^*$ minimizes the Lagrangian under optimal multipliers.
• •The left inequality says optimal multipliers make the Lagrangian as large as possible at $x^*$.

Strong duality is closely related to the existence of such a saddle point.

Pause point #2 (Slater sanity-check)

Decide whether Slater’s condition holds.

Problem A:

Is there a strictly feasible point? Yes: $x=0$ gives $0<1$. So Slater holds.

Problem B:

Feasible set is only $\{0\}$. There is no $x$ with $x^2<0$, so Slater fails.

Take 30 seconds to reflect: both problems are convex, but B has a “boundary-only” feasible set.

Slater failing does not automatically mean strong duality fails, but it removes a key guarantee.

Strong duality is not universal

For nonconvex problems, duality can be loose:

• •Dual provides a lower bound (still true).
• •But $d^*$ can be strictly less than $p^*$.

This is why in combinatorial optimization, one often uses duality as a relaxation: solve the dual (or a related convex relaxation) to get bounds even if you can’t solve the primal exactly.

A practical consequence: dual optimality = optimal certificate

When strong duality holds, a dual optimal solution $(\lambda^*,\nu^*)$ is a certificate of optimality:

• •If you have a candidate primal feasible $x$ and a dual feasible $(\lambda,\nu)$ such that $f(x)=d(\lambda,\nu)$, then you have proven global optimality (because $d(\lambda,\nu)\le p^*\le f(x)$).

This “sandwich” proof is one of the most useful ways to trust an optimizer.

Duality is not only theory; it directly yields optimization methods.

The dual problem as concave maximization

The dual problem is:

with $d$ concave. So we are maximizing a concave function, which is the “nice” direction (equivalently, minimizing a convex function $-d$).

But there’s a catch: $d(\lambda,\nu)$ is defined via an infimum over $x$. It may be nonsmooth.

Computing a subgradient of the dual function

Suppose for given $(\lambda,\nu)$ we can find

Then a subgradient of $d$ is given by constraint residuals at that minimizing $x$:

• •For inequalities: $\partial_{\lambda_i} d(\lambda,\nu)$ includes $g_i(x(\lambda,\nu))$.
• •For equalities: $\partial_{\nu_j} d(\lambda,\nu)$ includes $h_j(x(\lambda,\nu))$.

Intuition:

• •If a constraint is violated ($g_i(x)>0$), increasing $\lambda_i$ should raise the penalty and thus raise the lower bound.
• •If a constraint is satisfied with slack ($g_i(x)<0$), increasing $\lambda_i$ may actually lower $d$ (and the optimizer will keep $\lambda_i$ from growing).

Dual ascent updates

A basic dual ascent / subgradient method:

1. 1)Given $(\lambda^k,\nu^k)$, compute

2. 2)Update multipliers using residuals:

Where:

• •$g(x^k)$ is the vector $(g_1(x^k),\dots,g_m(x^k))$.
• •$h(x^k)$ is the vector $(h_1(x^k),\dots,h_p(x^k))$.
• •$\Pi_{\lambda\ge 0}$ projects onto the nonnegative orthant (componentwise max with 0).
• •$\alpha_k$ is a step size.

Why projection only for $\lambda$? Because dual feasibility requires $\lambda\ge 0$ for inequalities, but $\nu$ is free.

How to choose step sizes (briefly)

Subgradient methods are sensitive to step sizes.

Common choices:

• •Constant step size: $\alpha_k=\alpha$ (often gives a neighborhood around optimum).
• •Diminishing step size: $\alpha_k \to 0$ with $\sum_k \alpha_k=\infty$ (classic convergence conditions for subgradient methods).

In practice, many systems use more advanced variants (accelerations, adaptive rules) or different splitting methods (e.g., ADMM) that are also rooted in the Lagrangian.

Why dual ascent can be efficient: separability and decomposition

A major payoff occurs when the Lagrangian separates over components of $x$.

Suppose $x=(x_1,\dots,x_N)$ and

and constraints couple them only through a simple sum, e.g.

Then

Now the minimization over $x$ splits:

So computing $d(\nu)$ is $N$ smaller problems, often parallelizable.

This is the conceptual foundation of distributed optimization: multipliers coordinate many local optimizations.

Connecting back to KKT

If strong duality holds and the method converges to $(\lambda^*,\nu^*)$ with corresponding $x^*$ minimizing $L(\cdot,\lambda^*,\nu^*)$, then KKT conditions emerge:

• •Stationarity: $x^*$ minimizes $L$.
• •Complementary slackness: in the limit, multipliers grow only where constraints are tight.
• •Feasibility: residuals driven toward 0 by multiplier updates.

This is a clean story:

• •KKT describes optimality.
• •Dual ascent is one route to satisfy KKT by iteratively tuning multipliers.

A second interactive-canvas moment (algorithm intuition)

If you can animate iterations:

• •Show a point $x^k$ moving in primal space (perhaps unconstrained minimizer of $L$).
• •Show $\lambda^k$ changing over time.
• •Overlay the constraint boundary $g(x)=0$.

What learners should observe:

• •If $x^k$ violates the constraint, $\lambda$ increases, “tilting” $L$ so the next minimizer is pushed back toward feasibility.
• •If $x^k$ is strictly feasible, $\lambda$ may decrease toward 0.

This makes dual ascent feel like an automatic constraint-enforcement mechanism driven by prices.