Good morning and good afternoon,
I am Esteve Codina and I'm going to present this video
9T, convex sets and functions within the block three calculus.
We will see the following contents.
We will go first in the learning objectives,
and next will have an introductory example
in that we will see sets in
'n' dimensions defined by linear equality and inequalities.
We will go next, to set the idea or concept of convex sets,
next convex function on convex sets.
And finally, we will see why this case is important
and finally we will end the contents with references and extensions.
Okay.
The learning objectives of this video are to know what are the convex sets
to know that sets defined by linear equality and inequalities are convex,
and we will use some examples to illustrate this.
We will see the notion of what is a convex
multivariate function and to know some simple and useful examples.
And finally, we will see
why a constraint optimization problem in the convex case is so important.
Okay,
Let's see here an example. We have
two cities A and B, and from city A to City B,
we have 6000 trips/hour. Our cities A and B are joined by
two highways.
And we want to know a set of all the possible feasible flows
that on the two highways 'v1', and 'v2' go from A to B, Okay.
So in this case, we see we see that the flows on the first highway
and on the second highway must summ up to 6000.
Next, we want to refer only to non-negative flows.
So if 'v1' must be non-negative and 'v2' must be non-negative
and 'v1' should be constrained to be smaller equal than 4000.
'v2' should be smaller or equal than 5000.
Yeah.
So, mathematically we we have to present this as the set F,
by means of this equality and four inequalities.
Okay, so let's see
in this case how you set looks like in
in the R2 Euclidean space.
Initially, let's consider the flows which are non-negative which are
in the negative orthant of R2, that sum up to 6000.
Yeah. So, we will see that these flows lie within
this segment, the blue segment, that appears on the screen.
Yap. Next, we will add
the constraint that 'v1' should be no larger than 4000.
So, we have to exclude from the segment those points with coordinate 'v1'
larger than 4000, and next, that
finally with the constraint on 'v2' to be smaller equal than 5000.
So we simply had
the constraint.
And this would imply that the other extreme of the segment
is eliminated leaving us with this small segment
in the non-negative orthant.
Okay. So let's see another example.
A second example. Consider points in R2 with coordinates 's', 'm'
verifying simultaneously the following set of inequalities.
Inequality 'R1', 'R2', 'R3' plus the non-negative inequalities
for each of the coordinates.
Okay, so let's see. to see in and
explain how the previous inequalities form a set,
let's consider first only the first inequality.
The inequality of '2s' + 'm' <=100.
We can see that the points verifying
this inequality are those represented
and the upper left side
of the screen, on which appear in blue.
Yeah.
Next, we will see what happens if we add a second requirement 'R2'.
If we add the second constraints, or second requirement,
then from the
the previous set
we have to exclude some points,
and if we add a third requirement, again we have to include some points.
So point verifying simultaneously 'R1' 'R2', and 'R3'
are those who appear on this blue region of the
two dimensional space R2.
Finally, we would make the requirement of being coordinates non-negative,
and then we obtain finally the feasible set which appears here in yellow. Yep.
So, always we have linear inequalities
we will have a set that we can be considered a polyhedron.
We will refer to it as a polyhedron, and in general
the set of inequalities and equalities will form
the so-called, feasible region.
Yeah.
Okay, so let's go into the idea of convex sets.
We consider a subset within the n-dimensional space Rn,
and the idea is:
if we pick up two arbitrary points 'x super 1' and 'x super 2'
in the set C, then we form a segment
with extremes 'x super 1' and 'x super 2'. This is equivalent to pick up all possible
scalars within 0 and 1, and form a point x,
which is alpha 'x super 1' + 1-alpha 'x super 2'.
Then, if after making this operation for any arbitrary two points,
'x super 1' and 'x super 2' and a point within the segment
defined by 'x super 1' and 'x super 2'.
If the point so defined within the segment lies in C, then the set C is convex.
For instance, we can see on the bottom left of the slide
a convex set, we have simply defined by a linear inequality.
And every time we pick up two points
'x super 1' and 'x super 2' to form a segment,
the segment is entirely contained in the set.
Yeah, the same happens with the set
in the middle, which is defined by these two inequalities.
Notice that the first inequality is not linear, the second is linear.
But again, picking up two arbitrary points 'x super 1' and 'x super 2',
and forming a segment
the segment must be entirely contained in the set.
So this set is convex.
Instead, in this case it's easy to pick up for third example
two points and see that the segment here
defined by these two points in this case, but particular case
is not entirely contained within the set C.
So, this set is not convex.
Yeah. Okay.
So again, another important
example of convex sets are polyhedron
sets defined by equalities and inequalities.
In this case we see that again picking up two arbitrary points
'x super 1' and 'x super 2' the segment formed by the these two arbitrary points
lies entirely within the set C. So, polyhedrons
are convex sets.
Okay, some convex sets
have special points
which are of importance.
These are vertices, right?
So, a vertex is a point that cannot be contained
within a segment, which has both extremes of the segment,
entirely contained in the set C. For instance considered point A here
the green point A which and two segments
that contain point A,
so one of the extremes of the segment of each of these segments
must be at least outside of the set C. when this happens
then the point in particular is is referred to as vertex.
Instead, point B is not a vertex
because we can form a segment
that is entirely contained in the in the set C and both extremes
forming the segment are also in set C. So B is not a vertex.
Okay.
So let's go now to the the idea of convex function on convex sets.
So consider a function with n variables.
defined on a convex set.
So we will say that the function f is convex.
If for any two arbitrary points lying on the set C
and forming a segment
defined by the arbitrary points 'x super 1', 'x super 2' in the segment,
When evaluated the function on it, we have that it yields a smaller value
than the values that would be obtained on the secant made
by the values of the function on 'x super 1', 'x super 2'.
For instance, consider this function of two arguments
f of 'x1' and 'x2', 5 x1^2 + 10 x2
and then we pick up two arbitrary points,
'x super 1', 'x super 2'. 'x super 1' = (1,-7), 'x super 2'=(7,-7),
and then we evaluate the function F on them
yielding mean -65.
And the first case, and 175 in the second case.
And then we choose an arbitrary point on the segment defined by
'x super 1', 'x super 2', which is the point (3,-7).
So notice that this point, (3,-7), which corresponds
to 2/3 'x super 1' + 1/3 'x super 2',
so it corresponds to an alpha = 2/3.
Well, when evaluating the function on point x=(3,-7), it
yields -35, which is a smaller than the secant obtained by combining the
the values of the function on points 'x super 1' and 'x super 2', which is 15.
Right.
So in this case we illustrate that ,
for 'x super 1', 'x super 2', at the point x.
the inequality is verified and this can be done no matter what
pair of points 'x super 1', 'x super 2' you choose.
So, this function is a convex function.
Okay,
here there are some elementary or basic properties of convex functions.
Consider two convex functions defined in a common convex set,
'f1' and 'f2'. Then
if we make the summation and consider the function
'f1' + 'f2', then the summation 'f',
is convex also on C.
The second property is that if we have a positive real number
and we have a convex function defined on a convex set, if we consider a second
function defined by the product of this scalar 'a' times the function 'f',
this function 'g' is also convex on C.
we see here some examples of convex functions.
First, some elementary univariate functions.
The first one is the the linear function, where 'a' is a parameter
and the second case is a potential function, where 'b' is
an exponent, larger or equal than one.
And the set C are the non-negative numbers.
In the case of multivariate separable convex functions,
we can find the linear function which is made up by summing linear terms.
One for each component
of the vector of variables.
And the second is the
linear combination of potential functions, where the parameters
'a' are non-negative and the exponents should be larger than one.
Then we
we enter into consider why are convex functions
defined on convex sets so important.
It happens that if 'f' is a convex function
defined on a convex set C, then if we have that
if 'x*' is a local minimum of 'f' on C, then 'x*' is also a global minimum.
So, for this point 'x*', the function 'f'
takes always values smaller equal
than when evaluated at any other point in the set c
So it happens that nowadays there are many procedures or algorithms
for finding local minima of functions on convex sets in any dimensions,
and also commercial computational codes, that the problem of finding local minima
of a function on a convex set can be considered well solved
and computationally viable, even for large dimensions and large problems,
but convex functions have the advantage that instead
of finding only a local minima, we find global minima.
In the case of 'f' being convex and C being a convex set is
is known as a convex optimization problem.
Okay.
So to end, we see that these references and in the two initial ones
are to illustrate the concepts we've seen in this video
and the second ones are for more
elaborate properties and concepts based on convex sets and functions.
Okay so thank you very much for your attention.
And that's all