Convex sets and convex functions

Convexity is the single most important structural property in optimisation. Convex problems are tractable; non-convex problems generally are not. Every local minimum of a convex function over a convex set is a global minimum. This makes 'is my problem convex?' the first question to ask, and 'can I make it convex?' the second.

Convex set

A set C is convex if for any x, y ∈ C and any λ ∈ [0, 1], the point λx + (1-λ)y ∈ C. Geometrically: the line segment between any two points in C lies entirely in C. Examples: halfspaces, hyperplanes, balls, ellipsoids, intersections of any of the above. Non-examples: a 'donut', an annulus, the integers.

Convex function

A function f: Rⁿ → R is convex if its domain is a convex set and for all x, y in the domain and λ ∈ [0, 1]:

f(λx + (1-λ)y) ≤ λ f(x) + (1-λ) f(y)

The chord lies above the graph. f is strictly convex if the inequality is strict (for λ ∈ (0,1), x ≠ y). Strict convexity implies unique global minimum (when it exists).

Three convexity tests

• Zeroth-order: definition. Hard to verify by hand for non-obvious functions.
• First-order: f differentiable, then f convex iff f(y) ≥ f(x) + ∇f(x)ᵀ(y - x) for all x, y. Tangent below graph.
• Second-order: f twice differentiable, then f convex iff Hessian ∇²f(x) ⪰ 0 (PSD) for all x. Strictly convex iff Hessian PD.

Operations that preserve convexity

• Non-negative combinations: α₁ f₁ + α₂ f₂ convex if α_i ≥ 0 and f_i convex.
• Pointwise maximum: max(f₁, f₂) convex if both convex.
• Composition with affine: f(Ax + b) convex if f convex.
• Composition with convex non-decreasing outer function preserves convexity of the inner.
• Restriction to a convex subset preserves convexity.

Convex functions in finance

• Quadratic forms wᵀΣw with Σ PSD — portfolio variance.
• p-norms ‖x‖_p for p ≥ 1 — regularisers, transaction-cost models.
• Maximum of linear functions — payoff of a max option, robust-cost objectives.
• log-sum-exp Σ log(1 + e^xᵢ) — soft-max approximations to constraints.
• Negative log-likelihoods of exponential-family distributions — MLE objectives.

Concave functions

f is concave iff -f is convex. Maximising a concave function = minimising a convex function — same machinery. Mean-variance utility is typically maximised; written as max μᵀw - (λ/2) wᵀΣw, with λ > 0, this is a concave objective and a strictly convex minimisation problem in disguise.

Common non-convexities and convex substitutes

• Cardinality constraint (≤ k non-zero weights): non-convex. L¹ norm penalty is the convex relaxation.
• Boolean indicators (in/out): non-convex. Replace with [0, 1] continuous if context allows.
• Round-lot / integer constraints: non-convex. Use continuous solution + post-rounding when shares cheap.
• Maximum drawdown constraint: non-convex in path. Replace with CVaR-like surrogates.