Convex combination (original) (raw)

From Wikipedia, the free encyclopedia

Linear combination of points where all coefficients are non-negative and sum to 1

Given three points x 1 , x 2 , x 3 {\displaystyle x_{1},x_{2},x_{3}} {\displaystyle x_{1},x_{2},x_{3}} in a plane as shown in the figure, the point P {\displaystyle P} {\displaystyle P} is a convex combination of the three points, while Q {\displaystyle Q} {\displaystyle Q} is not. ( Q {\displaystyle Q} {\displaystyle Q} is however an affine combination of the three points, as their affine hull is the entire plane.)

Convex combination of two points v 1 , v 2 ∈ R 2 {\displaystyle v_{1},v_{2}\in \mathbb {R} ^{2}} {\displaystyle v_{1},v_{2}\in \mathbb {R} ^{2}} in a two dimensional vector space R 2 {\displaystyle \mathbb {R} ^{2}} {\displaystyle \mathbb {R} ^{2}} as animation in Geogebra with t ∈ [ 0 , 1 ] {\displaystyle t\in [0,1]} {\displaystyle t\in [0,1]} and K ( t ) := ( 1 − t ) ⋅ v 1 + t ⋅ v 2 {\displaystyle K(t):=(1-t)\cdot v_{1}+t\cdot v_{2}} {\displaystyle K(t):=(1-t)\cdot v_{1}+t\cdot v_{2}}

Convex combination of three points v 0 , v 1 , v 2 of 2 -simplex ∈ R 2 {\displaystyle v_{0},v_{1},v_{2}{\text{ of }}2{\text{-simplex}}\in \mathbb {R} ^{2}} {\displaystyle v_{0},v_{1},v_{2}{\text{ of }}2{\text{-simplex}}\in \mathbb {R} ^{2}} in a two dimensional vector space R 2 {\displaystyle \mathbb {R} ^{2}} {\displaystyle \mathbb {R} ^{2}} as shown in animation with α 0 + α 1 + α 2 = 1 {\displaystyle \alpha ^{0}+\alpha ^{1}+\alpha ^{2}=1} {\displaystyle \alpha ^{0}+\alpha ^{1}+\alpha ^{2}=1}, P ( α 0 , α 1 , α 2 ) {\displaystyle P(\alpha ^{0},\alpha ^{1},\alpha ^{2})} {\displaystyle P(\alpha ^{0},\alpha ^{1},\alpha ^{2})} := α 0 v 0 + α 1 v 1 + α 2 v 2 {\displaystyle :=\alpha ^{0}v_{0}+\alpha ^{1}v_{1}+\alpha ^{2}v_{2}} {\displaystyle :=\alpha ^{0}v_{0}+\alpha ^{1}v_{1}+\alpha ^{2}v_{2}} . When P is inside of the triangle α i ≥ 0 {\displaystyle \alpha _{i}\geq 0} {\displaystyle \alpha _{i}\geq 0}. Otherwise, when P is outside of the triangle, at least one of the α i {\displaystyle \alpha _{i}} {\displaystyle \alpha _{i}} is negative.

Convex combination of four points A 1 , A 2 , A 3 , A 4 ∈ R 3 {\displaystyle A_{1},A_{2},A_{3},A_{4}\in \mathbb {R} ^{3}} {\displaystyle A_{1},A_{2},A_{3},A_{4}\in \mathbb {R} ^{3}} in a three dimensional vector space R 3 {\displaystyle \mathbb {R} ^{3}} {\displaystyle \mathbb {R} ^{3}} as animation in Geogebra with ∑ i = 1 4 α i = 1 {\displaystyle \sum _{i=1}^{4}\alpha _{i}=1} {\displaystyle \sum _{i=1}^{4}\alpha _{i}=1} and ∑ i = 1 4 α i ⋅ A i = P {\displaystyle \sum _{i=1}^{4}\alpha _{i}\cdot A_{i}=P} {\displaystyle \sum _{i=1}^{4}\alpha _{i}\cdot A_{i}=P}. When P is inside of the tetrahedron α i >= 0 {\displaystyle \alpha _{i}>=0} {\displaystyle \alpha _{i}>=0}. Otherwise, when P is outside of the tetrahedron, at least one of the α i {\displaystyle \alpha _{i}} {\displaystyle \alpha _{i}} is negative.

