[TOC]

- The space ℝn − It is an n-dimensional vector with real numbers, defined as follows − ℝn={(x1,x2,…,xn)τ:x1,x2,….,xn∈ℝ}
- The space ℝmXn − It is a set of all real values matrices of order mXn.

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‖≥0
- ‖x‖=0⇔x=0∀x∈X
‖αx‖= α ‖x‖∀x∈Xandαisascalar - ‖x+y‖≤‖x‖+‖y‖∀x,y∈X
- ‖x−y‖≥‖‖x‖−‖y‖‖

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,

- ⟨x,x⟩≥0,∀x∈X⟨x,x⟩≥0,∀x∈X
- ⟨x,x⟩=0⇔x=0,∀x∈X⟨x,x⟩=0⇔x=0,∀x∈X
- ⟨αx,y⟩=α⟨x,y⟩,∀α∈κand∀x,y∈X⟨αx,y⟩=α⟨x,y⟩,∀α∈κand∀x,y∈X
- ⟨x+y,z⟩=⟨x,z⟩+⟨y,z⟩,∀x,y,z∈X⟨x+y,z⟩=⟨x,z⟩+⟨y,z⟩,∀x,y,z∈X
- ⟨y,x⎯⎯⎯⎯⎯⎯⎯⎯⟩=(x,y),∀x,y∈X

**NOTE**

- Relationship between norm and inner product: ‖x‖=√(x,x)
- ∀x,y∈Rn,⟨x,y⟩=x1y1+x2y2+…+xnyn

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**

**S**is an affine set if and only if it contains every affine combination of its points.- Empty and singleton sets are both affine and convex set. For example, solution of a linear equation is an affine set.

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, *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.

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 **x**j is in *P*, every *λ*j is strictly positive, and

Suppose *k* > *d* + 1 (otherwise, there is nothing to prove). Then, the points **x**2 − **x**1, …, **x**k − **x**1 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*.