Convex Optimization 2026, 07 - Basic Properties of Convex Functions

A function is convex if its domain is a convex set and for all x, y ∈ dom f, θ with 0 ≤ θ ≤ 1: f(θx + (1 - θ)y) ≤ θf(x) + (1 - θ)f(y) (3.1.1). This is known as Jensen's inequality. Geometrically, this places all line segments between (x, f(x)) and (y, f(y)) lies above the graph of f. If f is convex, then -f is concave. Convex functions can be extended to all of ℝⁿ by setting it to ∞ outside of dom f. The domain of the original function can be recovered from the extended-value extension by identifying all points, at which the extension is finite, Concave functions can be extended to be -∞ instead (3.1.2).

A differentiable function f is convex iff dom f is convex, and f(y) ≥ f(x) + ∇f(x)^T(y - x) ∀ x, y ∈ dom f (Eq. 3.2). The affine function f(x) + ∇f(x)^T(y - x) is the first-order Taylor expansion of f around x. It's a global underestimator of the function (3.1.3.). Strict convexity can be characterized by a first-order condition: f is strictly convex iff dom f is convex and for nonequal x, y in dom f, f(y) > f(x) + ∇f(x)^T(y - x). For concave, take the converse of that inequality. Assuming f is twice differentiable (Hessian), and dom f is open, the f is convex iff dom f is convex and if ∇²f is positive-semidefinite (3.1.4).

Define an α-sublevel set of a function f: ℝⁿ → ℝ as C_α = { x ∈ dom f | f(x) ≤ α }. Sublevel sets of convex functions are convex for all α. The converse is not true (3.1.6).

Define an epigraph of a function f: ℝⁿ → ℝ as epi f = {(x, t) | x ∈ dom f, f(x) ≤ t }. epi f is a subset of ℝ^{n + 1}. A function is convex iff its epigraph is a convex set. The analogous approach for concave functions defines the hypograph hypo f = {(x, t) | t ≤ f(x)}, which is a convex set (3.1.7).

A convex function can be extended by generalizing Jensen's inequality to any number of variables, so that f(θ₁x₁ + ... + θ_kx_k) ≤ θ₁f(x₁) + ... + θ_kf(x_k). For convex sets, it extends to infinite sums, integrals and expectation values (3.1.8).