Skip to content
Glacius
OptimizationConcept reference

Convex functions

Convexity requires the function at every mixture to lie at or below the corresponding weighted endpoint values.

2 min read1 figureSources & further reading
On this page 8 sections
  1. Overview
  2. Understand the idea
  3. If function values are supplied, form the weighted chord directly
  4. Convexity is an all-pairs, all-weights condition
  5. To disprove convexity, one valid chord violation is enough
  6. Key takeaway
  7. Sources & further reading
  8. Concept connections

01Understand the idea#

A convex function lies below straight chords connecting points on its graph, over a convex domain. The condition makes averaging two inputs no worse than averaging their endpoint objective values. Convexity is useful because a local minimum of a convex objective on a convex domain is also global.

For a convex function, evaluating at a mixture gives no larger a value than mixing the endpoint values. The domain must also be convex.

f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)\begin{gathered}f(\theta x+(1-\theta)y)\\\le\theta f(x)+(1-\theta)f(y)\end{gathered}

This must hold for all domain points and 0≤θ≤1.

For f(x)=x², midpoint 2 between 0 and 4 has value 4. The endpoint-value average is 8, so this comparison satisfies 4≤8.

For f(x)=x², the chord joins (0,0) and (4,16). At their midpoint input 2, the curve has height 4 while the chord has height 8. The curve lies below this chord; this example illustrates the convexity inequality without proving it for all pairs.For f(x)=x², the chord joins (0,0) and (4,16). At their midpoint input 2, the curve has height 4 while the chord has height 8. The curve lies below this chord; this example illustrates the convexity inequality without proving it for all pairs.
Figure 1For f(x)=x², the chord joins (0,0) and (4,16). At their midpoint input 2, the curve has height 4 while the chord has height 8. The curve lies below this chord; this example illustrates the convexity inequality without proving it for all pairs.
Link to this figure ↗Download SVGDownload PNG

For f(x)=x2f(x)=x^2 between inputs 0 and 4, the midpoint input is 2 and its function value is 4. The midpoint of endpoint heights is (0+16)/2=8(0+16)/2=8. Thus the graph lies below that chord at the midpoint. This is one verified comparison, not a proof for all pairs of inputs.

Check your reasoning

f(z)=z² on all real z. x=1, y=5, θ=0.5. Give (f(θx+(1−θ)y), θf(x)+(1−θ)f(y)).

  1. A(9,14)(9, 14)
  2. B(9,13)(9, 13)
  3. C(10,13)(10, 13)
Show answer and explanation
(9,13)(9, 13)

Mixed input 3: left 9, chord 13.

02If function values are supplied, form the weighted chord directly#

If function values are supplied, form the weighted chord directly. Subtract the actual mixed-input value to see how much room the inequality has.

A nonnegative gap passes this comparison; a negative gap is a violation. Equality is allowed in ordinary convexity.

Check your reasoning

x,y are in a convex domain; θ=0.25. Given (f(x),f(y),f(θx+(1−θ)y))=(4, 12, 9). Find chord value minus mixed-input value.

Show answer and explanation
1

Chord 10 minus 9 gives 1.

03Convexity is an all-pairs, all-weights condition#

Convexity is an all-pairs, all-weights condition. One passing example cannot establish it over the whole domain.

One valid violation is enough to disprove it. A single low point in a plot is also insufficient evidence of the universal inequality.

Check your reasoning

On a convex domain, a valid mixture gives left side 6, chord 4. Assess convexity: f(mixture)≤chord.

  1. AProved.
  2. BUndefined.
  3. CDisproved.
Show answer and explanation
Disproved.

6>4 violates the rule.

04To disprove convexity, one valid chord violation is enough#

To disprove convexity, one valid chord violation is enough. To establish it, every allowed pair and mixture must satisfy the condition. Real training objectives need not be convex, so the useful local-to-global guarantee cannot be assumed just because an optimizer found a low point.

Key takeaway

Compute both sides; one violation disproves convexity, while one passing comparison does not prove it.

  • Check the convexity inequality for a supplied scalar example.

Sources & further reading

  1. [1]
    Boyd & Vandenberghe §3.1.1 ↗Boyd & Vandenberghe §3.1.1 · Article

Reference this concept

Link to this page, a section, or an individual figure.

Glacius. “Convex functions.” Math behind ML. /learn/o-convex-function