noc18-ee31-Lec 49 - Applied Optimization | Stochastic Linear Program, Gaussian Uncertainty

[Music] [Music] hello welcome to another module in this massive open online course so we are looking at different kinds of we are looking at convex optimization problems and in most specifically we are looking at this specific class of convex optimization problems which is basically linear programs okay we have looked at linear programs and also demonstrated the practical application of a linear program all right and in this mode you let us start looking at our variation of that or an extension of it known as the robust linear program all right so what we want to look at in this module is another interesting extension of a linear program and which is also very useful practically that is robust robust linear program and linear program if you remember can be formulated as follows that is we want to minimize a bar transpose X bar this is our objective function which is an affine objective and this is subject to the constraint of again an affine constraints that is C bar transpose I X bar less than or equal to di or I 1 and now however while formulating this linear program you assume this constraint that is the C bar is that is if you look at these vectors okay we have assumed these to be perfectly known now remember these can be perfectly know now remember these C bar is this vector C bar I which characterize this problem they depend on the problem right for instance in our base station cooperation there they are basically that the power gains all right the gains between the base stations and the various use of solid so these have to be estimated in practice for any particular problem which means naturally that there is going to be a certain level of uncertain be a certain level of uncertainty in this so what happens in as we've seen many times before and practical scenarios and this is especially that's what we've said it's very it has a lot of practical relevance there can be uncertainty in this C bar alright so and there can be various levels of uncertainty know there can be various models for this now one interesting way or one practically useful model for such scenarios where is uncertain it is e bar I is to assume that these C bar eyes are random in nature okay alright and this also gives rise to a stochastic linear program a stochastic version of this linear program so one can assume that the C bar is random in nature in particular you can assume that these C bar eyes are Gaussian these are Gaussian random vectors with their nominal value which is their mean mean equals mu bar I and the covariance that is if you look at this C bar eyes see bar I minus mu bar I see bar I minus mu bar I transpose this is equal to RI this is the covariance matrix you can say this is the covariance matrix so and remember the covariance characterizes the spread around the mean alright so this is a vector I am simplifying this for a scalar for instance if you have a Gaussian alright that this is your mean mu I and as the variance decreases as the variance decreases it becomes more and more concentrated on the mean alright so C bar I is a Gaussian random vector the nominal value or let us say the estimated value of this is mu bar I that is the vector and the covariance matrix characterizes the spread around that if the covariance matrix let's say the eigenvalues or if the covariances of these different elements of C bar I are low it means that it is very close to the mean if the variances are large it means that it has a large spread around the mean okay so basically that characterizes this problem and of course when the covariance matrix tends to 0 or becomes very close to 0 it reduces the previous version because in that case C bar I becomes equal to MU bar I that it's it is equal to the mean mu bar I with probability 1 and it again reduces to the deterministic linear linear program that we have seen before okay so now for this stochastic linear program or this you know linear program in which the C bar eyes are random how do you formulate there now if you look at the constraints let's go back and take a look at the constraint the constraint is C bar transpose I into X bar is less than or equal to di now if you look at this C bar is random in fact C bar is Gaussian X bar is a vector correct now therefore C bar now C bar C bar I transpose X bar this is also random because C bar is a random vector so this implies this is random okay and in fact you realize something interesting that this is we can also say that this is Gaussian reason being si bar I is a Gaussian random vector C bar I transpose X bar is a linear combination of the components of this vector C bar I we knew linearly combined Gaussian random variables you get another Gaussian atom therefore C bar there's a linear transformation of Gaussian random variables yields another Gaussian random variable therefore C bar I transpose X bar is a Gaussian random variable in fact all right and what you can see more interestingly since this is C bar I transpose X bar is Gaussian random variable C bar I transpose X bar X bar this belongs or this can lie can take any value can take any value in minus infinity to infinity that is the other interesting thing so remember C bar I transpose X bar previously was a deterministic on it now it's random so it can take any value between minus infinity and infinity which means that it need not be less than or equal to D I for some values that is there can always exist some random some values of this vector C bar I where this exceeds di one cannot because of the random nature of this constraint one cannot hope that this constraint is always satisfied in the optimization problem all right so because this is a random need not or cannot be satisfied all the time because it is varying randomly cannot be satisfied this cannot be satisfied all it cannot be satisfied all that which means this only holds with a certain probability I can expect this to hold so this holds only with some probability so only holds [Music] [Music] this only hold with some probability let's say the probability is ETA so what ETA I what we mean by that or let's say this is beta I so what or etai let's say the probability that C bar transpose I X bar less than or equal to D I has to be greater than or equal to ETA which means the what we are saying is very interesting the probability with which the constraint holds that this you can only talk in terms of probability so this constraint holds with probability etai that is what we are saying is this constraint need not hold all the time but it can hold with a very high probability that is the probability with which this constraint holds is has to be greater than equal to ETA for instance ETA I can be let us say 95% just take a simple example which means that this constraint has to hold 95% of the time okay so each I can be let us make it 0.95 ok 95% or 0.95 which means this constraint has to hold which means this constraint which means this constraint holds 95% of the time okay and therefore now I can modify this linear program no I can modify this optimization problem I can write this as minimize a bar transpose X bar plus be subject to the constraint that the probability C bar Trang I transpose X bar less than or equal to D I greater than or equal to it I okay I equals 1/2 of 2 so this is your modified stochastic you can call this as robust LP or you can call it as a stochastic stochastic because the constraint is random in nature or holds with a certain probability you can also call this as robust LP because you are ensuring that you're taking the uncertainty in Susi bar I uncertainty in C bar I in to occur let us modify this problem further now let us look at this quantity C bar I transpose X bar if you look at this quantity C bar I transpose X bar we have already said that this quantity this is a Gaussian random variable now let us find the mean and variance of this Gaussian random variable we have expected the mean is simple expected value of C bar I transpose X bar this is expected value of C bar I transpose times X bar or which is equal to expected value of C bar is mu bar I so this is mu bar I transpose X bar which is equal to X bar transpose so this is the mean this is the mean now what is the variance of this what is the variance the variance is the expected value of the random variable that is C Bar I transpose X but or you can write it as X bar transpose C bar a so X bar transpose C bar I minus its mean which is X bar transpose mu bar I whole square now I can write this as expected value of x bar transpose C bar I minus mu bar I whole square now this is a scalar quantity so I can write this as expected a sole I can write it as the quantity into itself or quantity into its transpose because this is a scalar quantity X bar transpose C bar I minus mu bar I this is a scalar quantity or basically it is simply a number so this is simply a number so this is therefore equal to expected value of x bar transpose C bar I minus mu bar I times its transpose which is C bar I minus mu bar I transpose times X bar which is basically expected value off I can take the X bar outside so this is X bar transpose and now you have something interesting expected value of C bar I minus mu bar I times C bar I - noubar i transpose into X bar and this is equal to X bar transpose RI into X bar where RI you can see this is the covariance that is expected value of Z bar I minus mu bar I - C bar I minus mu bar I transpose so basically the variance of this C bar I transpose X bar or X bar transpose C bar I this is X bar transpose RI into X bar that is the variance of this quantity okay and therefore and therefore now what we have seen is X bar transpose C bar I this is Gaussian with mean X bar transpose mu bar I and variance X bar transpose RI into X bar okay and now let us find remember our constraint involves a probability so now let us find what is the probability that X bar transpose mu bar I is less than or equal to so therefore X bar transpose C bar is Gaussian alright now let us go back to the constraint and find what is the probability that this let us simplify the probability that X bar transpose C bar is indeed less than equal to di now if you look at that the probability robot X bar transpose C bar I less than equal to di this is equal to the probability now X bar transpose let me subtract the mean X bar transpose C bar I minus X bar transpose mu bar I less than equal to di minus X bar transpose mu bar I alright I am subtracting the mean X bar transpose mu bar I now I am going to denote divided by the variance remember the divided by the square root of the variance so this is the variance and standard deviation you can think of this as Sigma square so Sigma was standard deviation equal square root of x bar transpose RI into X bar and so therefore this is equal to the probability divided both sides by the standard deviation this is equal to the probability that X bar transpose C bar I minus X bar transpose mu bar I divided by square root of x bar transpose RI X bar is less than or equal to di minus X bar transpose mu bar I divided by square root of x bar transpose RI into X and now if you look at this if you look at this quantity what we have done is from a Gaussian random variable we have basically subtracted the mean and divided by the standard deviation so that gives us a 0 mean unit variance Gaussian random variable which is nothing but the standard normal random error so this gives us this manipulation has given us the standard normal what we call the standard normal our way that is Gaussian random variable mean equal to 0 now the probability that this is less than equal to this is 1 minus the probability that this is greater than equal to this so this is equal to 1 minus the probability that this quantity X bar transpose C bar I minus X bar transpose Y bar I divided by square root X bar transpose RI X bar is greater than or equal to X bar transpose to be bar I divided by X bar transpose RI into X bar and now we have probability that the standard row the standard normal random variable Gaussian anomaly will mean 0 variance 1 is greater than equal to some threshold that is given by the cue function alright so this quantity is nothing but the tail probability of the standard normal which is equal to Q of D minus X bar or di minus X bar transpose u bar I divided by under root X bar transpose all right X bar very earlier and this quantity is equal to 1 minus that 1 minus the tail problem and therefore the probability and that is what we are saying right this is the tail probability that is a probability standard normal if you remember q of x equals probability X greater than or equal to X where X is your standard normal that is Gaussian random variable with mean zero and variance unity and we need this probability to be greater than or equal to ETA so this means this quantity is greater than equal to it so therefore what we have is if you look at it what we have is the following thing the probability X bar transpose C bar I less than equal to di greater than equal to ETA this implies that Q of di minus X bar transpose mu I divided by X bar transpose R I into X bar square root this has to be or 1 minus Q I am sorry 1 minus Q has to be greater than or equal to ETA okay and this implies that Q of X bar transpose mu I divided by square root X bar transpose R into X bar is less than or equal to 1 minus ETA now the q function is a decreasing function implies this implies di minus x-bar t transpose mu bar I sorry this is has to be all mu bar I / mu bar i / X bar transpose rx what this has to be greater than equal to true inverse 1 minus ETA okay since the cue function is a decreasing function the inequality gets reversed so if this has to be less than equal to this that implies that this quantity has to be greater than equal to Q inverse of 1 minus 0 and note that if ETA is greater than 0.5 that is a reliability with which this has to be hold is greater than 50% then this Q inverse 1 minus theta this is greater than equal to 0 so this quantity is greater than equal to 0 if ETA is greater than equal to point okay let me just simplify this now further into something that is interesting remember RI is a covariance matrix so RI is a positive semi definite matrix so I can factor it as alright tilde all right tilde transpose this implies X bar X bar transpose RI X bar equals x X bar transpose all right tilde all right tilde transpose X bar and if you look at this this is nothing but all right tilde X bar norm Square and therefore square root of x bar transpose are X bar equals more right tilde transpose X bar and therefore the condition above this implies that di minus X bar transpose mu bar I over square root of x bar transpose RI X bar which is nothing but nor right tilde transpose X bar is greater than equal to Q inverse 1 minus ETA which basically implies that again q nurse 1 minus ETA is positive so you can write this as write tilde transpose X bar is less than or equal to di minus X bar transpose mu bar I / / q inverse of 1 minus ETA okay and now if you look at this you will observe something interesting you have here an on and here you have something that is a fine so you have norm of vector X bar something all right norm is less than or equal to an affine function of X bar remember this represents a cone so this is a conic constraint okay so this represents a cone and this is equal to a conic so this will become a cone program so this implies what with robust linear program that we are talking about this becomes a cone program implies or the stochastic LP you can call it the stochastic LP equals a cone program does conic constraints okay and therefore now you can formulate this stochastic LP as follows that is basically minimize a bar transpose X bar plus B subject to the constraint that your nor RI tilde transpose X bar is less than or equal to di minus X bar transpose mu bar I universe 1 minus theta4 I equal to 1 to 12 in fact this can be ETA I it does not really matter this can be ETA I I am just going to correct this over all places it can be a common ETA or it can be Gita I okay you might want different reliabilities for different constraints alright so this can be there you go so it is ETA I and you can correct it everywhere to ETA I and this has to hold for I equal to 1 to up to L so this is your linear program you can think of this as a robust version for or the scenario when these vectors see bar I are at random in nature all right so that's another interesting flavor in fact we can say this is a practical flavor of the traditional linear program the linear program itself has several practical applications this in that sense it makes it more practical or immensely enhances its utility by making it more relevant because several in several scenarios these coefficients C bar might not be known might not meet on accurately or might be not only with a certain degree of accuracy in particular when they are random and they gave me modeled as Gaussian random variables one can use this interesting framework to formulate the equivalent either stochastic or you can call it term with the stochastic version of the robust stochastic LP or robust LP or the stochastic version of the robust it is stop here thank you very much [Music] [Music]