Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 38 · Convex Sets and Functions

Operations That Preserve Convexity

Build complicated convex functions from simple ones: non-negative sums, pointwise maximum, affine composition and more, with numerical checks in Python.

In practice you rarely test convexity from scratch. You recognize that a complicated function is built from convex pieces using operations that are known to keep convexity. This is the "calculus of convexity", and it is the main skill of anyone who models problems for convex solvers. Learn six rules and you can certify most functions you meet.

Rule 1: non-negative multiples

If f is convex and α ≥ 0, then α·f is convex. Multiplying by a negative number flips the bowl upside down, so it does not work for α < 0.

Rule 2: sums

If f and g are convex, so is f + g. Chords of each add up, so the sum stays below its chord. Combined with Rule 1, any non-negative combination α₁f₁ + α₂f₂ + ... of convex functions is convex. This is why regularized objectives such as "error + λ·penalty" (with λ ≥ 0) are convex when both parts are.

Rule 3: composition with an affine map

If f is convex, then g(x) = f(Ax + b) is convex. Stretching, shifting or rotating the input does not change the bowl shape. This lets you build ‖Ax - b‖² (least squares) from the convex function ‖·‖².

Rule 4: pointwise maximum

If f₁, ..., fₖ are convex, then max(f₁(x), ..., fₖ(x)) is convex. The same holds for the supremum of infinitely many convex functions. Intuition: each fᵢ lies below its chord, so the highest of them does too.

Examples: max(x, -x) = |x| is convex, built from two linear functions. The hinge max(0, 1 - t) is convex and is the loss used in support vector machines.

Python The maximum of convex functions

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.

Rule 5: composition rules in one variable

For h(g(x)) where h is a scalar function:

g is h is h is Then h∘g is
convex convex non-decreasing convex
concave convex non-increasing convex

Example: exp(f(x)) with f convex is convex, because exp is convex and increasing. Example: 1/g(x) with g concave and positive is convex, because 1/t is convex and decreasing for t > 0. Be careful: (f(x))² with a convex f is convex only when f ≥ 0, because t² is increasing only for t ≥ 0. Take f(x) = x² - 1: its square is x⁴ - 2x² + 1, a double-well, not convex.

Python Careful with composition

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 first and third lines should show zero violations; the middle one shows many.

Rule 6: partial minimization

If f(x, y) is jointly convex in (x, y) and C is a convex set of y, then g(x) = min over y in C of f(x, y) is convex in x. This is used, for example, to show that the distance from a point to a convex set is a convex function.

Putting the rules to work

Is F(x) = ‖Ax - b‖² + λ‖x‖₁ + max(0, cᵀx - d) convex for λ ≥ 0? Yes:

  • ‖Ax - b‖²: the convex function ‖·‖² composed with an affine map.
  • λ‖x‖₁: a norm is convex, times λ ≥ 0.
  • max(0, cᵀx - d): maximum of two convex (affine) functions.
  • The sum of convex functions is convex.
Python Verify a composite objective numerically

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 count is zero, as the rules predict. If you change lam to a negative number, violations can appear, because Rule 1 no longer applies.

flowchart TD
    A["Start with known convex pieces"] --> B["Scale by non-negative numbers"]
    B --> C["Add them"]
    C --> D["Take pointwise maximum"]
    D --> E["Compose with affine maps"]
    E --> F["Result is convex"]

A recipe for building convex objectives.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which operation does NOT in general preserve convexity?

    Multiplying by a negative number turns a convex function into a concave one.
  2. 2. Why is max(0, 1 - t) convex?

    Both 0 and 1 - t are affine, and a pointwise maximum of convex functions is convex.
  3. 3. Is exp(x² - 1) convex?

    Convex, non-decreasing outer function applied to a convex inner function gives a convex function.
  4. 4. For a convex f that can be negative, (f(x))² is

    t² is not increasing for negative t, so the composition rule does not apply (x² - 1 squared is a double-well).

Summary

  • Non-negative multiples, sums, affine composition and pointwise maxima preserve convexity.
  • Composition h(g(x)) needs the right mix of convexity and monotonicity.
  • Many real objectives (least squares, hinge loss, norms) are certified convex by combining these rules.
  • A numerical chord test is a quick safety net.

Next: Convex Optimization Problems and Optimality