In this video, I'll talk about some concepts such as convex combinations, convex sets,
convex functions, and concave functions.
Given two points x and y in n dimensional space.
A convex combination of these two points is defined as any point z that can be written
in this form z=λx+(1-λ)y, λ is between 0 and 1.
Graphically, the convex combination z is a point on the line section between x and y.
For example, if λ = 0.3, it means z is a combination of 30% of x and 70% of y.
A set S in n dimensional space is called a convex set if it contains all convex combinations
of any two points within it.
Graphically: A set of points S is a convex set if the line segment joining any two points
in S is wholly contained in S. Let's see some examples.
This set is a triangle.
Let's pick two points in the set S and connect them.
You will see that no matter how you pick these two points, the line segment is wholly contained
in S. So it is a convex set.
This set is a diamond.
Let's pick two points in the set S and connect them.
Similarly, the line segment is wholly contained in S. So it is a convex set.
This set is a semicircle.
Let's pick two points in the set S and connect them.
The line segment is wholly contained in S. So it is a convex set as well.
This set is a hollow circle.
Let's pick two points in the set S and connect them.
The line segment is not wholly contained in S. So it is not a convex set.
This set is a cross.
Let's pick two points in the set S and connect them.
The line segment is not wholly contained in S. So it is not a convex set.
This set is a partial circle.
Let's pick two points in the set S and connect them.
The line segment is not wholly contained in S. So it is not a convex set, either.
We have two special cases of convex sets.
An empty set is a convex set and a single-point set is also a convex set.
Now let's answer this question: Is the intersection of two convex sets convex?
The answer is yes.
Let's see two examples.
This is S1, and this is S2.
They are both convex sets.
Their intersection is S2, which is still convex.
Another example, this is S1, and this is S2.
They are both convex sets.
Their intersection is the shaded area, which is still convex.
Let me briefly explain the reason behind this.
If the intersection is empty, or consists of a single point, it is a convex set by definition.
Otherwise, take any two points A and B in the intersection.
The line segment AB joining these points must also lie wholly within their intersection.
Therefore, the intersection is a convex set.
It turns out, the intersection of any number of convex sets is also convex.
Now answer this question: Is the union of two convex sets convex?
Let's see two examples.
This is S1, and this is S2.
They are both convex sets.
Their union is S1, which is still convex.
It seems the answer is true.
But let's see another example.
This is S1, and this is S2.
They are both convex sets.
Their union is the shaded area, which is not convex.
This is a counterexample.
So, the answer to this question is no.
Let S be a convex set.
The function f(x) is a convex function if for any two points x1, x2 in S, this relation
holds: the function of the convex combination of these two points is less than or equal
to the convex combination of their function values.
Graphically, f(x) is convex if its value is below the interpolation formed between any
two points.
In this figure, we have two points, x1 and x2.
Their f values are f(x1) and f(x2).
The function of the convex combination is marked in red, and the convex combination
of their function values are marked in blue.
The blue line is the interpolation and the red curve is blow the interpolation.
So it is convex.
If the function of the convex combination of these two points is greater than or equal
to the convex combination of their function values, then the function is concave.
Graphically, f(x) is concave if its value is above the interpolation formed between
any two points.
The function of the convex combination is marked in red, and the convex combination
of their function values are marked in blue.
The blue line is the interpolation and the red curve is above the interpolation.
So it is concave.
Let's see some more examples.
Is this function convex or concave?
It's convex because its value is below the interpolation.
Is this function convex or concave?
It's concave because its value is above the interpolation.
What about this function?
It is convex in one section and concave in another section.
But overall it is neither convex nor concave if we consider the entire curve.
What about the last one?
The interpolation is overlapping with the function itself.
So, it is both convex and concave.
As a general rule, a function is convex if it entirely opens upward.
A function is concave if it entirely opens downward.
Also, if a function is convex in S, its opposite is concave in S.
Okay, I just introduced convex combinations, convex sets, convex functions, and concave
functions.
Thanks for watching.