Posts /

Convex Optimization Part 1

Twitter Facebook
31 Aug 2017

[TOC]

Terminologies

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

By definition, norm is calculated as follows:

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,

NOTE

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

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 r \leq d. 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, \lambda_i-\alpha\mu_i=0. 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.

Weierstrass Theorem


Twitter Facebook