Lecture 11

[Music] [Music] welcome to the course on linear programming we have seen linear programs we have seen some linear algebra specifically how the solutions of ax equal to B look today we will see that that is not good enough and we have to introduce the concept of convexity Theory but before I start what happened here right so the idea was that the solution set of this was easy to describe right if you remember I take the Matrix a and I can do goian elimination right so if I do goian elimination it turns out I will have this kind of a structure where I don't know these this will be some entries but what do I know these are my leading variables and these are my free variables right so let's just call the leading variables X12 XK and the free varable Ables XK + 1 to xn right so what do we know if I want to create any solution of ax equal to B then how can I do it so first fix up anything any value of free variables right so this can be obtained by two steps first and then once you fix up these values this will determine the value of X1 to XK uniquely and this is given by these coefficients right so sounds good this means there is no restriction on XK + 1 to xn right this is anything in R to the N minus K I can fix these values as as whatever I like and then I'm by arranging X1 to XK in a certain way determined by these coefficients I am sure to get a solution of axal to B right other way to say it I would is write X1 to XK as linear combination of XK + 1 plus some constant C1 some coefficient here some coefficient here similarly sorry [Music] CK but once I know this I can substitute this in C transpose X and then I have got a function of the kind was it minimize okay these coefficients will change plus some constant C and there are no constraints remaining right it is just optimizing this linear function and now my life is easy this is going to be minus infinity if any of these are non zero because then I can make sure that going in that direction I can make it negative there is a trivial case uh you have to remember that if all of these are zero then that means for any solution the objective function is C okay this is all so this basically means this is very simple to solve because even in a very bad case you can do gasan elimin in order of n Cube Okay order of n cube is a pretty good bound on what's in elimination probably do better but yeah so that means we can solve this problem very easily correct great so this direction did not help it shows us things only become interesting when I have this constraint right otherwise there are not many applications also it's it's this constraint which is making this linear program interesting and you remember what we were trying to do we were trying to learn in programming and now we tried a simplification that is too simple now we want to see oh life is not that simple but can you still get some more information right so when our feasible space was a vector space right ax equal to B the solutions of axal to B is a some kind of a fine space that's easy that's not very difficult but that's not going to be the case so the question is is there still some structure of visible space which allows us to solve it easily right so the question in other words is how does feasible region change with X greater than equal to constraint okay and when you can't solve a problem the best thing to do is now we are not in linear algebra right we have come out of linear algebra so gods and elimination is not the answer to everything assuming something yes uh so that we tried uh and generally it is good to look at small subcases right you want to simplify the problem there are many ways to simplify a problem remove an assumption or now in this case since you want to understand the structure let's at least see what happens in 2D or 3D so now let's say in 2D that's the simplest I have uh program uh so minimize something I don't care I'm interested in just the feasible region let's say this is the the problem right if this is the case and there is some line like this right so what is my feasible region no just the line segment right my feasible region is just this right and now this is not a vector space but then what is it it's still nice right it's still a line segment it's not completely unstructured or something so what do we know about line segment it's actually a convex set and once we observe this we remember movi and say oh in 1900 he has done so much about convex sets let's learn from him let's see what has been done and see if we can apply those principles in our problem and this is what we are going to do in next week so we to learn convexity we going to learn about convex Theory and immediately we will see that an algorithm pops out because of the structure already known of convex sets sounds good that's the plan our Target becomes learning convexity theory how many people have studied convexity Theory before some idea okay so convexity theory is study of convex sets and convex functions and if you read this what you realize is most important thing is this word convex right and the first thing we will start with is convex combination and again the idea is to describe this line segment instead of this line right so in a plane how do you write if you are given vectors uh let's say X1 X2 or let me these are two vectors in R square what is the line passing through it Lambda where Lambda is is that okay with everyone correct cor what is this this is a linear combination right and then that means in two Dimension this is what is this what is the shape plane mostly a plane right except some trivial cases when these are linearly dependent right good so first thing was from linear combination if I wanted to come from the entire plane if I wanted to restrict my attention to a line I do this okay so this is a line This is a plane and how do I get a line segment anyone accept Dave thank you right so it is Lambda X1 + 1 - Lambda X2 such that Lambda is in zero right and now when you look at all this there should be one more combination which should come to your mind what is that so this is called convex combination this is going to be important what is the remaining combination if you see these cases don't think of geometrically look at these three so now I started with any general Lambda 1 Lambda 2 I put one kind of constraint I put another kind of constraint what kind of constraint is remaining so this was a plane this is the constraint that summation add up to one this is the constraint that that both are positive if you mix these you get this this is called conic combination okay and how will the conic combination look right suppose this is a point X1 this is a point X2 the conic combination what will be that set what will be that set you can tell me definitely this point is going to be there this entire line is going to be there you can convince yourself of that okay you can you can at this and now because I talked about convexity Theory convex sets and everything it seems like this is the most important thing but I assure you all four are going to be important for us all four kind of combinations are going to be useful for our study of linear programs and the reason is pretty simple if you look at constraints something like a transpose x equal to B this is going to be an a fine set if you look at this is a right so all these shapes all these combinations are going to arrive when you when we are going to study linear programming make sense and this is what we are going to do study these combinations that's the plan for today okay just to make sure that you understand what is going on which which statement is correct let's don't discuss let's take a vote four options right none of that is correct both of them are correct first one is correct second one is correct that is why India does not have a good political system because nobody votes like out of 12 people only three people voted what the hell okay think about it I will give you some time but everyone has to vote bring out your pen and paper good okay very good so the first question to ask is we have seen an example of an aine set I told you that line segment is convex a line is aine right so at this point you can only answer this in terms of examples okay but an aine set is something which has all its aine combinations a convex com convex set is something which has all its convex combinations oh I just told you I had written down these once okay let me just write it uh so the the way to remember it is linear combination is a fine the constraint is Lambda 1 + Lambda 2 = to 1 kic is Lambda 1 Lambda 2 greater than equal to zero convex is which basically means it lies between 0 and one okay the a transpose x equal to B no the space you get is not a plane you get a line right for example when it was 3x + 2 yal to 5 in the two Dimension did you get a line or did you get a plane you got a line right so it's only an aine combination don't get confused by when I say ax equal to B are you thinking of it in terms of and you are saying that's why this is a linear combination no here what you are saying is uh you are allow any X1 to xn which satisfy this equation are going to be in your feasible set it is not saying that you have X1 and X2 and X andr vectors here and you're taking any possible linear combination here that's not what you are saying right so don't get confused and and this is actually very important it's a very nice question because we will see this duality in terms of oh it's a linear combination comination a fine combination or I can describe it in terms of equations both sides are very important for a geometric picture oh it's a linear combination or a fine combination but if I want to study it then I also want to see the equalent way in which it can written it can be written down as an as a bunch of equations and this we will see okay so this is very nice this this confusion is natural to arise but we should remember so all these sets we will describe in almost two ways okay so now you know an aine set is something which contains every aine combination a con convex set is something which contains all the convex combinations now let's vote okay how many for one One V okay okay both incorrect people are guessing how many for three there is influence you're not allowed to either you would not vote or you will vote twice there's something wrong with the youth in this country 1 2 3 4 5 you voted already I know yeah and you said that is obvious no no this is the correct answer given that out of 15 people only five got it right it's definitely not obvious right so what is happening here a line segment remember a line SE a line was a fine is it convex why not take any two points take any anything here it's convex combination is inside that line yes no how does convex combination look it's the line segment between the two points right that we described remember I said what is a line segment it's a convex combination of those two points right so if you take a line you take any two points the line segment between them is part of this so it also contains convex combination so a fine implies convex and a line segment this is convex but not a fine why because the fine combination of this point these two points will be the entire line and you can make an argument you know oh the fine combination condition is stricter convex combination con is weaker and I always get confused you can do that and you can figure out and say that oh the condition for this is weaker than the condition for this sorry the other way this is the stronger condition this is the weaker condition so if the weaker condition is true this is fine right but if you get confused line segment line is your friend this weaker and stronger is always confusing for but yeah if you are very very precise and if you are not drunk then even the weaker and stronger will will make it work and for the record I'm not drunk now but okay good so a fine combination all those are making sense now [Music] [Music] okay [Music]