Convex Sets in Linear Programming
nasirenesh@gmail.com
Lecture 4
N – Dimensional Space
All definitions displayed here exist within an n-dimensional space, where n is an integer > or = to 2 (greater than or equal to 2).
What is a convex set?
A convex set means that between the two points in a Set, once a line joins them both, all other points on the line between are physically, completely lying within the set.
Definitions of a Convex Set: Featuring:
- R^n
- with n – dimensional space in n – dimensional sets,
- where n is an integer
- greater than or equal to 2 e.g. 3*3 = 3^2 : 2 dimensional square)
- n-dimensional space uses capital letter notations for those points belonging to the very set…
- A set S (within R^n)
- All X, Y in S
- lambda X + (1-lambda)Y also exists in S,
- where 0<=lambda<=1 (ie. a fraction)
$$\text{ A set S residing in } R^n \text{ is said to be convex if for all X, Y in S, we have } \lambda X + (1-\lambda)Y \text{ also in S, with} 0 \le \lambda \le 1 $$
Again, its convex when the line joining two points within the set , lies completely within the set…
First example discussed that I need to understand:
Confirm convexity:
$$ S1=[X such \text{ } that |X| \le 1]$$
S1 = {X such that |X|<=1 } whatever the X value is…
NB to self;
- the theorem uses capital Xs
- all this is really is the multiplication of fractions, ie. numbers that are under the value of 1
- eg. a half of the number 1/2 is the same as 1/2 * 1/2 = 1/4
Proof:
$$\text{Let} X_1, X_2 \epsilon S_1$$
$$\text{Then} |X_1| \le 1, |X_2| \le 1 \text{ where } 0 \le \lambda \le 1$$
$$\text{So that, }| \lambda X_1 +(1- \lambda X_2 | \le | \lambda X_1 | + | (1- \lambda ) X_2 | $$
$$ = \lambda| X_1 | +( 1 – \lambda ) | X_2| $$
$$ \le 1 $$
$$ \lambda X_1 + (1- \lambda ) X_2 \epsilon S_1 $$
$$ S_1 \text { is therefore a convex set }$$
2nd example discussed that I need to understand:
Check convexity
$$ S_2=[X s.t. |X|=1] where X \epsilon R^n $$
Proof:
$$ Let X_1, X_2 \text{ be in } S_2, s.t. X_1 \ne X_2, |X1|=|X_2|=1 $$
$$ Now | \lambda X_1 + (1-\lambda) X_2 | \le \lambda |X_1| + (1-\lambda)|X_2|, 0 \le \lambda \le 1, $$
$$ \text{with equality possible if and only if either} $$
$$\text{1. } X_1=0$$
$$ \text{2. } X_2 = 0 $$
$$ \text{3. } \lambda X_1 = \mu (1-\lambda) X_2, \mu >0 $$
Method to show by contradiction that the line joining the 2 points does not belong to the set…
Theorem 1:
Theorem 2:
Action Required – do these again…
Theorem 3:
Theorem 4:
Theorem 5:
Theorem
