Lecture 10 - Equivalent LP's

[Music] [Music] so uh again uh uh there is no very robust meaning of converting well LP to other uh our uh basic principle would be uh uh I don't want to say same solution but uh achieves the same purpose okay and uh most of the time this purpose will be achieved so converting Val let's say you want to convert a to b or you know these directions and this will be done so this is a map or a function or a process which converts any way can be converted into so when you look at this uh you should at least be convinced that if I can do this then clearly instead of solving a I can solve b instead of solving B I can solve a right so this is probably the simplest way in which we can Define two things are equivalent but this is not General General enough it turns out most of the time what we need is we can convert optimal solution and the other feasible Solutions even if you cannot convert to them I don't care okay and again instead of same it could be uh well behaved function so instead of the output value P you can get p + 1 or 2 p or p² and in all these cases even though it's not the same objective value you can get the previous object value back right so this is in some sense the meaning of converting one LP into another okay and let me just show you to by examples which will make this thing clear okay yeah so remember uh I should write down the standard program so you can have constraints like and the standard program is okay okay this is not exhaustive uh in the sense that you can also ask how do you convert equality into inequalities all that but let's just see this direction others are not very difficult okay so first do I care about min max how do I convert maximum into Min just yes just change C to minus C okay so then this is fine okay how do I convert AI transpose X less than equal to bi to equal to bi no no but you are putting an extra constraint that might not be therei sorry a dum variable yes what you can do is you can say this let's now let's say this is a jth constraint equal to bi okay so is it so given any solution here I can obviously convert into solution here whatever is left I will put it in SJ given any solution here it automatically gives me the same solution here right so here the equivalence is pretty tight right you can go back and forth easily this is fine and obviously uh this is either way right so AI transpose so I've have taken care of both sides right what else can be different in the standard function it could have strict inequalities what do I do with strict inequalities s sorry s you haven't changed the thing right it is still now but here there is problem right so how will you change SJ greater than equal to Z greater than Z to S greater than equal to Z we don't know a way okay and this so one thing would be that you know we allow this kind of constr strains to but that makes the mathematics of linear programming much tougher okay so what we do is just approximate them by putting the equality constraint there so we will just switch this to this to this again vares the same yeah if you want to convert to equality then so once we have converted to this then we can use the same rout okay what else could be different between these two programs compress all the AI into matx sorry have to compress all the that you can do but mathematically what have we not seen what is left notice that when I write this as a standard linear program this greater than equal to condition is on the entire thing you can have a linear program where your variable is just real like the coefficients in the approximate degree case then what do you do how do you deal with unconstrained inters it as very nice yes so the idea is if you have an unconstant variable let's say this is an R you can switch this to okay clear so now given these small tips and tricks it turns out we can always assume that our linear programs are in the in this fashion correct now in some circumstances this is a standard form which we want to deal with this is very helpful it turns out some people like that standard form do you agree that this is good enough what do we have to do to prove that this is also a standard form right so then I want to change this into this kind of a linear program C transpose X is fine X great than equal to Z right I can change so what is going to be my new a prime and B Prime in terms of A and B write it V yes yes thank you that's a good point uh yeah it could have different meanings but for us X greater than equal to 1 y means for every similarly equality similarly less than equal to okay so if there were M constraints and N variables what will be the dimension of like okay uh how long will a prime be right it is going to have 2 m+ N constraints right and what will be the things here here okay so when I do this with this a prime and B Prime I get generally when we are solving things this standard form is nice when we talking about convexity and all this standard form is nice okay so don't get hung up on this is the standard form okay the important point is as required we can simplify and we can just worry about one particular kind of standard form that makes our life easy suppose you are given these sets from 2 The Power n buan strings okay these are not elements sorry these are subsets from 01 to the N clear okay and you are given this LP so the variables so constraints are over these this is the linear program given to you okay there are some M subsets you want to maximize ux plus VX such that ux - VX is less than mod of CI what is the value of this linear program what can you say about this linear program this is what you want to solve can you utilize those tips and tricks or convert it into into an equivalent LP this is a hint can you convert it into an equivalent LP and suddenly the answer will pop out uh anyone knows the answer to this kind of okay good anyone else yes very good so two people see it let me just write in a different way and then everyone will see it okay okay is the thing to notice here is we have this substitution given ux and VX I can get ZX and YX given ZX and YX I can get ux and VX right so then this change of variables is fine I'm only converting one LP into an another equivalent LP but now if you look at this LP the thing which you are maximizing is different from the thing at the constraint right so that means you can get the value of z x as high as possible it doesn't matter so as pointed out this is right so this is kind of these tips and tricks even though they're not very uh ingenious they're not very difficult but they are really really useful I'm not going to devote much more time to it you will see exercises you will see like most of the applications you have to do these tips and tricks to make your LP look nicer okay what I'm trying to emphasize here is that even though these are simple tricks you shouldn't Overlook them and you should understand what is required once again the bigger philosophy is I can solve this if I can solve this but then most of the time it will be achieved by saying given a solution here I can convert it into a solution here and if you want it to be equivalent given a solution here you can convert into a solution here okay keeping the objective value in a nice fashion probably a nice monotonic function or something this allows us to change go between different linear programs and suddenly your knowledge about the linear program increases right so I think you will agree that some people saw this to be unbounded but this makes it suddenly very very clear this is unbounded right so this is part of our tool set when we deal with linear programs and uh just to take the last example uh I talked to you about dual right and what was the idea you are given a linear program there is something called a dual which has which is very nicely related to your original optimization program okay they obviously have the same value not just that they're very deeply related and we will explore this but before the Dual uh but uh before we go into that uh I I want to talk about the Dual of the approximate degree problem you remember we did the linear program what was the linear program right so in general whenever we see a linear program we can always ask what is its dual and understanding the Dual gives us lot of import uh lot of information about understanding the Primal that you will see throughout this course but what I want to do is I will in this case because we are not familiar about how to take the Dual I will give you the Dual and I want you to simplify it okay so you remember we had a function which we wanted to approximate this was correlation so this is the monomial x i1 x I2 x i k whatever is in the S right and this is equal to Z clear uh this is a linear program what it represents everything is at this point not clear right uh there are what are the variables here S1 X and S 2x okay so there are two * 2 the^ N variables and then these are the constraints given how can you simplify this and uh I think what you are also given is uh yeah now if you want to simplify it uh let me tell you uh we don't have much time but one thing would be I see the s1x - s 2x many many places right so let's just replace it by a single variable so this is just to tell you what kind of tricks you can play in this equivalence things so I will just say this okay now at this point it seems like I have made more variables than what I had right I had two the two * to the^ n variables now I have three * to the^ n variables and the idea should be we should be able to write this in terms of s one way is that I Define s 1X Plus s 2x some other variable but that doesn't help I will give you one more minutes we don't have much time but can you think of some simplification here see uh what you can do is you can think of s1x and S2X uh we interested in their difference right can we make sure that at least one of them is zero Okay so let's say uh my s1x and S2X I'm just talking about 1 x suppose this one was the case okay I make it 3 - 0 okay how does it help me my s1x - s 2x Remains the Same and this thing is now I have much more control over this what I can do is remember here I want to maximize right so if I do this then this thing becomes smaller than one I can scale these things and get a better value here this is not easy this is probably one of the more difficult uh conversions but okay the and and there's possible because this is an optimization problem this you might not have seen an equivalence what we were doing was equivalence YX equal to Z x but since we are optimizing here we're only interested in the optimal solution what we can say is if these were the values it's much better for me to consider it as 3 - 0 and then you know that sum total here was five here it is three I will just scale everything by 5x3 so this allows me so or um yeah even this is equal this this constraints but this allows me to have this satisfied but increase the objective value Okay so and if that is the case uh you can actually replace it by X so you you get a very easy program in the end again this is not a written as a linear program but it's easy to understand what it means and then so I think I have not explained this properly uh what I want is you think about this think about this equivalence otherwise we will do it again in the next class but this is a very non-trivial equivalence okay so take it as a homework see if you can convert from here to [Music] [Music] [Music] here