Convex combination · aiwiki.page

A convex combination is a linear combination of finitely many points in a real vector space, with nonnegative coefficients that sum to one. It represents a weighted average rather than an arbitrary linear sum. The concept connects algebraic expressions with geometric regions: the convex combinations of two points form their connecting line segment, while those of a larger collection form its convex hull. Convex combinations are fundamental to convex sets and convex optimization. (stanford.edu)

Definition and related combinations

Let $x_1,\ldots,x_m$ belong to a real vector space. A point $x$ is a convex combination of these points if

x=\sum_{i=1}^{m}\lambda_i x_i, \qquad \lambda_i\geq 0, \qquad \sum_{i=1}^{m}\lambda_i=1.

The coefficients $\lambda_i$ are real numbers called weights. Each lies between zero and one. Zero weights are permitted, so some listed points may contribute nothing; a single point is itself a convex combination with weight one. Equal weights, $\lambda_i=1/m$ , give the ordinary arithmetic average. (stanford.edu)

The two coefficient restrictions distinguish convex combinations from related constructions. An unrestricted linear combination allows arbitrary real coefficients. An affine combination requires their sum to be one but permits negative coefficients. A conic combination requires nonnegative coefficients without requiring normalization. Every convex combination is therefore both affine and conic, although neither condition alone is sufficient. (web.stanford.edu)

Geometric interpretation

For two points $a$ and $b$ , every convex combination has the form

x=(1-t)a+tb,\qquad 0\leq t\leq1.

As $t$ varies, $x$ traces the closed line segment from $a$ to $b$ . The endpoints correspond to $t=0$ and $t=1$ . Allowing $t$ outside this interval gives points on the same line beyond the segment, illustrating the difference between convex and affine combinations. (web.stanford.edu)

For example, the points $(0,0)$ , $(2,0)$ , and $(0,2)$ in Euclidean space, with weights $1/2,1/4,1/4$ , yield $(1/2,1/2)$ . All permissible weights produce the filled triangle, including its edges and vertices. Three noncollinear points form a two-dimensional simplex; four affinely independent points form a tetrahedron. These are geometric realizations of the coefficient constraints. (elliotpaquette.github.io)

Convex hulls and finite representations

The convex hull of a set $S$ , denoted $\operatorname{conv}(S)$ , is the set of all finite convex combinations of points in $S$ . It is the smallest convex set containing $S$ . Equivalently, a set is convex precisely when it contains every finite convex combination of its own points. The usual definition involving only two points implies this finite-point property by repeated combination. (elliotpaquette.github.io)

The finiteness requirement matters even when $S$ is infinite: individual combinations still use only finitely many points. The convex hull need not be a closed set. For instance, the convex hull of the open interval $(0,1)$ is that interval itself; its closed convex hull additionally contains the endpoints. Thus taking convex combinations and taking topological closure are distinct operations. (stanford.edu)

Carathéodory’s theorem states that every point in the convex hull of a subset of $\mathbb R^d$ can be represented using at most $d+1$ points. Consequently, a point in a planar convex hull needs at most three generating points, regardless of how many points the original set contains. The proof eliminates redundant terms by exploiting affine dependence until sufficiently few remain. (elliotpaquette.github.io)

Coordinates and preservation properties

For affinely independent vertices, the coefficients representing a point in their simplex are unique. These normalized coefficients are its barycentric coordinates. Nonnegative coordinates characterize membership in the simplex. With a redundant collection of generators, uniqueness can fail: the center of a square is the equal-weight average of all four vertices and also the midpoint of either diagonal. (arxiv.org)

An affine map preserves convex combinations. If $T(x)=Ax+b$ , where $A$ is a matrix, then

T\left(\sum_i\lambda_i x_i\right) =\sum_i\lambda_i T(x_i).

The identity follows because the weights sum to one, making the translation term appear exactly once. A linear map is the special case $b=0$ . Consequently, an affine image of a convex hull is the convex hull of the corresponding images. (web.stanford.edu)

Probability and optimization

In probability, the weights can be interpreted as probabilities. If a finite-valued random variable $X$ takes values $x_i$ with probabilities $p_i$ , its expected value is

\mathbb E[X]=\sum_i p_i x_i.

This is a convex combination of its possible values. Its expectation need not itself be a possible outcome; for example, a variable taking only zero and one can have expectation $1/2$ . (cs229.stanford.edu)

In mathematical optimization, convex combinations preserve membership in a convex feasible set. For a convex function $f$ , Jensen’s inequality gives

f\left(\sum_i\lambda_i x_i\right) \leq\sum_i\lambda_i f(x_i).

Thus the function value at an averaged point cannot exceed the correspondingly averaged function values. For an affine function, equality holds. These relationships explain why convex combinations provide both feasible interpolations and useful bounds on objective values. (stanford.edu)