Welcome back. So we're talking about

convexity and in particular convex sets

today. So convexity is a key concept in

optimization theory. If we have a convex

optimization problem then there are a

huge wealth of techniques to solve those

problems and they're much much much

easier to solve than non-convex

optimization problems. And so there are

two ingredients to a convex optimization

problem. There's the objective function

and then there is the set of constraints

that determines a feasible set where the

optimum solution has to live. And so

today we're going to talk about what

makes a set convex or non-convex. So

here are two examples of convex sets um

a little hexagon and an oval. And we're

going to illustrate what is we're going

to define what it is to be a convex set

and then give a bunch of examples and

properties.

So the definition of a convex set is the

following. A set C like this hexagon or

this oval is convex if for every two

points inside of this set for every x

and y point uh pair of points inside of

this set the line segment connecting

those two points is also in the set. If

that's true for every pair of points, if

every pair of points has a line segment

connecting them that is also in the set,

then we would say that that set C is

convex. If that's not true, then the set

is not convex. Okay? So here uh I'm

going to illustrate it on this oval

example. So we have our set uh our set

here and we have these two points X and

Y. They're just arbitrary points. And

you can parameterize the line segment

between those points, this orange line

segment with this alpha parameter. So

when alpha is zero, we are entirely at

the point y. And when alpha is one, we

are entirely at the point x. And for an

alpha between 0 and one, I slide along

this line segment. So for every single

alpha between 0 and one, for every point

on this line segment, that point has to

be in this set in this purple region for

the set to be convex. And that has to be

true for every single pair of points I

could pick in this set. For every pair

of points I can pick, uh, in this case,

including on the boundaries, the line

segment connecting them has to be in the

set. So that's clearly true for this

oval. You can kind of verify that just

intuitively in your mind. It's also true

for this hexagon. Any two points, the

line segment connecting them is also in

the

set. This is an example of a non-convex

set because there is this uh we call

this here a concavity, this little bump

that's taken out. And if I take two

points uh x and y that are kind of

around that concavity, the line segment

connecting them, there are points that

are not inside the set. These points

here are not in the set. And that means

that that set is not convex. It's a not

it's not a convex set. Okay. So really

really important definition and actually

really simple and easy to understand.

This is kind of all there is to convex

set theory. A set is convex if and only

if for every two points in that set, the

line segment connecting those points is

also in the set. Okay? And this idea

generalizes to much higher dimensional

spaces and much kind of weirder shapes

and geometries. Okay, so this is a a

really simple definition, but this will

encapsulate a huge array of

shapes. Good. So let's look at another

example. If I have this uh this this

circular disc and the interior of that

disc is also part of the set. So this is

a shaded disc. This is a hollow circle.

The shaded disc is a convex set because

any two points the line segment

connecting them is in that shaded disc.

Whereas the ring the hollow circle or

the hollow ring is not convex because if

I take two points on the boundary the

line segment connecting them is interior

and the interior is not in the set. So

all of these dashed orange points are

not in this hollow ring set. So the

filled disc is convex but the hollow

ring is

non-convex. Um polyhedra in higher

dimensions in three dimensions, four

dimensions, n dimensions are generally

uh convex if they have this kind of this

this property. Um, but if they have

weird boundaries where some of the

boundaries are included and some of them

are not included, you might have them be

uh kind of degenerately non-convex

because if I took a point uh at this

corner and a point at this corner, there

would be points along the line

connecting them that are not in the set.

So, I've drawn this as kind of a dashed

boundary here. But usually if you do

common sense things like include the

boundaries uh or disregard all of the

boundaries then your set will be convex.

And there's a lot of pretty hairy deep

mathematical theory in set theory and

topology uh related to convex set

theory. I'm going to gloss over most of

that and just give you the intuitive

kind of common sense notions of these

things and maybe later I'll have some

more kind of deep dive math lectures on

convexity. Good. So these are some

examples. Um other good examples are a

point is convex. Um kind of trivially

convex. Uh a line segment or an infinite

line those are both convex. A section of

a plane or an entire plane or a half

plane those are also convex. Uh and

these generalize to higher and higher

dimensions. So for example a you know a

positive quadrant of a three-dimensional

space that would be convex or the entire

three space is also convex or the

positive half space where x is greater

than or equal to zero that would be

convex. So these are all building

blocks. And what we're going to see very

soon is that I can get kind of more

exotic shapes by taking the

intersections of these and I can build

these little convex sets out of these

building block pieces. So other useful

uh convex sets that are going to come up

a lot are things like spheres,

ellipsoids, and cones. And as long as

the cross-section of this cone is

convex, then if I extrude it out either

in a cylinder or a cone, that will also

be a convex set. Okay, so these are

really, really useful. And we're going

to see these all the time in

optimization theory. And remember, a lot

of our optimization problems are going

to be very highdimensional. we're going

to be trying to train a neural network

with a million parameters or doing a le

squares problem where we're fitting you

know a hundred or a thousand unknown

variables. So our notion of a convex set

is going to be in a very highdimensional

space. So we need to be able to take

these building blocks these these kind

