Lecture 12

IIT Kanpur July 201
20 followers
Mar 1, 2024
[Music]
[Music]
so let's study a fine
sets
so this I already
answered a set is a
fine
if
contains
okay so your set is a fine if you pick
any two points in that set and the line
containing it or the a fine combination
of those two points are still in the set
itself that is the a fine set
and it's not uh hard to argue using
induction that this definition can be
changed to a set is a
fine
if all
possible a fine combinations
of points in
s r in s so there is no good reason to
restrict taking a fine combination just
any two points you can take any any
number of points in s take their a fine
combination and things won't change yes
it is not obvious but you can make it
work sorry this is the
definition pick your
favorite
okay uh countably F
idea we are in reals so those things are
fine uh those things are a problem if
you take integers and things like that
but in a real space these these things
don't
matter good
yes good that is the next question that
is what we are going to solve right but
once again the question soam has in his
mind
is what does the fine space look like
seems like a difficult question so what
do we
do
examples good and we have taken already
one example if I take two
points there a fine
combination is a
line
right what if I take three
points it's a
line okay so that's a good
generalization but did you really
understand how you prove it so
okay so assertion is and I guess that's
because you believe in the beauty of
mathematics so you say yeah if it is a
line let's say plane through the three
points but then as the ugly part of
mathematics we need to prove
it very good
right this is what we want to study
where alpha 1+ alpha 2 plus Alpha 3
equal to
1 right this is the set we want to
study
and as Dave has planned it has actually
a very nice representation where I can I
can say this
is Alpha 1 * X1 - X3 + Alpha 2
* X2 - X3 Plus
plus is this
correct oh just X3
sorry okay sounds good and the important
Point here
is Alpha 1 and Alpha 2
are
and now you have gotten your
answer what is
this this is the
plane span
by by X1 - X3 and X2 - X3 this we
already know right this is just a plain
linear combination of X1 - X3 and X2 -
X3 because Alpha and Alpha 2 are
unrestricted this we already know and
now the structure of this is very simple
you take X3 and put
the plane through it plane on top of it
so it is a plane with a with an
offset
okay
and not
surprisingly you can do this
trick with any aine
set right
uh uh you
uh X is some point in R to the
n
and V belongs to somebody Vector space
okay so this is for all
X and for all Vector spaces so you fix
an X you fix a vector space you define
your Subspace like this sorry I should
not say
this and you can easily
prove that this is an aine set so a
translation of a of a of a plane or a
sorry I should say a linear Subspace is
an a fine
Subspace a translation
ofs
and since I can do this trick for any
number of points it is going to turn out
that
even reverse is
true so what is an aine
set it is
offet plus a vector space
okay and in my favorite two
Dimensions it looks like
this this is my
offset and then if I translate this line
to here that is going to be my Vector
space remember this is not a vector
space if I pass it through the through
zero then it is a vector
space right that you can easily easily
see that if look at all points you
know Alpha V this is a vector space but
if I move that line that doesn't remain
a vector space right but all yourin sets
look like
this and now if you look at this
definition these two things seem
important it turns out actually not the
offset is not really important the
vector space always Remains the Same you
can actually choose this Offset you can
choose this Offset you can actually
choose any point in the uh aine set as
the offset and this is true I could have
played the same trick with
X1 right I could have played the same
trick with X2 so even though it looks
like it is offset plus a vector space
it's any offset in the fine
set adding the vector space and that's
because of the linear combination
structure sounds good do we have a good
understanding of what an aine set is
now because before you go to convex sets
you understand a fine sets no and we
have to understand convex sets
because linear programming requires
convex
sets the feasible gen is going to be a
convex
set
so now this is one kind of
a for the lack of the better term
Duality here in the sense there are two
descriptions of a a fine set right one
description
is
sorry
right no but that and this yeah that is
true uh that's kind of a way to define
it but I don't think we ever use it
that's not very useful definition to use
so one is
this offset
plus Vector space and the other is you
know how do you describe a line you
write a equation for it for a fine set
it is going to
be uh what we call a hyperplane
which
is okay so again this this both Natures
I can write it as an equation I can
write it as a geometric object now this
is in a fine set is not hard to
prove
other way is also not
high right because what is this saying
this is
saying that every X which has a
constant inner product with
a
correct right they is saying that my
inner product with B is constant now
again this would have been easy what is
this this is the things which are
perpendicular to
a right this now let's say x0 is a point
in this then this is
x0 so let's say this was the
case you have an x0 an offset a
transpose x0 will give you B you can add
any V to it such that a transpose V
equal to B right so this is the vector
space which is perpendicular to a
moved in some direction and again the
same thing the vector space Remains the
Same you can't change the vector that's
the important part it is the
perpendicular Vector space to a
x0 pick any point such that a transpose
x equal to
B right so in multiple ways we see the
same thing but this is the important
trick this is the trick which will play
again and again for almost all the
geometric things we will have a
geometric picture and an equation
picture sounds
good now we move move to convex sets I
should talk about conic sets also but
that's not very important I will talk
about cones later they are slightly
difficult you have to be very careful
while you define conic sets or cones
that we will do later today we
understand convex sets any questions
about a fine
sets good okay
great what is the
definition a set is
convex if it
[Applause]
contains the line
segment
okay natural the way we did the fine
right and no price for
guessing theorem yeah you can take
convex combination of multiple points
also
I won't go through it because that's
basically an exercise in
induction but once we Define this
another important thing is what we
call
convex Okay
so given a set
s convex Hull of s this is the
notation is the
set of all convex
combinations of
this okay so what is the convex h of two
points
line
segment that's okay right this we have
seen multiple times that's the simplest
case but in general I can have multiple
points and if I take convex combination
of
everything uh everything in that set s
that's called the convex of
s right and also now what can
happen suppose with these three points I
take a convex combination I get a point
here
with these three points I get a convex
combination this is here now I can
possibly take convex combination of
these two points
again what do you
think is this a convex combination of
these four points yes it is do I do you
do I need to prove that you can all do
it right you have two set of
coefficients each of them you kind of
multiply by let's say half and half or
1X 3 2x3 still they will remain positive
they will sum up to one what does this
prove convex H is
convex too too many convex
things but yeah convex H is
convex right even though I just took the
convex combination of s these are going
to be
vertices but this is fine
and this might again look complicated
but you have seen these things like
ainet turned out to be
just Vector space and offset similarly
convex H see uh generally a convex sh
shape could be very very complicated
very hard to describe a circle is
a convex set because you take two points
inside the circle the line segment stays
inside
right this is convex or at least the
shape I intended to draw was convex
right
convex no oh
sorry
the yeah right and to be able to
describe it in you know every possible
way this is going to
be it is convex in my eyes Okay so uh
but it is very hard to describe it uh if
you want to describe it by equations we
will take the simpler task we will talk
about convex Hull of finite many points
and that is going to be reasonable
enough okay
so
now I have three points how will the
convex C look
like
why okay start this line has to be
there this line has to be
there this line has to be there is it
convex yet no I can take these
points
ENT
good I was hoping that you asked this
question because then I can tell my next
[Music]
theorem convex
H is the
smallest
Set
uh
yes or uh I should say do I want to
write it as uh intersection yeah uh is
this is the
smallest
or if you want to think about it take
all possible sets which are convex and
contain s take their
intersection that is going to be convex
so let me write
it
all these are equivalent
definitions okay so this is a valid
point what is the guarantee that I
haven't left out anything this is a
convex
set this contains three
points that is the that is enough so
that means I just need to prove this
theor
take take two minutes and prove this
it's not
hard it's like a two line
proof it basically says that you are not
confused between all these convex convex
convex
convex
sorry that's the next thing I'm going to
talk about but again I'm not going to
talk about it because you will prove it
it's like the simplest
thing
uh right again if there are two points
if they are in both the sets their line
segment will be in both the sets it will
be in the intersection so
then right so every com so if it is S1
S2 S10 S1 will contain the line segment
S2 will contain the line segment s 10
will contain the line segment so the
intersection will contain the line
segment that's
all but we go there
later so think of any set which contains
s s right now it contains s it's a
convex set that mean it will
contain all the convex combinations of s
okay
so take
s oh sorry take T containing s take any
set which contains s
now if T is convex
it
contains all convex combinations of
s that means it
contains convex h of s that
means T is bigger than convex
ofice
simple okay again these definitions
might seem
uh out of line or slightly confusing but
this is something geometrically is very
very simple so just to make sure that
you align your geometric intuition with
these
definitions and if there are any
questions I would be happy to
answer or give them as
exercise right so we had aine sets aine
sets were Linear subspaces by an
offset right now we're talking about
convex
sets look like a triangle if I take four
it will look like
a mostly a quadrilateral sometimes a
triangle right
so if I take four
points great this is the convex set
right uh when I I mean all
this
if I take a point
inside Still Remains the
Same right and now what do you think
intuitively can you describe to
me what is convex of s if
this is a finite
set what what's again I don't want it to
be mathematically correct in your mind
what what is the picture for four it was
a
quadrilateral something which has kind
of a boundary lines right it might
happen that it the number of bound uh
the number of vertices number of extreme
points are not equal to S because some
of the points can get inside but in some
sense I look at all the points I look at
all the outer points and connect them by
straight lines that's called
a yeah
thank
you
polygon
or
poope okay so the difference
is
this is
bounded okay so what do I mean to
say
so actually for finite set of points
this will always be a
polygon okay that means it will be
bounded but we will be interested
sometimes in convex sets which are
slight extension of polygons right so
polygon
is
okay right polygon like this okay okay
but we might sometimes be interested in
convex
sets which
go the previous thing was bounded this
is unbounded right what is the
mathematical definition of a set being
bounded what do you think it should
be good so you have seen it before so
there's a big ball so there is a big
ball you can say from origin which
contains the entire set of finite radius
there's a sphere of finite radius which
contains my
set so in case my set was like
this there is a big ball so basically
you are not going to Infinity right so
so again simple intuition I have to give
a mathematical definition to all these
things bounded okay so polygon is
bounded polytop is unbounded but
something which whose boundaries are
these straight lines and a convex set
but again we will see these two
things
coincide and uh before I proceed further
uh and
Forum
objects intersection of two convex
sets convex similarly
Union of two convex
sets
not each of you draw an
example why can't you draw in your
paper I don't think that's a good enough
excuse everyone keep a pen and a paper
with you it helps in my in my class at
least please try these things I know you
are smart as I always say what is the
best thing about
ug's they give very give very quick
incorrect
answers right
so let's try to make them
correct and the simple thing is to think
before you are answering so everyone can
draw two convex sets such that their
Union is not
convex right
good simply put you take any two
disjoint convex sets their Union is not
going to
be
convex good
okay
sorry Union is
convex and intersection is also convex
so uh
good
sorry yes let complete
[Music]
[Music]
your
[Music]
