convex set

To discuss about the convexity of set first we discuss about line segment. What is Line Segment? Let any two points $x$ and $y$ in $\mathbb{R}^n$ . The set $\{u : u=\lambda x+(1-\lambda)y$ , $0 \le \lambda \le 1\}$ is called the line segment joining the points $x$ and $y$ . The points $x$ and $y$ are called end points of this segment and for each $\lambda$ , where $0 \le \lambda \le 1$ the points $\lambda x+(1-\lambda)y$ is called an in-between points or internal points of the segment. The line segment joining the points $x$ and $y$ will be denoted by $[x:y]$ . The open line segment denoted by $(x:y)=\{u : u=\lambda x+(1-\lambda)y$ , $0 < \lambda < 1\}$ . Therefore $[x:y]=\{u : u=\lambda x+(1-\lambda)y$ , $0 \le \lambda \le 1\}$ is called the closed line segment.

Now we discuss about convex combination. Convex combination is nothing but a universal definition of line segment. The convex combination of a set of $k$ points $x_1,x_2,\dots \dots x_k$ in a space $E^n$ is also a point $x$ in the same space given by $x=\lambda_1x_1+\lambda_2x_2+\dots\dots +\lambda_k x_k$ where $\lambda_i$ is real scalars and $\ge 0$ for all $i$ and $\sum_{i=1}^{k} \lambda_i=1$ . Always remember that convex combination is also a point.

Convex Set : A point set is said to be a convex set if the convex combination of any two points of the set is in the set. In other words if all points of the line segment joining any two points of the set is in the set then the set is known as convex set. A subset $S \subset \mathbb{R}^n$ is said to be convex set if for each pair of points $x,y$ in $S$ the line segment $[x:y]$ is contained $S$ . In symbols a subset $S \subset \mathbb{R}^n$ is convex set iff (if and only if) $x,y \in S \Rightarrow [x:y] \subset S$ . Hyperplane, hyper sphere, convex hull , half space etc are examples of convex set.

Hyperplane: A hyperplane in $E^n$ is a set $X$ of points given by $X=\{x : cx=k\}$ where $c$ is a row vector given by $c=(c_1,c_2,\dots, c_n)$ and not all $c_j=0$ and $x=(x_1,x_2,\dots x_n)$ is an n component column vector. A hyperplane can be defined as a set of points which will satisfy $c_1 x_1+c_2 x_2+\dots +c_n x_n = k$ . A hyperplane in two dimension is a line and in the three dimension is a plane.

Convex Function : Let $f$ be a function : $I \rightarrow \mathbb{R}$

$f$ is said to be convex if $f(\lambda a+(1-\lambda)b) \le \lambda f(a)+(1-\lambda)f(b)$ for all $a,b \in I$ and all $\lambda \in \mathbb{R}$ with $0 < \lambda <1$ .
$f$ is said to be strictly convex if it is convex and the strict inequality holds in above mentioned equation $\tag((1)$ whenever $a \neq b$ .

We may give some other equivalent, formulations of the convexity of function $f : I \rightarrow \mathbb{R}$

$f(x) \le \frac{b-x}{b-a} f(a) + \frac{x-a}{b-a} f(b)$ for all $a,b,x \in I$ with $a<x<b$ . Note that the right hand side of this enequality can be writen as $f(a) + \frac{f(b)-f(a)}{b-a} (x-a)$ .
$f(\lambda a + \mu b) \le \lambda f(a) + \mu f(b)$ . For all $a,b \in I$ and all $\lambda, \mu \in \mathbb{R}$ such that $\lambda > 0$ , $\mu > 0$ , $\lambda + \mu = 1$ .

THEOREM : Let $f : I \rightarrow \mathbb{R}$ be convex. Then $\frac{f(x)-f(a)}{x-a} \le \frac{f(b)-f(a)}{b-a} \le \frac{f(b)-f(x)}{b-x}$ . Whenever $a,b,x \in I$ , $a<x<b$ .

Proof : Since $f$ is convex, we have $f(x) \le \frac{b-x}{b-a} f(a) + \frac{x-a}{b-a} f(b)$ . From this inequality we can derive $f(x)-f(a) \le \frac{b-x}{b-a} f(a) + \frac{x-a}{b-a} f(b) - f(a) \Rightarrow f(x)-f(a) \le \frac{(x-a)(f(b)-f(a))}{b-a}$ . Therefore $\frac{f(x)-f(a)}{x-a} \le \frac{f(b)-f(a)}{b-a}$ which proves the first inequality of the theorem. The second inequality can be proved in a similar way.

Comments

Leave a Reply Cancel reply