Lecture 29

IIT Kanpur July 201
20 followers
Mar 17, 2024
[Music]
[Music]
okay we see the proof first let's fix up
our notation okay so that uh we don't
get confused P and D we already know
let's say x
star and Y
star
are the Optimal
Solutions
for dual
respectively correct
okay and what we want to show is
that
if no technicalities is
happen right and you remember
technicalities is one is invasible both
are invasible and things like that so if
none of that strange weird things are
happening both are feasible then this is
the case Okay uh before I move forward I
wanted to just as an aside I want to
mention convex
programming uh what do I want to mention
about it notice that many of these
things which we are saying about linear
programming the niess comes because the
feasible set is a convex set right so
there are cases uh there is this bigger
branch which contains linear programming
and many other places where my feasible
set is convex and then I want to
optimize some nice function it could be
a quatic function it could be a linear
function it could be a convex function
so on and so forth but the idea is that
still some of the properties of linear
programming can still be used here and
people in optimization actually study
convex
programming I remember a case when I I
went to this optimization person told my
program he said oh it's not convex we
can't do anything
so that's generally the the feeling they
have convex good not convex not good for
optimization right so this is a major
field of study of which LP is a very
very small
subset there is another small subset
which kind
of comes in between which called
semi-definite programming and I will
cover that CU that's also used used a
lot in complexity Theory semi
programming and this this is where my
research started so kind of fund of it
so I will tell you about this whether
you like it or
not but uh yeah so LP sem def programs
convex programming and what you realize
is that this is the strongest that means
very few programs can be written like
this very few in the scheme of still a
lot but few compared to others though it
has strong properties As you move this
site the set
increases but then the properties
decrease Duality is one thing which
works out for convex
programming you can Define what we call
dual of convex
codes so instead
of this we can say x is part of some
convex cone and then the Dual will be
all the things which have positive inner
product with everything here right why
why why were we saying X should be
positive because X positive is the
elements which which will always give
you positive when multiplied by
something which is
positive okay similarly you can Define
this idea of dual codes and this entire
Duality Theory can be extended to convex
programming
but then strong Duality does not come
for
free weak Duality Duality Theory works
out strong Duality you have to be
careful here it is automatic here it is
almost automatic here you have to work
for
it okay so in the big scheme of things
it's nice to remember yes LP is
something we are studying but there are
there's a bigger class of problems so if
your problem is not LP not all hope hope
is lost probably it is Semite
programming then you are still very very
okay if it is convex programming you are
fine if it is not convex programming
change your
program do PhD on something else no I'm
just joking there are other techniques
too but this is the general
idea okay great so one of the nice
property of LP is that strong Duality
almost always holds and if you have this
convention of minus infinity and plus
infinity then it's kind of always there
right okay now we are ready for the
proof uh I will erase this you will
remember this actually let me just keep
it I think it's it's important
so
so let's take the first
case suppose p is
empty okay what does this
mean that we have to prove that's not
now we end up okay wait
proof right so we can't say that that
means this is infusible that is what we
want to prove right so now but from
beforehand before knowing the statement
of strong Duality if someone tells you
this what do we
know there is no X greater than equal to
Z such that ax is equal to B that
means I'm not looking for English
equivalence I'm looking for a
mathematical
equivalence you should be able to tell
me this I told you strong Duality is
relies on what you're going to
elementary
elementary before that there was an
elementary version of
Duality yes so what does it
mean b is not in the cone
of
vectors of
a ax is equal to b x greater than equal
to Z this is saying that b is not
present in the cone finite convex cone
generated by The Columns of a right so
then what does for Lama tell us there
has to be
a hyperplane
separation there exist a
y such
that what do I which sign do I prefer
okay okay in the original thing if I had
written the opposite signs don't worry
you can multiply y
by minus one right so there is a hyper
plane separating the cone and the point
B right this was the hyper plane
separation theorem
great now D could be empty or D could be
nonempty right if D is empty there is
nothing to prove both of them are empty
we never said anything but
suppose D is
nonempty that means there exist a y
Prime such
that sorry a transpose y Prime is
greater than equal to
C
right
so what should I do
now now I'm not viewing this as a cone
I'm viewing this as a constraint here
and what is my task I want to prove that
this is what do I want to prove p is
empty dual is feasible so I want to
prove that this
is unbounded right so you look at these
equations and tell me why it is
unbounded you should be able to see this
add a multiple of exactly if I take y
Prime add multiples of
Y what
happens is this constraint violated it
cannot be right so look at this
solutions
right they are
all dual
feasible
everyone
agrees this is also dual feasible
because a transpose y Prime is greater
than C A transpose Y is greater than
equal to zero so a transpose zi is also
greater than equal to C you take a
positive quantity bigger than C you add
a positive thing it will still remain
bigger than C again this is Vector
inequalities by the way right but it is
fine but what is happening to the
objective
value B transpose zi is B transpose
Yi plus
sorry B transpose y this is a fixed
quantity B transpose Y is negative as I
tends to Infinity this becomes minus
infinity
okay right because I have constructed
feasible Solutions of dual which are
taking my value
to minus infinity so that means dual is
unbounded
okay
clear and by the way if dual is
unbounded then clearly Primal is
infusible
right
why if dual is unbounded and if there is
a feasibility then they I have a lower
bound but I know lower bound cannnot
happen because this is unbounded right
so this unbounded feasibility all that
we can now leave and we know dual of
dual is Primal so we can say that if you
know p is D is empty then dual is
unmounted or right so we leave out
everything now we are in the final
interesting case which
is P and
D are
non-empty okay so both of them are non-
empty now I want to prove
that both the
values agree I get this this is my
target this is the interesting part of
the
proof
okay technicality is over this is the
main part so let's
focus and again the idea is to apply for
Kash
LMA right but what to apply for a
kashon right I don't see any uh like a x
equal to B is
feasible a transpose y great than equal
to C is feasible right so there is no
cone uh invisibility here on which to
apply a fkash gamma but let's
say so are nonempty and both are
bounded I can assume that because if any
of them were unbounded then I know that
other has to be empty right so if these
are nonempty implies both are bounded so
now
uh uh
suppose the optimal value of Primal is p
star dual is D
star okay this is just
notation uh and this is equal to C
transpose X
star P transpose y star okay and I want
to prove that these are equal so now the
the invisibility or the fact that you
know I can't write something as a cone
is
that let's look at everything in one
more Dimension and this is probably
something which I mentioned this is
going to be farkash LMA or this is going
to be hyperplane separation in just one
more
Dimension now let's look at all these
points
okay this such that X greater than equal
to
zero
right what do I know about
this if ax is equal to
B right then C transpose X
is less than equal to P
star that is the
optimal right so what do I
know if ax equal to
B then C transpose X is less than equal
to B
Star other way to say it
is can you find a point which is not
part of
this not in terms of
X okay very
good B comma P star +
1 right this is not part of
this
agreed though this is a good question if
you have done a discrete structures
course in previous semester but if
you're looking at linear programming you
don't want one here you want
Epsilon Epsilon greater than equal to
zero right why one this is a continuous
domain so we want to say that any B
comma P star plus1 B St B comma P star
plus1 is not there in this
scod okay and now if I saw solution for
for any of the Epsilon here then I'm
done okay so this is the plan once I
know that this point does not exist here
I can
apply farkash
Lama and using that I will construct a
solution for the further
do so let me just write down the
idea so yes when you look at it see here
it was quite clear how this was
hyperplane separation question what you
have to realize is that you can actually
write your objective function also as a
constraint you can
write or
is this
feasible right so you can apply you can
look at this in ver Moon Dimension and
apply
farash okay but let's not worry about
this let's see the straight direct uh
proof we just going to apply we are
looking going to look
at this
cone
okay
now ideally there should be vectors here
but it is understood there is a matrix
I'm talking talking about The Columns of
this so Columns of A and C they generate
a finite convex SC right and we also
know this is the point outside the
coin
okay so
idea
so one way to kind of understand it
is my my y AIS is going to be this last
AIS Okay
so
I have this
region this
is this is my feasible
region okay not feasible region but X
great than equal to Z what do I get here
right now this is the line where let's
say this line represents B
okay and this is taking different values
at the last coordinate okay so this is
in some sense B comma Infinity this is B
comma 10 the 10 or
what you know and this
is p star so I have rotated uh my
feasible set so that I'm aligned with
this
AIS right and here the feasible region
is going to be this line but that
doesn't matter what I'm going to say now
is that if you look at so I don't know
probably 10 to the 10 is here I don't
know so I don't want to write 10 the 10
but b a comma very very large value but
so
now if I look at
this this point is going to be outside
the feasible region and if that was the
case there would be a hyper hper plane
separating it but that hyperplane
separation will give me a dual
solution so that's why there cannot be
any gap between it all the feasible
Solutions of dual were giving me upper
bounds but if the upper bounds were not
tight then there is a gap here but the
Gap allows me to give a better upper
bound that's the
idea
okay
so let's apply for Kash LMA since you
guys are sleeping you will apply fkash
LMA I will
not wake up what does for fkash LMA says
there exist a y such that or there exist
a y Prime such
that
so let me just see if this is the sign I
want or I want to okay yeah this is fine
with me okay and obviously if you want
to reverse the sign you can can multiply
by minus but there is a y Prime right
and now
obviously one of this coordinate is
special right so I would split it with
this special coordinate so let's assume
y Prime
is y comma
U
sorry oh why is any general I'm just
writing the name the I'm calling the
first n coordinate M coordinates of Y
Prime as y the last coordinate as you
yes you can check that it's just matrix
multiplication and you can check that
and I'm going to write it for you this
is going to say that a transpose
y
plus
and why didn't I apply a transpose
here
it's a number U is a number remember
this is onedimensional
multiplication P Star Plus Epsilon is a
is a number this is a matrix this is a
vector inequality this is a
number okay oh sorry this is also
finally this is a number a transpose y
plus C no no no sorry sorry sorry this
is a this is a vector inequality this is
a number inequality right because B is a
vector U is
not
right okay
good uh where is the
is and now obviously just to make things
simple now even if I multiply y by any
scalar right still these inequalities
will remain True by a positive scalar
right so that means I can assume that my
U is equal
to is that
okay
sorry very
good it's
okay
yes
right so since I can multiply U by any
scal or actually I multiply all these
equations by any scalar constant that
means I can make sure that my U is
either 1 or minus one or
zero does that trouble
you right you have some number it will
be either be a positive number then you
can reduce it to one it's a negative
number you can reduce it to minus one if
it is neither negative nor positive then
the only possibility is zero Hur you
don't need to multiply it by
anything right so you can restrict it to
this case and why I'm looking at this
case is Remember If U is equal to
1 right uh sorry I I probably want to
switch
these yeah so U equal to 1 or U equal to
minus 1 this starts giving
me dual feasibility oh I'm just
simplifying my
analysis by saying that so now I'm
instead of saying that U is some any
number and then keep dividing by
It ultimately what do I want I want a
dual feasible solution right so you see
that this is a dual feasible solution of
that
form with u
extra this is almost a transpose y kind
of greater than equal to C right so if
the things are right you would be
good
okay uh by the way there is no transpose
needed here U is a
number
okay yeah so you so probably it's the
column of a transpose I was talking
about one of this but you
will those will match I don't want to do
the hard work but uh basically uh yeah
so so you have to just see whether this
this implies this is the cone generated
by the rows of a or The Columns of
a that you have to
see or uh yeah it is C transpose or
whatever so you you have to see okay but
this will match like this is not uh it
has to kind of one more Dimension
so okay
great so the meat of the problem is
here how do I use these to give me a
dual feasible
solution
okay okay
good so let's say U is equal to
minus1
okay
then I get that a transpose Y is less
than equal to
C
okay VOR sorry Vector C is a
vector this is a vector
inequality okay so probably it is C
transpose but again we have to match it
Dimensions I uh right so a transpose Y
is less than equal to C but from
here ppose Y is greater
than P Star Plus
Epsilon
correct
okay this
is dual
feasibility but in
the opposite direction and you remember
our meta
thing The Meta equations which we had
written if the Dual feasibility in the
opposite side then we should not get
upper bound we should get lower bone but
this is giving an upper bone there is
some
issue so this is going to give us a
contradiction Okay
so
we just take this multiplied by
xar correct what is
this what is
this x star is an optimal is a feasible
solution
right these are basically I have applied
The Meta inequality here right so in
some sense this is saying that your
picture will be oriented in the correct
way okay I'm just giving you intuition
but it is basically saying that U is
equal to minus1 is not possible so it is
basically saying that this thing
can't go in this
way that is a
contradiction okay so final thing has to
go
up that's the that's the kind of uh
that's that's that's what this all
calculation intuitively is saying
okay good so case
one case
two U equal to0
you will tell me what happens at U equal
to Z do it on your
paper pen and paper why case U equal to
Z do you get a dual feasible
solution you have these
equations I'll just put U equal to Z
here
then but we have already assumed that
Primal was
feasible right so U equal to Z is also
not
possible okay again intuitively this
means
that this has to be a non-trivial
picture in this
Dimension okay what does U equal to 0
mean U equal to0 mean that this hyper
plane it has nothing in this Dimension
so it is in this the picture in this
Dimension is kind of tre it is inside
that uh so all all those weird things
are not happening so these are again
cases which we are ruling out by saying
that oh this picture actually looks like
this everything is feasible then I'm
going to have some meat here it's not
like these are squished inside n minus
one dimension Subspace or something none
of that is going to
happen Okay uh what should I erase I can
erase
this so if U is equal to 1
a transpose
Y is
uh less than equal to C huh minus
C good thank you
and
U is
1 okay what do I want to do I want to
create
a feasible solution of the Dual looking
at this equation how do I create a
feasible
solution replace y byus
and I can play this
game
for
okay so that
means this implies D star is less
than
and now there might be people who are
very familiar with analysis and you
might ask oh what if infimum supremum
and all those things look at the note
there is an extra reading it basically
says we are in the nice world with this
linear optimization and everything we
know that the sequences will converge so
we are okay the we don't need to in
linear programming we will never talk
about inum supremum you always talk
about min
max what is the first property of
Duality any feasible solution will
always give you a value higher than P
star proving strong Duality never forget
weak
Duality right so we know that D is
definitely going to be bigger than P
star question is is it
equal Okay
so
this line is just for da
[Music]
okay
[Music]
