= Convex function
{title2=$f(tx+(1-t)y)\leq tf(x)+(1-t)f(y)$}
{wiki}
= Convexity
{synonym}
= Convex
{synonym}
A <function> $f:C\to\mathbb R$ on a <convex set> $C$ is a <convex function> if, for every $x,y\in C$ and $t\in[0,1]$,
$$
f(tx+(1-t)y)\leq tf(x)+(1-t)f(y).
$$
Geometrically, a <line segment> joining two points of its <graph of a function> lies on or above that <graph of a function>. The <convex set> condition ensures that the intermediate input stays in the <domain of a function>. An <affine function> satisfies the defining <inequality> with equality.
For the <quadratic function> $f(x)=x^2$, the inputs $1$ and $3$ have equally weighted <arithmetic mean> $2$. Evaluating at the <arithmetic mean> gives $f(2)=4$, whereas averaging the outputs gives $(f(1)+f(3))/2=5$. \b[Averaging first saves one unit in this example.] More generally, direct expansion gives
$$
tx^2+(1-t)y^2-[tx+(1-t)y]^2=t(1-t)(x-y)^2\geq0.
$$
This identity proves <convexity> and also shows exactly when its defining <inequality> is strict.
\Image[/convex-chord-and-tangent.png]
{title=The graph of a convex quadratic lies below its endpoint interpolation and above its supporting tangent}
{description=For $f(x)=x^2$, the <line segment> through $(1,1)$ and $(3,9)$ has height $5$ at $x=2$, while the <graph of a function> has height $4$. The <tangent line> $y=4x-4$ is an <affine minorant>: $x^2-(4x-4)=(x-2)^2\geq0$ everywhere.}
For a <differentiable> <convex function>, the <tangent line> in one dimension, or the corresponding supporting <affine function> in several dimensions, lies below the entire <graph of a function>. This is the <subgradient inequality>. The equivalent geometric statement is that the <epigraph>, consisting of points on or above the <graph of a function>, is a <convex set>. These characterizations are developed in https://stanford.edu/~boyd/cvxbook/bv_cvxslides.pdf[Boyd and Vandenberghe's convex-function slides, sections 3.1–3.4].
<Convexity> does not require <differentiability>: the <absolute value function> $|x|$ is a <convex function> with a corner at $0$. When a <function> is twice continuously <differentiable> on an open <interval>, it is a <convex function> exactly when its <second derivative> is nonnegative throughout that <interval>. In several dimensions, the corresponding criterion on an open <convex set> is that its <Hessian matrix> is <positive semidefinite> everywhere. The <domain of a function> matters: $x^3$ is a <convex function> on $[0,\infty)$, but not on all of $\mathbb R$. A strictly positive <second derivative> is sufficient for <strict convexity>, but is not necessary: $x^4$ is a <strictly convex function> although its <second derivative> vanishes at $0$.
The usefulness of <convexity> is that local information can certify a global conclusion. Every <local minimum> of a <convex function> on a <convex set> is a <global minimum>: if a lower value existed elsewhere, the defining <inequality> would produce lower values arbitrarily close to the proposed <local minimum>. For a <differentiable> <convex function> on an open <convex set>, a zero <gradient> therefore certifies a <global minimum>. <Strict convexity> gives uniqueness when a <global minimum> exists; it does not supply existence by itself. These facts explain the role of <convex functions> in <convex optimization>.
Back to article page
