Lec 25 | Applied Optimization | Test for Convexity | IIT Kanpur

[Music] [Music] hello welcome to another module in this massive open online course so we are looking at convex functions and test for convexity we have seen the test for a function of a single variable correct when y equals f of X and f of X is a one dimensional variable correct let us now extend that test for functions of a vector or a multi dimensional variable okay so we want to find the test for convexity okay and we want to consider y equals f of X bar so this is a vector now okay so X bar equals this is an N dimensional vector X 1 X 2 up to X n so this is n dimensional vector and so we want to find the test for convexity for this function of a vector and for this we want to first define the gradient of this that is the gradient with respect to X I'm just going to simply write this as gradient of F with X part since it's clear from the context that the function is of the n-dimensional vector X bar this is simply defined as the vector which contains the partial derivative with respect to each component of the with respect to each component of X F ok so this is also on the gradient is also an n-dimensional vector okay so what is the gradient of f of X bar that it contains the partial derivative of F with respect to X 1 partial derivative of F with respect to X 2 so on and so forth until the partial derivative of F with respect to X n ok so it's also an in dimensional vector of partial derivatives ok 1 with respect to each component of the vector X bar now what is the Hessian we want to consider the next that is the Hessian okay so this is denoted by square of x-bar this is a matrix of partial derivative second order partial derivatives dou square f by dou X for square dou square F or let me write it here the Hessian of F is to square F by dou X 1 square dou square F by dou X 1 partial with respect to X to go square F by dou X 2 so X 1 dou square F by dou X 2 square dou square F by dou X n dou X 1 dou square F by dou X 1 dou X n so on and so forth 2 square F by dou X n square okay and this is basically the Hessian okay so this is you think of this as a second order derivative this is the Hessian where the IJ entry if you look at any IJ entry of the hessian the IJ entry incorrect Delta square F if you look at the IJ entry that is the second-order partial of F with respect to X I and X G that is the IJ at entry so it is a matrix with the IJ and naturally this is going to be a needless to say this is an N cross n matrix for an n-dimensional vector X bar okay so this is an N dimensional for if you consider a vector X bar to be n-dimensional then this Hessian is an N cross n matrix with the IJ Maitre entry corresponding to the partial second-order partial derivative of F with respect to X I and XJ okay now the condition the test for convexity okay the test for convexity of this vector X bar is that we have to have the Hessian with respect to X bar this has to be remember this symbol this denotes a positive semi definite matrix so if this is positive semi definite that is Delta square that is the patient equals a positive semi definite matrix this implies this implies that f of X bar is convex so if the Hessian is positive semi-definite we have f of X bar is a convex function of the vector X bar so we have to compute the Hessian of this function multi-day this function of the vector X bar and check if the Hessian is positive semi-definite and it's positive semi-definite one can conclude that f of X bar is convex okay let us understand that by looking at a simple example a simple example let us consider ref of X bar I am going to first talk about a simple X so first let's start with a two-dimensional vector X bar ok so X bar equals x1 okay and we have f of X bar equals x1 square let me write this clearly f of X bar x1 square divided by x2 then first let us consider the gradient with respect to X bar so that we know is the partial of F with respect to X 1 the partial with respect to X 2 okay now partial derivative with respect to X 1 treat X 2 as constant differentiate with respect to X 1 that gives us 2 X 1 by X 2 partial with respect to X 2 treat X 2 is constant differentiate with respect to I'm sorry treat X 1 is constant differentiate with respect to X 2 so that will be minus X 1 square by X 2 square correct so we are treating X 1 as a constant and differentiating with respect to X 2 ok now consider the Hessian with respect to X that will be just to refresh your memory that will be dou square F by dou X 1 square dou square F by dou X 1 2 X 2 dou square F by dou X 2 dou X 1 and finally though square f by dou X 2 square which you can see is the following thing this will be well this will be 2 over X 2 this quantity you can see minus 2 X 1 divided by X 2 square in fact dou square f by dou X 1 dou X 2 will be same as dou square F by dou X 2 2 X 1 which will be minus 2 X 1 divided by X 2 square and finally do square if there's the second derivative of second order partial derivative with respect to X 2 that is 2 X 1 square divided by X 2 cube okay and now if you take 2 over X 2 cube as common we have X 2 square minus X 1 X 2 minus X 1 X 2 and we will have this one is X 1 square which you can now write as you can decompose this matrix above as follows you can write this as you can see this will be x2 minus x1 times x2 minus x1 and if I call this vector as u bar this will be u bar transpose so this will be 2 by I'm sorry 2 by x2 cube X 2 to u bar u bar transpose okay that is the Hessian so this is the Hessian okay where you bar is the vector X 2 minus u bar is the vector X 2 minus X 1 and now here you can see that if there is any matrix P that can be decomposed as a a transpose or for that matter uu transpose then it is positive semi-definite and this can simply be seen as follows many of you might already be familiar with it if you have any matrix P which is basically can be written as a matrix u times u transpose then X bar transpose P X bar equals X bar transpose u u transpose X bar which is u X bar transpose times u X bar which is basically norm of u X bar square so the moment you have any matrix P which is u u transpose then P automatically becomes a this becomes a PSD matrix P automatically becomes a P estimate which implies that this 2 by x2 cube times u bar u bar transpose this is automatically this is a PSD matrix already so we can assume that X 2 is greater than or equal to 0 I think one can restrict this domain such that X 1 X 2 greater than equal to 0 so what we have is this quantity 2 by X 2 cube this is greater than equal to 0 this is u bar u bar transpose is a positive semi definite matrix implies so this implies let me just write it clearly this is basically 2 by X 2 cube times u bar u bar transpose so this is greater than equal to 0 this is positive semi definite ok the squiggly or this curved greater than equal to so implies Delta square F yes this is positive semi definite implies implies X 1 square by X 2 a simple function function of the vector X bar two-dimensional vector X 1 X 2 this is convex okay since the Hessian is so we have evaluated the Hessian of this function and demonstrated that the Hessian is a positive semi-definite meter therefore the function is a convex function ok let us proceed on to look at another example and we look at an interesting practical application of this convexity of a function of a vector ok so what I want to look at now is to develop a practical application of this and in fact in this practical application what we want to look at we want to look at I want to look at a MIMO a multiple input multiple output wireless communication system consider practical application with my mobilis system where my mo some of you might already be familiar the concept of my mo is basically you have this is stands for multiple input multiple-output okay so this implies that you have multiple transmit and multiple receive antennas and having such a multiple-input multiple-output system significantly increases the communication rate or the data rate of a wireless communication system so it's considered to be one of the revolutionary technologies in wireless communication and if you look at this MIMO communication system you have as I already said you you have a system that is you have a transmitter okay you have a transmitter and you have many possible channels between each transmitter so this is your T transmit antennas or let us represent this by small T transmit small T transmit antennas and this is our receive antennas our receive antennas and therefore what we can do is we can transmit the symbols X 1 X 2 X T from the T transmit antennas X 1 X 2 up to XT and we can receive the symbols Y 1 y 2 yr so we can write this as y bar equals the received vector corresponding to the symbols y 1 y 2 up to yr this is the received vector or you can say this is the vector of received symbols and for that matter if you look at X bar that is X 1 X 2 X T because you are transmitting T symbols one from each transmit antenna so this is your transmit this is your transmit vector and our model for this MIMO system is therefore given as y bar equals H X bar plus n bar where we know this Y bar this is an R cross one receive vector this is a T cross one transmit vector which implies that this must be rien R cross T matrix H and this is known as the MIMO channel matrix so this R cross T matrix H which are where R is the number of receive antennas T is the number of transmit antennas this is your R cross this is your R cross T matrixes this is also the MIMO channel matrix multiple-input multiple-output channel matrix of course this n bar this is an R dimensional noise vector you can see this is an R cross one ok noise vector so this is the noise vector this also you can say additive noise vector this is an additive noise vector because it's adding two HX bar okay and if you look at this channel matrix H that has the following structure that has H 1 1 H 1 to H 2 1 H 1 and so h21 h21 H 1 to H R 1 H 1 T this is H 2 2 and this is finally H R T so this is an R cross T matrix our equals number of rows which is the number of receive antennas t equals number of columns that is the number of transmit antennas okay and if you look at H I J so each of these quantities correct each of these quantities these are basically your fading channel coefficients okay so these are fading wireless there because the wireless channel is a fading channel so these are fading these are fading channel coefficient in particular if you look at this quantity H I J this is the channel coefficient between the eyath receive antenna and JH transmit antenna this is the channel coefficient between the eyuth transmitted between the ayats receive I'm sorry I receive and jaea transmit antenna okay and now our challenge is the problem that we want to address is basically which we will continue in the subsequent module is that remember at the receiver we have this vector Y bar correct which we know at the receiver all right now with this received vector Y bar one has two deep decode or one has to estimate the vector X bar that has been transmitted all right so that is a problem of communication and a communication system you transmit some symbols these symbols have to be recovered at the receiver correct so in a MIMO system you have this received vector Y bar but you don't know at the receiver you don't know that record its vector X bar that has been transmitted which comprises the T transmitted symbols X 1 X 2 X T correct so one has to estimate this transmitted vector X bar and that forms the problem or the problem of mime or receiver design ok so one has to design a suitable algorithm or a technique for the MIMO is a receiver which recovers this transmitted vector or the transmit vector X bar so what we want to look at is this problem that is given Y bar given the vector Y bar how to estimate where remember x-bar comprises of your vector of T transmitted symbols okay so this vector comprises of the T transmitted symbols okay so how do you detect this vector X bar that comprises of the T transmitted symbols how do you recover the T transmitted symbols from the given vector y bar at the receiver all right so that forms the problem of my mo receiver design all right which we will look at in a subsequent module the problem of MIMO receiver design and its relation to convex optimization the problem of MIMO receiver design and its relation to convex optimization optimization is something that we want to explore in a subsequent model all right thank you very much [Music] [Music]