Lecture 13

[Music] [Music] this was correct convex sets again this turned out to be different right so we will only describe a subset of these okay so a special what does happened to my spelling skills polytop and polygons right and this is going to be your not just for the standard ones right this is going to be intersection of your constraints okay and let's look at this so let's make this picture complete this was a a fine set or a hyper plane geometrically it was a hyper plane it looks like a plane moved from the origin to some other place fine what is this yeah this is not a plane this is a half plane we call it half space and yes you take a line This is the line describing a transpose x equal to B either this side or that side depends on what A and B are one part of this is going to be a transpose X greater than equal to B other is less than equal to a cool okay and now if I take intersection of half space is I start getting polygons how do I get it I need more colors this is an inequality this is an inequality this this is an inequality this is an inequality right if I take the intersection I get this polygon okay but now you also see that it need not be bounded right for example if I take intersection of this is ax thing but it is not bounded but whatever boundaries are there they are lines this is a polygon this is a polytope this is also a polytope but this is also a polygon right clear so this is what we achieve with this intersection of a transpose x uh intersection of a transpose X less than equal to B so now I can give you a mathematical definition of a polytop which is a set s which is described by uh some inequalities so any set which is kind of intersection of our constraints is going to be a polytope and to prove that this is same as the geometric picture is called MOSI well theorem and we are not going to worry about it we just thank uh we just thank minkovski and will that they proved it it's going to be very useful but kind of not that easy to prove so you will skip it but what we will remember is this dual picture oh this is saying that these two definitions are the same so the the that uh okay I have to be much more careful this is going to be a polytope this is how I a polytope this is going to be a convex Hull of finite number of points with some rays like you have this infinite directions right so then you have to precisely Define this but I want to just do it geometrically but there is a kind of a cleaner way that you have finite points and then you have convex all of that and you're allowed to put extend them in in lines and that is going to be a polytop or polygon and that is same as these equation description okay yes yeah uh in two Dimension hard to visualize but if you take it take take them in higher Dimension you will see that they will give you some kind of so it's easy to see that these intersections will be convex right and then their boundaries would be linear so and yeah but I cannot draw four dimension and I cannot imagine also visualize also so when when even when I say that these intersections are going to be uh convex set polygon or polytope I believe menovsky and will right so they they look something like like that but you know yeah I understand it's weird because this looks like a linear Subspace but then we taking intersection so that that linear Subspace will be cut into Parts okay but the whole thing was done so that we understand convex sets are feasible region nicely this is visible region so our phys is going to be polytop or polygon no no no this theorem is telling us that our feasible region will look something like this but where did you prove that this set looks like or or it let's say if it is bounded it's a convex Hull of finite number of points what are those points how mathematically two ways this is one and other as I was pointing out to him you say it's a you take few points and few directions okay so it is convex combination of points and then you can extend them in any direction but that is not going to be useful that's why I'm not doing it you can read about that on internet but it is so if if it is finite if it is bounded then it is clearly convex combination of finite sets but now we want to allow infinite Rays also so it is convex combination of points and then you can extend them with some some rays so there are vertices and then there are rays that that is how you can Define them geometrically I am just giving you a picture for that is that okay so yeah X1 to xn V1 to VK then it is convex combination of this plus I haven't defined cones for you yet but you can extend them in this direction V1 to VK here there is no uh this uh the coefficients of this need not sum up to one just go in that that direction as much as you like okay so for example if you uh yeah remember this it is convex combination of this extended in this direction there is One Direction where it can lead to okay this is the picture we will we will have in mind the thing which we have not talked about is SPS yes Circle that's why I draw those weird shapes which looked like convex but you were not sure all those shapes are sorry no no this extension is also there right so that's why if you want to be mathematically precise then you have to appeal to this minovi will will theorem okay so we have seen a fine combinations we have seen convex combinations and then uh the thing which is left is what we call conic combinations right and your question should be that oh we defined a fine we defined uh uh convex sets what about cones conic sets or something first I Define cone a set s is called a cone if for any point x uh this is uh the line from origin to Alpha is contained in s okay so it basically looks like a Coe it's a cone if it looks like a cone okay and now you might be asking what if is it true that if I take two points they're conic combination is inside the cone or not what do you think yeah uh oh sorry yeah thank you thank you half line yes so what do you think does the cone contain all possible conic combination of the point inside it that's because you don't use pen and paper just these two lines is that a core or not yeah this is origin yes but it definitely doesn't contain the conic combination of these two points right so yeah uh there are reasons why we study cones and then we study convex Coes which are going to be you know more like containing all the possible convex combinations also but that's for the next class okay so now our plan is learn about convex cones then convex functions and once we learn that a nice algorithm for linear programming will pop up and you might think oh we did this all this linear algebra and our efforts went to waste no the things which you learned you know remember the solution space looks like this all that all that intuition will be helpful while implementing solution based on this okay this a good reminder nothing goes to waste especially in math right so we did linear algebra it did not give us it gave us Simple Solution but now we will see with this extra conditions our solution becomes slightly difficult but that can be obtained from what we have seen by modifying them appropriately okay and that's the plan for future lectures thank [Music] you [Music] [Music]