Convex combination of two functions as vectors in a vector space of functions - visualized in Open Source Geogebra with [ a , b ] = [ − 4 , 7 ] {\displaystyle [a,b]=[-4,7]} {\displaystyle [a,b]=[-4,7]} and as the first function f : [ a , b ] → R {\displaystyle f:[a,b]\to \mathbb {R} } {\displaystyle f:[a,b]\to \mathbb {R} } a polynomial is defined. f ( x ) := 3 10 ⋅ x 2 − 2 {\displaystyle f(x):={\frac {3}{10}}\cdot x^{2}-2} {\displaystyle f(x):={\frac {3}{10}}\cdot x^{2}-2} A trigonometric function g : [ a , b ] → R {\displaystyle g:[a,b]\to \mathbb {R} } {\displaystyle g:[a,b]\to \mathbb {R} } was chosen as the second function. g ( x ) := 2 ⋅ cos ⁡ ( x ) + 1 {\displaystyle g(x):=2\cdot \cos(x)+1} {\displaystyle g(x):=2\cdot \cos(x)+1} The figure illustrates the convex combination K ( t ) := ( 1 − t ) ⋅ f + t ⋅ g {\displaystyle K(t):=(1-t)\cdot f+t\cdot g} {\displaystyle K(t):=(1-t)\cdot f+t\cdot g} of f {\displaystyle f} {\displaystyle f} and g {\displaystyle g} {\displaystyle g} as graph in red color.

In convex geometry and vector algebra, a convex combination is a linear combination of points (which can be vectors, scalars, or more generally points in an affine space) where all coefficients are non-negative and sum to 1.[1] In other words, the operation is equivalent to a standard weighted average, but whose weights are expressed as a percent of the total weight, instead of as a fraction of the count of the weights as in a standard weighted average.

More formally, given a finite number of points x 1 , x 2 , … , x n {\displaystyle x_{1},x_{2},\dots ,x_{n}} {\displaystyle x_{1},x_{2},\dots ,x_{n}} in a real vector space, a convex combination of these points is a point of the form

α 1 x 1 + α 2 x 2 + ⋯ + α n x n {\displaystyle \alpha _{1}x_{1}+\alpha _{2}x_{2}+\cdots +\alpha _{n}x_{n}} {\displaystyle \alpha _{1}x_{1}+\alpha _{2}x_{2}+\cdots +\alpha _{n}x_{n}}

where the real numbers α i {\displaystyle \alpha _{i}} {\displaystyle \alpha _{i}} satisfy α i ≥ 0 {\displaystyle \alpha _{i}\geq 0} {\displaystyle \alpha _{i}\geq 0} and α 1 + α 2 + ⋯ + α n = 1. {\displaystyle \alpha _{1}+\alpha _{2}+\cdots +\alpha _{n}=1.} {\displaystyle \alpha _{1}+\alpha _{2}+\cdots +\alpha _{n}=1.}[1]

As a particular example, every convex combination of two points lies on the line segment between the points.[1]

A set is convex if it contains all convex combinations of its points. The convex hull of a given set of points is identical to the set of all their convex combinations.[1]

There exist subsets of a vector space that are not closed under linear combinations but are closed under convex combinations. For example, the interval [ 0 , 1 ] {\displaystyle [0,1]} {\displaystyle [0,1]} is convex but generates the real-number line under linear combinations. Another example is the convex set of probability distributions, as linear combinations preserve neither nonnegativity nor affinity (i.e., having total integral one).

  1. ^ a b c d Rockafellar, R. Tyrrell (1970), Convex Analysis, Princeton Mathematical Series, vol. 28, Princeton University Press, Princeton, N.J., pp. 11–12, MR 0274683