Why is the pointwise maximum of two linear functions convex despite its kink?

## Convexity does not require smoothness The definition of a convex function is the chord inequality on a convex domain, ``` f(t*x + (1 - t)*y) <= t*f(x) + (1 - t)*f(y) for all t in [0, 1] ``` No derivative appears anywhere in it. So the presence of a corner in the graph — a point where the slope jumps — is entirely compatible with convexity. Familiar convex functions with corners include `max(0, x)`, the absolute value, and any piecewise-linear function whose slopes increase from left to right. (The converse direction is worth knowing: a convex function on an *open* interval is automatically continuous there. Convexity buys you continuity for free, just not differentiability.) ## The proof that a pointwise max is convex Let `f1, ..., fk` be convex on a common convex domain and define `f(x) = max_i f_i(x)`. Fix `x, y` and `t` in `[0, 1]`, and write `z = t*x + (1 - t)*y`. For each index `i`: ``` f_i(z) <= t*f_i(x) + (1 - t)*f_i(y) (f_i is convex) <= t*f(x) + (1 - t)*f(y) (f_i <= f pointwise, t and 1-t are >= 0) ``` The right-hand side does not depend on `i`, so it also bounds the maximum over `i`, which is `f(z)`. That is exactly the chord inequality for `f`. Two features of the argument matter: the weights `t` and `1 - t` are non-negative, so the inequalities may be multiplied through without flipping; and nothing about the number of functions was used, so the same proof covers the **pointwise supremum of an arbitrary family** of convex functions, as long as the supremum is finite. Specialising to two affine functions `f1(x) = a1 . x + b1` and `f2(x) = a2 . x + b2`: each is convex (affine functions satisfy the chord condition with equality), so their max is convex. Geometrically the graph is two half-lines meeting at a crease that points **downward** — the region above the graph is still a convex set, which is the epigraph view of the same fact. ## Why this rule earns its keep Most convex objectives in practice are assembled, not verified. The three workhorse rules are: - a **non-negative weighted sum** of convex functions is convex; - **composition with an affine map**, `x -> f(A*x + b)`, preserves convexity; - the **pointwise maximum or supremum** of convex functions is convex. The third is the one that generates non-smooth convex objectives: piecewise-linear penalties, the maximum violation across a set of constraints, worst-case objectives of the form `max over scenarios`, and every norm (a norm is the supremum of linear functions over the unit ball of the dual norm). Recognising an objective as a max of convex pieces certifies convexity instantly, where trying to differentiate twice would stall at the kink. ## The minimum is not convex Symmetry is tempting but wrong: the pointwise **minimum** of convex functions is generally not convex. Take `f1(x) = x^2` and `f2(x) = (x - 3)^2` and let `g = min(f1, f2)`. Then `g(0) = 0` and `g(3) = 0`, so the chord between those points sits at height `0`, but `g(1.5) = 2.25 > 0`. The graph rises above its own chord, so `g` is not convex. The failure of the proof above is easy to see: `f_i >= g` gives an inequality in the unhelpful direction. ## Log-sum-exp A closely related function is `lse(a, b) = log(exp(a) + exp(b))`, which is convex and, unlike the max, infinitely differentiable. It brackets the max tightly: ``` max(a, b) <= log(exp(a) + exp(b)) <= max(a, b) + log 2 ``` The lower bound holds because `exp(a) + exp(b) >= exp(max(a, b))`; the upper bound because `exp(a) + exp(b) <= 2*exp(max(a, b))`. With `n` arguments the gap is at most `log n`. So log-sum-exp is a smooth convex surrogate that sits just above the max, which is why it appears wherever a differentiable stand-in for a maximum is wanted. Note the direction of the claim precisely: it is the max that has the kink, and log-sum-exp that smooths it — asserting the reverse is a common slip.