of concepts and abstract them. An nphere

is convex. An n-dimensional ellipoid is

convex. An n- dimensional hyper plane is

also convex. Things like

that. Good. Uh so this is the notion of

kind of convex and

non-convex. One kind of other point is

if you had a non-convex shape like this

kidney beam, there's something called

the convex hole. H u ll. This is like

the hole of a ship, the the kind of body

frame of the of a of a vessel, a naval

vessel. And you would get this convex

hole by taking the smallest set that is

convex that contains that non-convex

kidney bean. And in this case, it's

really kind of intuitive how to do this.

You just kind of take those two uh edge

points and connect them and fill it in.

Um you basically fill in this concavity

here and you get a convex set called the

convex hole. So you can take non

non-convex sets and convexify them by

adding in the points that are missing

essentially. Good. Okay. So that's the

notion of convexity. Um I want to show

you how you can take inequality

constraints which are going to come up

all over the place in optimization

theory and build convex sets using these

inequality constraints. So um if I have

something like the inequality constraint

that my x variable has to be greater

than or equal to zero that sets up a

feasible region in my optimization

problem that is the right half plane

where x is greater than or equal to

zero. It also establishes what's known

as an infeasible region. The complement

of that is the set x less than zero.

Notice that if this is x is greater than

or equal to then this is x strictly less

than. The boundary has to you know be

either feasible or not feasible. It

can't be both. Okay. And so this

feasible region in this case is a convex

set. The infeasible region is also a

convex set. So this inequality

constraint in my optimization problem

establishes a feasible region that is

convex. And so that means that all of my

powerful convex optimization techniques

are going to apply when I have simple

equality and inequality

constraints. Now I can have more complex

constraints like um the radius of my x

and y point has to be less than or equal

to one and that would also establish a

convex feasible region this unit circle

here. And it would establish a nonconvex

infeasible region which is everything

outside of that circle. So what I'm

trying to get at here is that you know

in our optimization problem our

constraints are generally going to be

written as either linear or nonlinear

inequality constraints and those are

going to establish feasible regions

which may or may not be convex. I could

easily write down an equation where the

feasible region is weird and

nonconvex. Uh but in these cases our

feasible region is in fact convex. So

that's kind of where we, you know,

inequality constraints often give you

convex sets. Linear inequalities will

always give you convex sets. Nonlinear

inequality equations may or may not give

you convex sets. Good. And the

intersection of two convex sets is also

convex. This is always true. Um, I'm

going to prove this in another video.

It's actually a really simple proof, so

I'm just going to like do it because

it's good for you to see it. If I have

two sets C1 and C2, the intersection

this C1 and that should be a C2. C1 and

C2 uh is this intersection of the two

sets. We call it C. And that means that

any point in this middle region has to

belong to both C1 and to C2 to be in

this intersection. And you can prove

pretty easily that if C1 is convex and

if C2 is convex then this kind of

intersection region in the middle has to

be convex. It has that property that

every line segment connecting any two

points lies entirely in that set. Okay.

And if this is true for two sets it's

true for three or for four or for n. I

can take the intersection of as many

sets as I want and I still if they're

convex the resulting set is still

convex. So this is huge. This is how

we're going to build convex feasible

regions with our constraint equations in

optimization. So for example, if I have

this matrix system of inequality

constraints, a bunch of inequality

constraints that can determine a convex

feasible set C uh like this kind of

quadrilateral here. So for example, I

might have two um inequality constraints

that y has to be greater than or equal

to zero and x has to be greater than or

equal to zero. Those are these kind of

very lightly shaded purple half planes.

Those are convex. And so their

intersection, the positive quadrant up

here is also

convex. And then I might add two more

constraints that y has to be less than

or equal to 2/3 and x + y has to be less

than or equal to 1. Again, the

intersection of these four constraint

equations, these four convex sets gives

me this feasible convex set here in the

middle. And this is where my optimum

value, my the solution of my

optimization problem has to live in this

convex feasible set given by these

inequality constraints. So super super

useful. The property that the

intersection of two convex sets is also

convex is what allows us to build these

convex feasible regions in optimization

problems. Super powerful, really

fundamental. And I'm going to show you a

proof of this in a future

video. Good. Um, and this again, like I

said, this establishes the feasible sets

that we're going to use for every linear

programming problem and for every

quadratic programming problem. the

constraints are going to be of this form

and so we're going to get these convex

feasible sets. So that's that's one of

the nice things about linear programming

and quadratic programming is that

they're convex optimization problems

that have really uh good generic

solution

techniques. Okay, so that's kind of all

I wanted to tell you at the beginning

with convex sets. Um, it's really just

defined by this simple definition that a

set is convex if for every two points X

and Y in the set, the line segment

connecting those two points is also in

the set. So these are examples of convex

sets. This set is nonconvex because it

does not satisfy that property. And this

is one of the most useful uh ideas in

set theory and in

optimization. So soon we're going to

talk about what it means to make a

function convex. So we can have convex

sets and also convex optim uh objective

functions. And so we'll talk about what

it means for a function to be convex

soon. All right. Thank you.