Convex combination

Last updated
Given three points
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}
is a convex combination of the three points, while
Q
{\displaystyle Q}
is not.
(
Q
{\displaystyle Q}
is however an affine combination of the three points, as their affine hull is the entire plane.) Convex combination illustration.svg
Given three points in a plane as shown in the figure, the point is a convex combination of the three points, while is not.
( is however an affine combination of the three points, as their affine hull is the entire plane.)

In convex geometry, 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]

Contents

More formally, given a finite number of points in a real vector space, a convex combination of these points is a point of the form

where the real numbers satisfy and [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 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).

Other objects

See also

Related Research Articles

Convex set In geometry, set that intersects every line into a single line segment

In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points, it contains the whole line segment that joins them. Equivalently, a convex set or a convex region is a subset that intersect every line into a single line segment . For example, a solid cube is a convex set, but anything that is hollow or has an indent, for example, a crescent shape, is not convex.

Basis (linear algebra) Subset of a vector space that allows defining coordinates

In mathematics, a set B of vectors in a vector space V is called a basis if every element of V may be written in a unique way as a finite linear combination of elements of B. The coefficients of this linear combination are referred to as components or coordinates of the vector with respect to B. The elements of a basis are called basis vectors.

Convex hull The smallest convex set containing a given set

In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.

In mathematics, a linear combination is an expression constructed from a set of terms by multiplying each term by a constant and adding the results. The concept of linear combinations is central to linear algebra and related fields of mathematics. Most of this article deals with linear combinations in the context of a vector space over a field, with some generalizations given at the end of the article.

In mathematics, a linear form is a linear map from a vector space to its field of scalars.

Affine space Geometric structure that generalizes the Euclidean space

In mathematics, an affine space is a geometric structure that generalizes some of the properties of Euclidean spaces in such a way that these are independent of the concepts of distance and measure of angles, keeping only the properties related to parallelism and ratio of lengths for parallel line segments.

In mathematics, an affine combination of x1, ..., xn is a linear combination

Linear differential equation Differential equations that are linear with respect to the unknown function and its derivatives

In mathematics, a linear differential equation is a differential equation that is defined by a linear polynomial in the unknown function and its derivatives, that is an equation of the form

In functional analysis and related areas of mathematics, locally convex topological vector spaces (LCTVS) or locally convex spaces are examples of topological vector spaces (TVS) that generalize normed spaces. They can be defined as topological vector spaces whose topology is generated by translations of balanced, absorbent, convex sets. Alternatively they can be defined as a vector space with a family of seminorms, and a topology can be defined in terms of that family. Although in general such spaces are not necessarily normable, the existence of a convex local base for the zero vector is strong enough for the Hahn–Banach theorem to hold, yielding a sufficiently rich theory of continuous linear functionals.

Carathéodorys theorem (convex hull) A point in the convex hull of a set P in Rd, is the convex combination of d+1 points in P

Carathéodory's theorem is a theorem in convex geometry. It states that if a point x of Rd lies in the convex hull of a set P, then x can be written as the convex combination of at most d + 1 points in P. Namely, there is a subset P′ of P consisting of d + 1 or fewer points such that x lies in the convex hull of P′. Equivalently, x lies in an r-simplex with vertices in P, where . The smallest r that makes the last statement valid for each x in the convex hull of P is defined as the Carathéodory's number of P. Depending on the properties of P, upper bounds lower than the one provided by Carathéodory's theorem can be obtained. Note that P need not be itself convex. A consequence of this is that P′ can always be extremal in P, as non-extremal points can be removed from P without changing the membership of x in the convex hull.

Real coordinate space Space formed by the n-tuples of real numbers

In mathematics, a real coordinate space of dimension n, written Rn or n, is a coordinate space over the real numbers. This means that it is the set of the n-tuples of real numbers. With component-wise addition and scalar multiplication, it is a real vector space.

Convex polytope

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.

In mathematics, the affine hull or affine span of a set S in Euclidean space Rn is the smallest affine set containing S, or equivalently, the intersection of all affine sets containing S. Here, an affine set may be defined as the translation of a vector subspace.

Convex cone subset of a vector space closed under positive linear combinations

In linear algebra, a convex cone is a subset of a vector space over an ordered field that is closed under linear combinations with positive coefficients.

In mathematics, Choquet theory, named after Gustave Choquet, is an area of functional analysis and convex analysis concerned with measures which have support on the extreme points of a convex set C. Roughly speaking, every vector of C should appear as a weighted average of extreme points, a concept made more precise by generalizing the notion of weighted average from a convex combination to an integral taken over the set E of extreme points. Here C is a subset of a real vector space V, and the main thrust of the theory is to treat the cases where V is an infinite-dimensional topological vector space along lines similar to the finite-dimensional case. The main concerns of Gustave Choquet were in potential theory. Choquet theory has become a general paradigm, particularly for treating convex cones as determined by their extreme rays, and so for many different notions of positivity in mathematics.

Affine geometry, broadly speaking, is the study of the geometrical properties of lines, planes, and their higher dimensional analogs, in which a notion of "parallel" is retained, but no metrical notions of distance or angle are. Affine spaces differ from linear spaces in that they do not have a distinguished choice of origin. So, in the words of Marcel Berger, "An affine space is nothing more than a vector space whose origin we try to forget about, by adding translations to the linear maps." Accordingly, a complex affine space, that is an affine space over the complex numbers, is like a complex vector space, but without a distinguished point to serve as the origin.

Gauss–Lucas theorem Geometric relation between the roots of a polynomial and those of its derivative

In complex analysis, a branch of mathematics, the Gauss–Lucas theorem gives a geometrical relation between the roots of a polynomial P and the roots of its derivative P′. The set of roots of a real or complex polynomial is a set of points in the complex plane. The theorem states that the roots of P′ all lie within the convex hull of the roots of P, that is the smallest convex polygon containing the roots of P. When P has a single root then this convex hull is a single point and when the roots lie on a line then the convex hull is a segment of this line. The Gauss–Lucas theorem, named after Carl Friedrich Gauss and Félix Lucas, is similar in spirit to Rolle's theorem.

Given a finite number of vectors in a real vector space, a conical combination, conical sum, or weighted sum of these vectors is a vector of the form

In algebra, a multivariate polynomial

Glossary of Lie groups and Lie algebras Wikipedia glossary

This is a glossary for the terminology applied in the mathematical theories of Lie groups and Lie algebras. For the topics in the representation theory of Lie groups and Lie algebras, see Glossary of representation theory. Because of the lack of other options, the glossary also includes some generalizations such as quantum group.

References

  1. 1 2 3 4 Rockafellar, R. Tyrrell (1970), Convex Analysis, Princeton Mathematical Series, 28, Princeton University Press, Princeton, N.J., pp. 11–12, MR   0274683