Lecture 28

[Music] welcome to the another lecture on linear programming we were looking at Duality Duality Theory and the perspective we had was giving bounds if a linear program is given to us in maximization format one way to give lower bounds is by showing a by showing a how do you show a lower bound here a feasible Solution on this side right and then the Dual allowed us to construct another linear program such that any feasible solution is an upper bound here and this is kind of symmetric in the sense that any solution here is a lower bound here any solution here is an upper bound here and in an Ideal World we would want that the best solution here is actually the best upper Bound in other words this optimal and this optimal is equal and since we live in an Ideal World these two things are going to match okay we do not live in an ideal world but these things are going to match right so this is the this can give you the strongest upper bound possible Right but there was a technicality right the technicality was about feasibility INF feasibility it might happen that this is infusible right what we know is if this is infusible if this is unbounded that means there cannot be a solution here and if this is unmounted then this is cannot be a solution here by the way small uh obvious question if this is unbounded that means the optimal value here is minus infinity if this is unbounded here then the optimal value is if this is infusible then the optimal value here is we will call it plus infinity so it's just to match again this is not mathematically matching right plus infinity is not equal to plus infinity that's not a mathematical state but just to make the convention similar saying that the values match generally for a minimization problem if it is infusible we say that the optimal value is positive Infinity for a maximization problem if it is infusible then we say that the optimal value is negative Infinity in some sense intuitively it makes sense right that as soon as you start getting Solutions here it gets it's it starts rising from minus infinity it can go up and up and so so on and so forth okay so now with all this actually I can write the strong Duality principle very clearly so this will be our formulation of strong Duality theorem again uh assume that you are given linear programs in this format standard format is this that means you are given c a b that's all right okay you are given these suppose p is the Primal feasible set similarly do is the uh D is the Dual phys set so this is a notation again I'm writing this for this particular standard linear program but you know it doesn't matter I can choose another standard linear program here get a dual for that and a similar theorem can written like this okay this is just to make it concrete but the strong Duality obviously holds for any linear program here and we saw last time how to take the Dual right we don't have to convert into standard form memorize this and do it right we can take it directly right we'll talk about it but yeah so if p is empty this implies dual is no D is unbounded or invisible okay similarly if D is empty these are the boundary cases okay and the interesting case is P and D both are non-empty and this is mostly going to be the case and if this is the case then optimal values exist and match okay sounds good and uh if you remember how did we take dual so just to remind you this equivalence was very important Primal constraints corresponded to dual variables and dual constraints corresponded to primary variables right and then we think of what elements should I multiply here so that I get a lower bound here right and this dual format will always look like this okay this this will depend on Dual constraint or Primal variable so this is because of okay so when you are given Primal your variables the sign of variables are specified you want to figure out the sign in the Dual constraint this will tell you how to if x is positive then y trans ose a should be more than C if x is negative then y transpose a should be less than C if x has no constraint then y transpose a will be equal to C okay there's no other way otherwise you cannot write this right you want to impose constraints on your dual constraint and Primal variables so that this is always true now when you look at this here I see Primal variables will be given that will already always be given to me then I can use the Dual constraint I can specify the Dual constraint such a way so that this is specified similarly this is done using B my Primal constraint will be given suppose it is given that ax is equal to B then whatever be y this will always be true this is the case here since ax is equal to B I have no constraint on y okay so this you if you know this framework you can figure out the exact constraints by yourself you don't have to memorize this is the Dual no just the idea is we want to take linear combination here so that we get something it looks like this what are the exact things they will follow from this uh standard set of inequalities this will determine and and this is very clearly this specifies this correspondence why this correspondence is there right okay so using this you can always take the tool then again but if you want to write this equation in some sense you always assume that both P and D are non empty okay this one equal here so yes this will be equal in this case but I'm writing this equation in general when you will be taking a dual and trying to emphasize the point that depending upon what is the constraint between a x and B I will keep y's so that this is satisfying it might be strict there are cases when this might be quality this might be quality I don't it's okay but General format is this right so there is this meta inequality which we will use to figure out exactly what will happen in your particular primma okay questions okay see it's always risky when I ask any questions and you don't because then I'm going to ask questions okay but that I will leave for some time but in the end I will ask questions if you are all okay about this okay but great so now we understand the intricacies generally plal and dual value will will agree except both could be invisible it could happen that one is invisible other is unbounded right these are the cases so and I probably told you before that uh and today we will see that the proof is basically based on farkash LMA right and you will see how why farkash Lama is like Elementary Duality and then elementary elementary Duality is row rank equal to column rank or the null space of a transpose and column space of a something which you did in the exam right so all these are some formulations of [Music] duality [Music] [Music] [Music]