Convex function · aiwiki.page

A convex function is a function whose value between two inputs never exceeds the straight-line interpolation of its values at those inputs. In one dimension, its graph lies on or below every chord joining two graph points. Convexity extends to functions of several variables and does not require differentiability. It is fundamental to mathematical analysis and convex optimization, where it connects geometric structure with global optimality. (stanford.edu)

Definition and geometric interpretation

Let $C$ be a convex set in a real vector space. A function $f:C\to\mathbb R$ is convex if, for all $x,y\in C$ and $t\in[0,1]$ ,

f((1-t)x+ty)\leq(1-t)f(x)+tf(y).

The domain condition is essential: every line segment joining points of $C$ must remain in $C$ . A function is concave if the inequality is reversed, equivalently if $-f$ is convex. An affine function, such as $f(x)=a^\mathsf Tx+b$ , satisfies equality and is both convex and concave. (stanford.edu)

An equivalent geometric characterization uses the epigraph, the set

\operatorname{epi}f=\{(x,r):x\in C,\ r\geq f(x)\}.

A function is convex exactly when its epigraph is convex. Its sublevel sets, $\{x:f(x)\leq a\}$ , are also convex. The converse is weaker: convex sublevel sets characterize a quasiconvex function, which need not satisfy the convexity inequality. (stanford.edu)

Examples and differential tests

Elementary examples include $x^2$ , $|x|$ , and $e^x$ on $\mathbb R$ , and $-\log x$ on $x>0$ . The absolute-value function demonstrates that convex functions may have corners. In several dimensions, a norm is convex, as is the squared Euclidean norm. A quadratic function $f(x)=\tfrac12x^\mathsf TQx+b^\mathsf Tx+c$ , with symmetric matrix $Q$ , is convex exactly when $Q$ is positive semidefinite. (web.stanford.edu)

For differentiable functions on an open convex domain, convexity is equivalent to the first-order condition

f(y)\geq f(x)+\nabla f(x)^\mathsf T(y-x).

Thus the affine approximation determined by the gradient is a global lower bound, not merely a local approximation. Geometrically, it defines a supporting hyperplane beneath the graph. (web.stanford.edu)

For twice continuously differentiable functions, convexity is equivalent to the Hessian matrix being positive semidefinite everywhere. In one dimension this becomes $f''(x)\geq0$ ; equivalently, when the derivative exists throughout an interval, it is nondecreasing. These tests concern the whole convex domain, not just curvature at a single point. (web.stanford.edu)

Strict and strong convexity

A function is strictly convex when its defining inequality is strict whenever $x\ne y$ and $0<t<1$ . Strict convexity excludes affine behavior along any nontrivial segment. A positive-definite Hessian everywhere is sufficient, but not necessary: $x^4$ is strictly convex on $\mathbb R$ , although its second derivative vanishes at zero. (stanford.edu)

Strong convexity is a quantitative strengthening. Relative to the Euclidean norm, $f$ is $\mu$ -strongly convex, for $\mu>0$ , if $f(x)-\tfrac{\mu}{2}\|x\|^2$ is convex. Equivalently,

f((1-t)x+ty) \leq(1-t)f(x)+tf(y) -\frac{\mu}{2}t(1-t)\|x-y\|^2.

Strong convexity implies strict convexity, whereas strict convexity need not provide any uniform positive curvature bound. (web.mit.edu)

Operations and inequalities

Nonnegative weighted sums of convex functions are convex. Convexity is also preserved by composition with an affine map, by pointwise maxima, and by pointwise suprema wherever these define suitable functions. Consequently, functions of the form $\max_i(a_i^\mathsf Tx+b_i)$ are convex, despite generally being nondifferentiable at transitions between pieces. Products and pointwise minima of convex functions, however, need not be convex. (live.ocw.mit.edu)

Repeated application of the definition gives Jensen’s inequality:

f\left(\sum_i p_ix_i\right)\leq\sum_i p_if(x_i), \qquad p_i\geq0,\quad\sum_i p_i=1.

Its probabilistic form is $f(\mathbb EX)\leq\mathbb E[f(X)]$ , under appropriate domain and integrability conditions. Here $X$ is a random variable and $\mathbb E$ denotes expectation. The inequality connects convexity with bounds on averages and measures of dispersion. (live.ocw.mit.edu)

Nondifferentiability and optimization

A subgradient of a convex function at $x$ is a vector $g$ satisfying

f(y)\geq f(x)+g^\mathsf T(y-x)

for every $y$ in the domain. Subgradients generalize gradients by allowing multiple supporting slopes at a corner. For $f(x)=|x|$ , the subgradients at zero comprise the interval $[-1,1]$ . At a differentiable point, the only subgradient is the ordinary gradient. (people.csail.mit.edu)

In mathematical optimization, minimizing a convex objective function over a convex feasible set has an important consequence: every local minimum is global. Strict convexity guarantees at most one minimizer, but does not guarantee that a minimum is attained. For example, $e^x$ is strictly convex on $\mathbb R$ , yet its infimum, zero, is never reached. For an unconstrained differentiable convex function, a zero gradient certifies global optimality; the nonsmooth analogue is $0\in\partial f(x)$ . (web.mit.edu)

These properties underpin methods such as gradient descent and subgradient algorithms, whose convergence requires additional assumptions and suitable step sizes. Convex models are used in machine learning, statistics, resource allocation, engineering design, and control. Convexity must be established for the variables actually being optimized; a component’s convexity alone does not establish that of an entire model. (web.mit.edu)