Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 38 · Duality and KKT Conditions

The Lagrangian and the Dual Function

Build the Lagrangian, minimize it over x to get the dual function, and see why it always gives a lower bound on the best value of a constrained problem.

Every constrained problem has a hidden twin. The original problem (the primal) asks you to choose x. The twin (the dual) asks you to choose prices for the constraints. The twin is always convex, even when the primal is not, and its best value is a guaranteed bound on the primal's best value.

In this lesson you build the two main objects behind duality: the Lagrangian and the dual function. The next lessons use them to prove optimality and to read off the "price" of each rule.

The primal problem

We study problems of the form:

Text
minimize    f(x)
subject to  g_i(x) ≤ 0    for i = 1..m
            h_j(x) = 0    for j = 1..p

Call the best value p* (the "primal optimal value"). We keep one running example with a single constraint:

Text
minimize    x²
subject to  1 - x ≤ 0        (that is, x ≥ 1)

The answer is obvious: x = 1 and p* = 1. The point of the example is to watch duality find this number in a different way.

The Lagrangian

The idea: instead of forbidding rule violations, charge a fee for them. Give each inequality a multiplier λ_i ≥ 0 and each equality a multiplier ν_j (any sign). The Lagrangian is:

Text
L(x, λ, ν) = f(x) + Σ λ_i g_i(x) + Σ ν_j h_j(x)

For our example, L(x, λ) = x² + λ(1 - x).

If x is feasible, then g(x) ≤ 0 and λ ≥ 0, so the fee term is ≤ 0: it can only lower L. Therefore, for every feasible x and every λ ≥ 0:

Text
L(x, λ) ≤ f(x)

The Lagrangian is a "soft" version of the problem that is never worse than the true objective on feasible points.

The dual function

Now let the Lagrangian choose the best x freely, ignoring the rules:

Text
d(λ, ν) = min over x of L(x, λ, ν)

This d is the dual function.

For the example, set the derivative of x² + λ(1 - x) to zero: 2x - λ = 0, so x = λ/2. Substituting back:

Text
d(λ) = (λ/2)² + λ(1 - λ/2) = λ - λ²/4

Two facts make d useful.

  • Lower bound. For any λ ≥ 0 and any feasible x: d(λ) ≤ L(x, λ) ≤ f(x). So d(λ) ≤ p* for every λ ≥ 0.
  • Concave. d is a minimum of functions that are affine in (λ, ν), and a pointwise minimum of affine functions is concave. This holds even if the primal is wildly non-convex.

Check the bound: d(0) = 0, d(1) = 0.75, d(2) = 1, d(3) = 0.75. All are ≤ 1 = p*, and λ = 2 reaches it exactly.

Python Dual function by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The dual problem

Each λ ≥ 0 gives a lower bound. The best lower bound comes from the dual problem:

Text
maximize    d(λ, ν)
subject to  λ ≥ 0

Its optimal value is d*. Because every d(λ, ν) ≤ p*, we always get d* ≤ p*. That inequality is called weak duality and is the subject of the next lesson. In the example, maximizing λ - λ²/4 gives λ = 2 and d* = 1 = p*.

The dual problem maximizes a concave function over a convex set, so it is a convex problem. That is why dual methods work even for hard primal problems: you may not solve the primal, but you can still get a certified lower bound.

Equality constraints: a second example

Find the point on the line x₁ + x₂ = 2 closest to the origin:

Text
minimize    x₁² + x₂²
subject to  x₁ + x₂ - 2 = 0

The Lagrangian is L = x₁² + x₂² + ν(x₁ + x₂ - 2). Setting each partial derivative to zero gives x₁ = x₂ = -ν/2. Then:

Text
d(ν) = -ν²/2 - 2ν

It is maximized where d'(ν) = -ν - 2 = 0, so ν = -2 and d* = -2 + 4 = 2. The primal solution is x = (1, 1) with ‖x‖² = 2. Again d* = p*.

Notice that ν has no sign restriction, which is why the dual maximum sits at a negative value.

Python Equality-constrained dual

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Why is the dual function d(λ) a lower bound on the primal optimal value p* when λ ≥ 0?

    On a feasible point g(x) ≤ 0 and λ ≥ 0, so the fee is non-positive. The minimum of L over all x is then below L at any feasible x, which is below f(x).
  2. 2. What sign restriction applies to the multiplier of an equality constraint h(x) = 0?

    An equality violation can go either way, so its fee works in both directions. Only inequality multipliers need λ ≥ 0.
  3. 3. For minimize x² subject to x ≥ 1, what is the dual function?

    Minimizing x² + λ(1 - x) gives x = λ/2, and substituting back gives λ - λ²/4, which peaks at λ = 2 with value 1.
  4. 4. What property does the dual function always have, even for non-convex primal problems?

    It is a pointwise minimum of functions that are affine in the multipliers, and such a minimum is concave.

Summary

  • The Lagrangian adds fees λ_i g_i(x) and ν_j h_j(x) to the objective, with λ ≥ 0 for inequalities.
  • The dual function d(λ, ν) = min_x L(x, λ, ν) is always concave and never exceeds p* when λ ≥ 0.
  • The dual problem maximizes d to find the best lower bound d*.
  • For minimize x² subject to x ≥ 1, d(λ) = λ - λ²/4 and d* = p* = 1.

Next: Weak and Strong Duality