Convex optimisation: constraints, Lagrange multipliers and duality

A convex function is bowl-shaped, so any local minimum is the global one. A problem with a constraint is solved by adding the constraint with a Lagrange multiplier, and duality looks at the same problem from the constraint's side.

Why it matters

Gradient descent only promises a local minimum. For convex problems that is enough: the answer is the best possible and doesn't depend on where you start. Knowing which models are convex (linear and logistic regression, SVMs) tells you when to trust the optimiser.

Constraints like "weights must add up to 1" or "every point on the right side of the margin" need Lagrange multipliers, and SVMs are usually trained through their dual problem.

The idea

A convex function is shaped like a bowl, so any local minimum is the global minimum and gradient descent cannot get stuck in a wrong valley.

Constrained problems ('minimise this, but keep that true') are solved with Lagrange multipliers, which add the constraint to the objective as an extra term. Duality looks at the same problem from the constraint's side, and it is how SVMs are usually solved.

A bowl versus a mountain range. Drop a marble into a bowl and it always ends at the same bottom. In a mountain range it can stop in any valley.

Real bowls are simple 3D shapes. Neural network losses are not convex at all, yet gradient descent still works well on them. Convexity is a guarantee we only get for simpler models, like linear regression, logistic regression and SVMs.

How it works

  1. Test convexity with the chord rule: the straight line between any two points on the curve lies on or above the curve. w² passes; w⁴ − 3w² + w fails.
  2. For a smooth function, convex means the second derivative is never negative. In many dimensions: the Hessian matrix has no negative eigenvalues.
  3. Convex ⇒ every local minimum is the global one. Gradient descent from any start reaches the same lowest value.
  4. Now add a constraint: minimise x² + y² subject to x + y = 1.
  5. At the best point, the contour of the objective just touches the constraint line, so their gradients are parallel: ∇f = λ∇g.
  6. Write the Lagrangian L = x² + y² − λ(x + y − 1) and set all its derivatives to 0: 2x = λ, 2y = λ and x + y = 1. So x = y = 0.5 and λ = 1.
  7. λ says how much the best value would change if you loosened the constraint a little: here about 1 per unit.

Key points

Common mistakes

Not true: A convex function always has exactly one point where it is lowest.
In fact: It has one lowest value, but that value can be reached along a whole flat stretch: many minimisers, all equally good.

Not true: The loss of a deep neural network is convex.
In fact: Deep-learning losses are not convex: they have many valleys. That is why initialisation and learning-rate schedules matter.

Go deeper: Why a local minimum of a convex function is the global one

  1. Write the chord rule from the lesson as a formula. For a convex f and any t between 0 and 1: f(t·v + (1 − t)·w) ≤ t·f(v) + (1 − t)·f(w). The left side is a point on the line between w and v; the right side is the chord above it.
  2. Suppose w is a local minimum: no point close to w is lower. Suppose also, hoping for a contradiction, that some far-away point v is lower: f(v) < f(w).
  3. Walk a tiny way from w towards v: the point t·v + (1 − t)·w, with t small, is as close to w as you like.
  4. By the chord rule, f at that point is at most t·f(v) + (1 − t)·f(w). Because f(v) < f(w), that is strictly less than f(w).
  5. So there are points right next to w that are lower than w, which contradicts "w is a local minimum". The assumption was wrong: no lower point v exists.

For a convex function, every local minimum is a global minimum. That is why gradient descent cannot get stuck in a bad valley on linear regression, logistic regression or an SVM.

Part of Unit 1: Math foundations in the free ML Foundations course.