Lec 32 | Applied Optimization | Test for Convexity, Quasi-Convexity: Examples | IIT Kanpur

Hello, welcome to another module in this massive open online course, so we are looking at example problems in convex functions and convexity, let us continue our discussion. So we are looking at example problems in convex functions and well let us look at this problem number 5, f of x bar equals x1, x2 for the region where both x1, x2 are greater than or equal to 0, we want to ask the question is f of x bar, of course x bar you can think of this as the 2 dimensional vector, this is a function of 2 variables x1, x2, we want to ask is this convex or concave, convex, concave or neither, remember it function need not be only either convex or concave, but can be neither convex or concave, so that is an important point to keep in mind. Let us start by looking at once again, remember we have a simple test for convexity that is the Hessian, which in this case is simply dou square f by dou x1 square, dou square f by dou x2 square, these are the 2 diagonal elements and the off diagonal elements are dou square f by dou x1 partial with respect to x1, x2 partial with respect to x1 and x2 and this is equal to if you look at this partial with respect to the first partial with respect to x1 is x2, partial with respect to x1 of x2, so you can evaluate this as follows dou partial second order partial with respect to x1 is partial with respect to x1 of partial with respect to x1, but partial with respect to x1 is x2, so this is partial with respect to x1 of x2 which is 0, so you can see this is 0, partial with respect to x1, x2 you can see this is 1, partial with respect to x1, x2 is 1, second order partial with respect to x2 is also 0. Now, first thing you can see is this is a symmetric matrix, so this matrix here the Hessian is a symmetric matrix, but this is not positive semi definite, in fact if you look at the determinant of this, this is 0 minus 1 equals minus 1 this is negative. So, the determinant is negative, remember the determinant of a positive semi definite matrix has to be a positive quantity, because the determinant is a product of the Eigen values all of these Eigen values are either are non negative. Therefore, the determinant has to be greater than or equal to 0 for a positive semi definite matrix, in fact if you compute the Eigen values that is find the characteristic polynomial minus lambda times i and take the determinant, this is equal to determinant of 0 1 1 0 minus lambda times 1 0 0 1. And you take the determinant of this that is equal to minus lambda 1 1 minus lambda and if you take the determinant of this that is basically lambda square minus 1 and lambda square minus 1 equals 0 implies basically lambda equals plus or minus 1 and you can see the Eigen values are both positive and negative, it has a positive Eigen value and a negative Eigen value and negative. So, implies matrix remember positive semi definite matrix has only positive semi definite matrix has only non negative that is Eigen values are greater than equal to 0, here you have a negative Eigen value that is minus 1, which implies the Hessian is not positive semi definite. And therefore, f of x bar is not convex implies delta square f of x bar is not positive semi definite implies f of x bar is not convex. Now, what about concavity for that consider minus x f tilde equals minus f x bar equals remember f of x is concave if minus f x is convex. So, we consider minus x 1 x 2, now consider the Hessian of f tilde the Hessian of f tilde is simply the Hessian minus of the Hessian of x bar. So, this will be 0 minus 1 minus 1 0, now again check the Eigen values delta square f tilde the Hessian minus lambda I determinant, look at the determinant of the Hessian this will be the determinant of well minus lambda minus 1 minus 1 minus lambda minus 1 minus lambda equals once again lambda square minus 1. And once again lambda square minus 1 equals 0 implies lambda equals plus or minus 1, again the Hessian of f tilde is not positive semi definite, which means Hessian of f which means f tilde is not convex and therefore, f is not concave remember f is concave only if f tilde that is minus of f is convex. So, this implies f tilde x bar equals minus of f of x bar is not convex implies f of x bar is not concave f of x bar is not concave. Now, so f of x 1 x 2 you can see it is very interesting it is neither convex nor concave that shows that any function does not always means not convex does not automatically mean that it is concave. There can be functions which are neither convex and concave and that is easy to see, because if you have a function that looks something like this neither convex nor concave and so these kind of functions these are neither convex nor concave. Something to keep in mind how about quasi convexity now for quasi convexity remember you have to look at the level sets S of t equals x bar such that x 1 x 2 less than equal to t. Now, if you look at the set x 1 x 2 less than equal to t what you will observe is that if you plot this if you look at the set x 1 x 2 less than equal to t that will be this set this is the curve x 1 x 2 equals and this is the area that is x 1 x 2 less than equal to t and you can see this set is not convex this set is not. On the other hand if you look at the super level set that is x 1 x 2 greater than or equal to t this is a convex set, because if you take any two points join them by a line it lies in this set the super level set x 1 x 2 greater than or equal to this is a convex set. So, implies thus not the sub level set super level sets equals is a convex set. So, that is super level set sub level set remember is the set such that x 1 x 2 is less than equal to t super level set is the set x 1 x 2 greater than or equal to t for any parameter value of the parameter t. So, the super level sets are convex which means this is a quasi concave implies this is a quasi concave this is a quasi concave. So, x 1 x 2 neither convex nor concave it is a quasi concave similarly let us now move on to the next example. Let us now consider the reciprocal of the previous one f of x bar equals 1 over x 1 x 2 again we want to ask the same question is this function 1 over x 1 x 2 is it convex or is it concave and you can once again find the Hessian of this the Hessian of this will be well let us first start with a gradient x bar is again the two dimensional vector this is a function of two variables x 1 x 2. So, the gradient with respect to x 1 x 2 will be well this will be derivative with respect to x 1 that will be minus 1 over x 1 square x 2 derivative with respect to x 2 will be minus 1 over x 1 x 2 square and now the Hessian will be take the first element differentiate it with respect to x 1. So, that will be 2 over x 1 cube x 2 and now differentiate the first element with respect to x 2. So, this will be 1 over x 1 square x 2 square this will be 1 over symmetric. So, this element will also be 1 over x 1 square x 2 square the 2 cross 2 element will be well that will be 2 over x 1 x 2 cube and now we have to see what is the is this matrix positive semi definite and you can simplify this by bringing x 1 cube x 2 cube outside this will be 1 over x 1 cube x 2 cube times well times this is twice x 2 square twice this x 1 square and this will be x 1 x 2 x 1 x 2. Now, we want to ask the question is this matrix positive semi definite this is the Hessian and we want to ask the question is this matrix positive semi definite. Now, there are many ways to show this if the matrix is positive semi definite one of the methods is of course, to compute the Eigen values which might be slightly tedious what we are going to do here is we are going to decompose this in the form of factors which are a times a transpose. Now, remember each such factor is positive semi definite we said that if a matrix can be expressed as a a transpose this is positive semi definite and the sum of such positive semi definite matrices is positive definite. So, we are going to factorize this into a sum of matrices which can be expressed in this form and you can clearly see it is not very difficult you can first write this as x 1 cube x 2 cube you can write this as x 1 or x 2 square x 1 x 2 x 1 x 2 x 1 square x 1 square plus this will be 1 over x 1 cube x 2 cube x 2 square 0 0 x 1 and this will be now I can decompose this into factors now you can see this will be 1 over x 1 cube x 2 cube times x 2 or x 2 x 1 times x 2 x 1 x 2 or x 2 x 1 times x 2 x 1 that is this is of the form vector a bar into a bar transpose plus obviously, the next one you can easily see that this is x 1 cube x 2 cube diagonal matrix x 2 0 x 1 0 times x 2 x 1 x 2 x 1 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 0 and this will be a matrix of the form B B transpose. So, we are decomposed it into the sum of matrices which are factorized as A A transpose. So, each of these matrices component matrices is positive semi definite therefore, the sum is positive semi definite you can easily see that if two matrices are positive semi definite all right compatible matrices if you sum them you get another positive semi definite matrix. So, this is positive semi definite this is positive semi definite and therefore, this implies that basically your matrix this implies that this is the sum of two positive semi definite matrices remember that this is also only for x 1 comma x 2 greater than or equal to 0 which means these factors that is if you look at these factors these factors 1 over x 1 cube x 2 cube is or also greater than equal to 0 therefore, this is positive semi definite matrix matrices weighted by positive factors. So, these are positive this these are positive. So, the resulting matrix is positive semi definite. So, that means, the Hessian is positive semi definite Hessian is positive semi definite remember this notation which implies that f of x bar equals convex and it can also be seen that since it is convex it is also quasi convex because any convex function is also quasi convex. So, this implies that f of x bar also quasi convex. So, it is 1 over x 1 x 2 remember what is f of x bar f of x bar this is 1 over x 1 x 2 this is quasi convex. So, 1 over x 1 x 2 is basically convex and hence it is also quasi convex. Let us look at another example and this is you can treat this as a practical application in fact, it is a very interesting we are going to look at the entropy function that is which can be defined as the entropy of a source h can be defined as minus summation or entropy of a minus summation i equals 1 to n x i log of x i plus 1 to n x i plus 1 to n x i plus to the base e natural log x i where x i equals probability of the i th symbol this is the probability of the i th symbol and this entropy denotes the information content of the source this entropy denotes the information content of the source that is given an source with n symbols which have probabilities x 1 x 2 up to x n what is the average information content per symbol of this source that is given by the entropy that is minus summation x i log log of x i and therefore, the higher the entropy it means the higher the information content of the source and therefore, we would like to maximize this entropy quantity and that has very important applications in information theory. So, we would like to maximize maximize the entropy or the information content. So, this has applications in information theory. So, this is a very important quantity in information theory and by extension in also wireless communication and signal processing. In fact, many fields machine learning also since information theory has widespread applications in several right as several applications as several applications in various fields. So, therefore, this quantity entropy is very important. Now, what we want to show is that this quantity entropy is a concave quantity and that is relatively easy to show we start by considering f of x equals x log x that is the natural logarithm and we demonstrate that this is convex you take the first derivative this is very simple this is x. So, we use the product rule. So, first differentiate with respect to x that is 1 times log x plus x into the derivative of log x which is 1 over x which is basically log x plus 1 and now if you look at the second derivative that will be derivative of log x which is 1 over x plus 0 which is 1 over x that is greater than equal to 0. So, this implies x log x hessian is greater than equal to 0 this implies x log x or second derivative greater than equal to 0 implies x log x is convex which implies that minus x log x equals and therefore, now if you look at the entropy log to the you can see this is the sum of concave functions implies this is concave. So, the entropy is the sum of concave functions and therefore, this is in turn concave and therefore, one can maximize the entropy thus maximizing the average information of the given source. So, we will stop here and continue in the subsequent modules.