Lecture 16

[Music] [Music] hello remember we were talking about convex functions convex functions are functions defined on real numbers or real number square or a convex region so we will always assume that these are the functions defined on a convex region and the important property that satisfied was this particular property which said that if you take two points X and Y and take a convex combination of them then the function value is lower than the value you would uh you would anticipate if the function was linear so let me just say it in terms of the graph it makes much more sense let's say my variables are Zed my function is f of Z a function which is depicted by this white line is convex because if I take any two points so I have taken these two points here these two orange points and if I join the line it is as though if my function was linear my actual function will lie below the orange line so the white line is lying below the Orange Line This is the value if the function was linear this is the actual function value so actual function value is is below the value anticipated if the function was linear this is called a convex function the opposite would be a concave function where you know the anticipated value is below the function value but we will be interested in convex functions uh and uh we talked about the fact that there are very nice properties of convex functions more importantly the central property we want is that if you talk about global if you talk about convex functions you optimize it over a convex region then Global optimality implies local optimality I want to give you an idea of the proof here but before I do that let's understand these terms okay first global optimality this is the natural notion of optimality let's say we are minimizing so we are interested in minimization let's keep that as constant a global optimal is the minimum point over the entire region okay okay what it means is given for all Zed a point xar is optimal if F of xar is less than equal to F of Z that means you take any point in the feasible region the function value is higher than the value at the global optimal this is what we are searching for when we minimize a function over some region we are looking for this Point what we want on the other hand local optimality you might guess is the condition which says that if you look at the point it is the minimum around it in the neighborhood the way we would like to say it is let's look at a ball a very very small ball around I should say xstar okay this means these are all points y such that y - xar the distance between y - xar is less than equal to Epsilon geometrically if this is my xstar I'm looking at a very very small neighborhood around xar and then a point is locally optimal if there exist an Epsilon such that xstar is the best point it's the optimal point in that small ball so I would like to say a point xar is local optimal if there is a small ball of radius Epsilon such that for all elements of this small ball not the entire region but every point in this ball X star is the best possible okay so Global optimal is when FX star is less than FZ for all Zed this is what we want and if you think about it this is what is easy to find in the sense that we only have to check a local neighborhood to find out if the point is optimal this means this is easy to find and like in life it's what we can find is necessarily not equal to what we want right this is the story of our life and in general if you want to optimize local optimal is what we can find but we need Global optimal that is why this property is so important it is actually saying for convex functions these two are the same in the sense that what we want can be found also other way to say it is intuitively minimization of convex functions is easy and you can guess that if I write maximization here this will become concave function but I think it is enough to look at one side of the story the other side is completely symmetric so this is the intuition and this is why we like this so much in general again I want to emphasize in general Global there can be many many local optimals but only one Global optimal fortunately when it comes to convex functions any fun any point which is local optimal is also Global optimal again I'm not saying that there is a single Global optimal what I'm saying is if there is a point which is local optimal it is also Global op optimal there can be infinite uh local optimal as well as Global optimal points but if you if if you are searching for optimal if you find a local optimal point you can stop there you don't have to move ahead because you are because the function is convex you know it is global optimal also this is why uh we really like optimizing over convex functions and if you think about this property this is not very difficult let me just show you this property you can visualize it by taking some examples okay the example one of the easiest example of convex function is x² I can plot x square with respect to X and the and it looks like a one dimensional again you can verify that this is a convex function but also it is easy to see from this graph if I take any two points the line connecting those two points lies above the curve of the function so we know that this function is convex and in this if you look at this bold shape there is only one Global optimal or local optimal notice that there can be functions where there are local optimals but not Global optimals for example look at this kind of a function these two points are local optimal but not Global optimal this point is global optimal you can easily verify that Global optimal is local optimal for FX is equal to x square we can take other functions FX isal to 1x X for X greater than equal to Z and I'm sorry yes the thank you tan for pointing it out FX is equal to 1 byx when X is strictly greater than zero because it is not defined at x equal to0 and then the function looks like this and again just by visual inspection you can see that the function is convex and also it is easy to prove that it is convex and then you can see that there is no Global Optima or a local Optima so we are good convex functions can be of many different kind one function could be such that it is a very very big number when X is less than zero some constant function then up to one it is zero and then it is x -1 so if I want to Define it uh this is you'll think of it as minus infinity zero this is zero X than equal to 1 and again you can see that the area above the curve is a convex region or if you take any two points the line lies uh the the curve lies below so then then this is fine and even here local Optimas and Global Optimas are the same in this case there are many local Optimas but all of them are Global Optima too in general the idea in the convex function is that if you look at the shape of the curve it's it's it's like a bowl which can hold water that's the intuition so even if yeah it will be probably be very hard for me to draw this but uh this will be a b a bold shaped picture where the region above the curve is going to be convex all these are convex functions and you can see that the global optimal is local optimal so I think at least by picture I have convinced you that this is the case but as m Ians we are not happy till we see proof this is in three dimension so yeah so I should say yes uh I should say X1 comma X2 and this graph is f of X1 X2 and then come down right so X1 X2 are in the you can think of it as a plane and then this is the AIS so it will look like this this po kind of a thing symmetric about both exes coming down coming down very nice yeah so as tan said if you want to visualize this as a picture you can think of it as a circle so my X1 and X2 lie in a plane my f of X1 X2 I drawing on the line going up and then you have Centric circles whose radius is decreasing as you go down this is the shape which will be there and you can see that this is kind of a nice symmetric Bowl which is a convex region and that's why it's a convex function great without further Ado let's see the proof of this we want to prove that Global optimal is local optimal how can we do this okay let's assume the qu assume there is a Lo local optimal point which is not Global optim okay so let's say uh xstar is local optimal but Zed is global optimal what this means is around the neighborhood of X star FX star is the best value but actually there's a point probably far away where FZ is less than FX star okay and you want to say that such possibility cannot arise why because f is convex and the region on which the function is defined is also convex this is the region so let's look at it I think two dimensions are good enough to give you the intuition let's say this is xstar uh FX star and somewhere there is a point Zed so let's say this is f of Z also so my curve lies somewhere like this the intuition is if I look at the line which joins Z and xar what is the function value and I know from the property of the convex function FX star this is just because f is convex notice that all these points lie in the feasible region because my region is convex the region on which function is defined is convex so that means all these points lie in my region and now the claim is that this quantity is I should say strictly less than FX this is an easy exercise notice that FZ is less than FX star if FZ was equal to FX star this quantity would be exactly B FX star but since f Z is strictly less than FX star these two coefficients add up to one this this quantity is less than FX star so that means everywhere on this line my value is less than FX star but then some part of this line has to lie in the neighborhood of FX star however small my neighborhood is this finishes the proof If I want to write it in the formal terms I will say assume this is the ball around xstar such that for all Zed uh element of uh FZ has to be more than FX this is by the local optimality property of FX star uh of of F and X star but there exist a very very small there is uh Theta I have taken it as 1 minus Theta so I should say there exist a Theta which is approaching one such that uh notice this is the line joining Z and xstar so as I increase Theta as I approach Theta close to one the point gets closer and closer to xar so if there is a ball around X star there has to be some part of line inside it that means there exist a Theta such that this point lies inside the ball so then there exist a Theta so this is part of B Epson X star but from that equation I know this is again because of convexity property here and the fact that F of Z is less then strictly less than FX star but this is contradiction uh this point was supposed to be bigger but this is smaller so uh this small proof shows a very nice property that Global optimal is same as local optimal and again I would like to emphasize that this shows that uh it is I wouldn't say easy but that difficult to check optimality and again the intuition is if I am at the point uh and I want to check it is optimal or not it might be very hard to check it is globally op optimal but if I only want to check it is locally optimal I just need to search in the neighborhood probably just want to see in all directions that the value decreases and that's enough to show that my point is locally optimal and uh this intuition will help us build algorithm for linear programming but before I give you the idea of the algorithm for for linear programming I also want to say one more property of convex functions which is that maximization lies on the boundary if you minimization if you want to minimize Global optimal is same as local local optimal but if you looked at all the shapes for the convex functions the maximum always lies at the boundary and this is clear from the picture if you have a convex function the function keeps increasing and the maximum Li on the boundary I will not prove it I will give it to you as an exercise but the simple idea is that if the maximum let's say Zed does not lie on the boundary look at the point at the boundary and the line connecting these these these points and you will be able to see that if uh so Z should be in the Z should be written as a combination of two points at the boundary right uh every point which is not on the boundary we should be able to write it in terms of the two points and then if FY star and FX star are less than FZ or I'm yes uh if suppose FZ is the global optimal then this is higher than FY star FX star then you can actually show that any point on X star and Y star will be below the maximum of T2 but again I would not go into the detail I will leave it to you as an exercise great we know nice things about convex function notice we'll always assume that the region where the function is defined or our physic region is convex now if you have a convex function minimization Global optimal is same as local optimal maximization optimal lies on the boundary these are the t two properties we have seen we have seen the proof of this I've given you some idea of why optimal lies on the boundary you can fill in the details now similar thing if I write it for concave functions I would say that if it is minimization optimal lies on the boundary or the vertex if your feasible region is convex and for maximization Global optimal is same as local optimal this is what we have seen today and just uh approaching it in the same way a symmetric proof will give it for the concave function why is this nice it is nice because when we talk about linear programming we are going to optimize a linear function over a convex region and now you should be happy what does it mean that a function is linear a function is linear that means it is convex as well as concave that means we have this properties as well as these properties for linear programming that's great so then for linear programming for whatever maximization we want to do for whatever optimization we want to do whether you want to maximize or minimize it doesn't matter we always have Global optimal equal to local optimal and the second property is optimal lies on the boundary or for us because we have a convex region it lies on the vertex these two properties are Central to defining the Simplex algorithm the idea of the algorithm is not very difficult I will give you the idea and then we will see the formal algorithm in the future lectures remember these are the two main properties we are going to use Global optimal is local optimal and optimal lies on the bound on the vertex the proposed algorithm is first find a Vertex obviously we are interested in comparing value of our function on all the vertices okay and yeah actually let's let's let's talk about this we know that optimal lies on the boundary I give you a very very simple algorithm look at all possible vertices look at all possible values on those vertices find the optimal that is going to give you the answer why is that not a good solution why is that not a good algorithm what do you think we can take all possible vertices of the phys region and ask what is uh what is the optimal among those vertices we know it has to lie on the vertex good tufan has very nice idea he says there might be many points many vertices in the feasible region and you can actually show that there can be convex regions which have exponential number of points in terms of the dimension so this uh algorithm is really not efficient we need smarter way to search for a Vertex which is optimal we can't just list out all the vertices that will take lot of time so that's not a good uh idea but again using this we can refine it the idea is find a Vertex I'm not telling you how to these things will become clearer from the next lecture the proposed algorithm is find a vertex calculate the value and check if it is optimal now this is easy because of property one what it means is for our convex region if this is my convex region I'm at this point I just need to check whether in both these directions my value increases or not and that's good enough to tell us whether this is a local optimal or not but local optimal implies Global optimality so we just going to check the local optimality here so checking if it is optimal is easy because we can just check all the directions from that vertex all the edges from that vertex and that is enough if it is not optimal move in the direction of optimality that means suppose we were at this vertex we wanted to find the maximum the function value if it doesn't increase here doesn't increase here we stop because this is optimal but let's say the value increases in this direction if the value increases in this direction we can go and find another vertex in this so then we the move in the direction of optimality and find a Vertex again this is the idea of the Simplex algorithm again there are many many things which are not clear here how do we find a Vertex how do we actually check if it is optimal and then what does it mean to move in the direction of optimality so describing these will finish our exact description of Simplex algorithm and that's what we will see in the next lecture how to make these this idea concrete thank [Music] you [Music] [Music]