[TOC]

## Terminologies

• 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.

## Norm

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

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

## Convex Set

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).

## Affine Set

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.

### Theorem

If C is an affine set and x0∈C, then the set V=C−x0={x−x0:x∈C} is a subspace of C.

## Convex Hull

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.

### Remark

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.

### Theorem

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.

## Caratheodory Theorem

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.

### Example

 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.

### Proof

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.