A Function is convex over some if it satisfies the inequality
f(αx+βy)≤αf(x)+βf(y)
for all x,y∈D (where D is the domain) and all α,β∈R with α+β=1,α≥0,β≥0 (i.e. this is a Convex combination
The domain D has to be a Convex set for this to be defined
Intuitively, a convex function is one for which the weighted average of the inputs produces at most the same weighted averages of the outputs.
Equivalent conditions for differentiable functions
- Once-differentiable. Tangent is lower bound. g(y)+∇g(y)T(x−y)≤g(x).
- If the function is twice Differentiable, then it is convex iff f′′≥0. For multivariate, Hessian has to be positive semi-definite. This can be proved as shown in page 26 of Elements of info theory by Cover and Thomas. Needs the Cauchy form of Taylor's theorem
Relations to Convex sets
All the points above the function (the function's Epigraph) form a convex set (vid)
Also Level sets of convex functions are convex
Operations that preserve convexity
- Non-negative weighted sums of convex functions. If you allow negative weights, we get a problem of Difference of convex functions.
- Pointwise maximum of the functions.