Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 38 · Convex Sets and Functions

Convex Functions

Define convex functions with the chord rule, see classic examples like x squared, absolute value and exp, and test the inequality on random points in Python.

A convex function is the mathematical version of a bowl. It curves upward, so any valley it has is the valley, with no false bottoms. In this lesson you learn the definition, a handful of standard examples and a numerical check you can run yourself.

The chord definition

A function f is convex if its domain is a convex set and, for all x, y in the domain and all θ in [0, 1]:

Text
f(θx + (1 - θ)y) ≤ θ·f(x) + (1 - θ)·f(y)

Read it geometrically. The left side is the height of the graph at a point between x and y. The right side is the height of the chord, the straight line joining (x, f(x)) and (y, f(y)), at the same point. Convex means the graph never rises above its chords.

  • f is strictly convex if the inequality is strict whenever x ≠ y and 0 < θ < 1.
  • f is concave if -f is convex (an upside-down bowl).
  • A linear (affine) function is both convex and concave.

Standard examples

Function Domain Convex?
x² all real x yes (strictly)
abs(x) all real x yes, but not strictly
eˣ all real x yes (strictly)
x⁴ all real x yes (strictly)
-ln x x > 0 yes (strictly)
x ln x x > 0 yes
1/x x > 0 only yes on x > 0, not on the whole line
x³ all real x no (only convex for x ≥ 0)
sin x all real x no
‖x‖ (any norm) vectors yes
aᵀx + b vectors yes (affine)

Notice that 1/x is convex on x > 0 but not across zero, and x³ is convex only on a half line. Convexity always depends on the domain.

Testing the chord inequality

Let us test random pairs of points. A single violation proves non-convexity; no violations after many trials is encouraging but not a proof.

Python Random chord test

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.

You should see zero violations for x², abs(x), eˣ and x³ on [0, 5], and many violations for x³ on [-5, 5] and for sin.

A picture of a chord

Python The chord lies above the graph

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.

Jensen's inequality

Extend the definition from two points to many. If f is convex, and θ₁, ..., θₖ are non-negative weights adding to 1, then

Text
f(θ₁x₁ + ... + θₖxₖ) ≤ θ₁f(x₁) + ... + θₖf(xₖ)

This is Jensen's inequality. In probability it reads f(E[X]) ≤ E[f(X)]: "the function of the average is at most the average of the function." For f(x) = x² it says the square of the mean never exceeds the mean of the squares, which is why variance is never negative.

Python Jensen's inequality with data

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 two last numbers are equal, and both are non-negative, as Jensen guarantees.

The first-order view

For a differentiable convex function, the tangent line is always below the graph:

Text
f(y) ≥ f(x) + ∇f(x)ᵀ(y - x)    for all x, y

This tells you that a zero gradient at x forces f(y) ≥ f(x) for every y: a stationary point of a convex function is a global minimizer. This single fact is why gradient-based methods are so powerful on convex problems.

Remember two pictures: chords lie above the graph, tangents lie below it. Almost every convexity proof in this track uses one of them.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. f is convex when the graph never lies above

    The defining inequality says f at a mixed point is at most the chord height.
  2. 2. Which function is convex on the whole real line?

    eˣ has a positive second derivative everywhere. x³ and sin x change curvature; ln x is only defined for x > 0 and is concave.
  3. 3. Jensen's inequality for convex f states that

    The function of the average is at most the average of the function.
  4. 4. For a differentiable convex f, if ∇f(x) = 0 then x is

    The tangent inequality f(y) ≥ f(x) + 0 gives f(y) ≥ f(x) for all y.

Summary

  • Convex functions lie below their chords and above their tangents.
  • Standard convex examples: x², abs(x), eˣ, norms, -ln x, x ln x and affine functions.
  • Jensen's inequality generalizes the chord rule to averages.
  • For differentiable convex functions, zero gradient means global minimum.

Next: Testing Convexity with Derivatives