Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 38 · Duality and KKT Conditions

Weak and Strong Duality

Learn why the dual value never exceeds the primal value, when the two are equal (Slater's condition), and see an example where the gap closes only in the limit.

The dual problem gives lower bounds. A natural question follows: how good is the best bound? If it equals the primal optimum, you can solve the problem from either side, and you can certify an answer by exhibiting matching primal and dual points. This lesson covers the two answers: weak duality (always true) and strong duality (true under conditions).

Weak duality

Let p* be the primal optimal value and d* the dual optimal value. In the previous lesson you saw that d(λ, ν) ≤ f(x) for every feasible x and every λ ≥ 0. Taking the best of each side gives:

Text
d* ≤ p*

This is weak duality. It holds for every optimization problem, convex or not. The difference p* - d* is the duality gap.

Weak duality is a practical tool. Suppose you have a feasible point x and a dual point λ ≥ 0. Then you know d(λ) ≤ p* ≤ f(x). If the two ends are within 0.001 of each other, your x is at most 0.001 from optimal, without knowing p*. Solvers use exactly this to decide when to stop.

Python Sandwiching the optimum

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.

Strong duality

Strong duality means d* = p*: the gap is zero. It does not always hold, but for convex problems it holds under mild conditions called constraint qualifications. The most common one is Slater's condition.

Slater's condition. For a convex problem with convex inequality constraints g_i(x) ≤ 0 and affine equalities Ax = b, suppose there is a strictly feasible point: g_i(x) < 0 for every non-affine g_i, and Ax = b. Then strong duality holds, and if d* is finite, some dual point attains it.

In words: the feasible region must have an interior (it is not squeezed down to a thin edge). In our running example, x = 2 gives 1 - 2 = -1 < 0, so Slater holds, and indeed d* = p* = 1.

For affine inequality constraints, strictness is not even needed (plain feasibility is enough). That is why linear programs have strong duality whenever they have a finite optimum.

When strong duality is subtle

Consider this convex problem:

Text
minimize    x
subject to  x² ≤ 0

The only feasible point is x = 0, so p* = 0. No point has x² < 0, so Slater fails. The Lagrangian is L = x + λx². For λ > 0 the minimum is at x = -1/(2λ), giving:

Text
d(λ) = -1/(4λ)

As λ grows, d(λ) approaches 0 from below but never reaches it. So d* = 0 = p* (the gap is zero) but no finite λ attains it. The value matches, yet the multiplier does not exist. That is a typical failure mode: the KKT conditions of the next lesson cannot be satisfied because there is no optimal λ.

Python A dual optimum that is never attained

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.

Non-convex problems: a real gap

When the primal is not convex, a positive gap is common. Take a tiny problem with a discrete choice:

Text
minimize    x
subject to  x(x - 1) = 0      (so x is 0 or 1)
            x ≥ 0.4

The only feasible point is x = 1, so p* = 1. Let λ ≥ 0 be the multiplier of 0.4 - x ≤ 0 and ν the multiplier of the equality. The next TryIt scans x on a grid, builds the dual function numerically and searches for the best bound.

Python Duality gap on a non-convex problem

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.

A little algebra confirms the search: for ν > 0 the dual function is 0.4λ - (λ + ν - 1)² / (4ν), and its best value over λ ≥ 0 is at most 0.4. So d* = 0.4 while p* = 1: a large gap, because the feasible set is not convex.

Why convexity matters

In a convex problem, the set of (constraint value, objective value) pairs reachable by some x has a convex "upper envelope". A supporting hyperplane to it at the optimum gives the multipliers. When the set is not convex (as with discrete choices), no single hyperplane touches the optimum from below, and a gap appears. Slater's condition guarantees that the hyperplane is not vertical.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which statement is true for every optimization problem, convex or not?

    Weak duality always holds: every dual value is a lower bound on the primal optimum.
  2. 2. What does Slater's condition ask for in a convex problem?

    Slater requires some point that satisfies the (non-affine) inequalities strictly. Then strong duality holds.
  3. 3. You have a feasible x with f(x) = 5.02 and a dual point with d(λ) = 4.99. What can you conclude?

    Weak duality gives d(λ) ≤ p* and feasibility of x gives p* ≤ f(x). So 4.99 ≤ p* ≤ 5.02.
  4. 4. In 'minimize x subject to x² ≤ 0', what goes wrong?

    The feasible set is {0}, so Slater fails. d(λ) = -1/(4λ) approaches p* = 0 only as λ grows without bound.

Summary

  • Weak duality, d* ≤ p*, holds always; the gap is p* - d*.
  • A feasible x and a dual λ bracket the optimum: d(λ) ≤ p* ≤ f(x). Solvers stop when the bracket is tight.
  • Slater's condition (a strictly feasible point) gives strong duality for convex problems.
  • Without Slater, the dual optimum may fail to be attained; for non-convex problems a real gap can remain.

Next: The KKT Conditions