[TOC]
A norm is a function that gives a strictly positive value to a vector or a variable.
Norm is a function f:Rn→R
Norm is a continuous function.
Let X be a vector such that X∈Rn, then
‖αx‖= | α | ‖x‖∀x∈Xandαisascalar |
By definition, norm is calculated as follows:
‖x‖1=n∑i=1 | xi |
‖x‖2=(n∑i=1 | xi | 2)12 |
‖x‖p=(n∑i=1 | xi | p)1p,1≤p≤∞ |
Inner product is a function which gives a scalar to a pair of vectors. Inner Product − f:ℝn×ℝn→κ where κ is a scalar.
Let X∈ℝn,
NOTE
Let S⊆Rn, A set S is said to be convex if the line segment joining any two points of the set S also belongs to the S, i.e., if x1,x2∈S, then λx1+(1−λ)x2∈Swhere λ∈(0,1).
A set A is said to be an affine set if for any two distinct points, the line passing through these points lie in the set A.
NOTE
If C is an affine set and x0∈C, then the set V=C−x0={x−x0:x∈C} is a subspace of C.
The convex hull of a set of points in S is the boundary of the smallest convex region that contain all the points of S inside it or on its boundary.
OR
Let S⊆ℝn, The convex hull of S, denoted Co(S) by is the collection of all convex combination of S, i.e., x∈Co(S) if and only if x∈n∑i=1λixi, where n∑1λi=1 and λi≥0 ∀xi∈S.
Conves hull of a set of points in S in the plane defines a convex polygon and the points of S on the boundary of the polygon defines the vertices of the polygon.
Co(S)={x:x=n∑i=1λixi,xi∈S,n∑i=1λi=1,λi≥0} Show that a convex hull is a convex set.
In convex geometry, Carathéodory’s theorem states that if a point x of R^d lies in the convex hull of a set P, 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, xlies 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.
Consider a set P = {(0,0), (0,1), (1,0), (1,1)} which is a subset of R2. The convex hull of this set is a square. Consider now a point x = (1/4, 1/4), which is in the convex hull of P. We can then construct a set {(0,0),(0,1),(1,0)} = P′, the convex hull of which is a triangle and encloses x, and thus the theorem works for this instance, since | P′ | = 3. It may help to visualise Carathéodory’s theorem in 2 dimensions, as saying that we can construct a triangle consisting of points from P that encloses any point in P. |
Let x be a point in the convex hull of P. Then, x is a convex combination of a finite number of points in P :, where every xj is in P, every λj is strictly positive, and
Suppose k > d + 1 (otherwise, there is nothing to prove). Then, the points x2 − x1, …, xk − x1 are linearly dependent, so there are real scalars μ2, …, μk, not all zero, such that , if If μ1 is defined as , then , . and not all of the μj are equal to zero. Therefore, at least one μj > 0. Then
for any real α. In particular, the equality will hold if α is defined as
Note that α > 0, and for every j between 1 and k, In particular, λi − αμi = 0 by definition of α. Therefore, where every is nonnegative, their sum is one, and furthermore, . In other words, x is represented as a convex combination of at most k-1 points of P. This process can be repeated until x is represented as a convex combination of at most d + 1 points in P.