Well, let me -- you can turn off all amplification in here. So yeah, so itfs still -- you still have amplification on in here so you can -- oh, well, wefll let them figure that out. Letfs see, couple of announcements. Itfs actually kind of irritating, frankly. I wonder if we can just cut that off? Oh, the advertisement went away, thatfs good.

All right, Ifll let them figure out how to turn off the amplification in a room thatfs got, like, a depth of 15 feet. So yes! No? All right. Anyway, Ifll let them worry about it. Okay, first just a couple of announcements to -- I keep getting hopefully. What do you think? Are we there? Getting better. Itfs funny. Youfd think you could just turn it off.

But anyway, all right, okay. So a couple of announcements is, as you know, the final project reports are due tomorrow. So thatfs one deadline. The other is on Monday; I think itfs been agreed. Wefre gonna have our poster session.

We havenft fixed the time exactly yet but wefre thinking of something like 5:00-7:00 and wefre gonna figure out about getting some food. So wefll -- but we havenft announced that. Thatfll be on the website and all that kind of stuff when we figure everything out.

And therefs already been some questions about whatfs the format of the posters and we donft know. So some people are gonna go ahead and do the fancy thing and make big posters which youfre more than welcome to do but you donft have to. You can just print out 12 black and white slides, or whatever, and, like, you know, tack them to the poster board. And I donft remember what the size of the poster board is but maybe thatfll also be forthcoming on the website or maybe be an announcement or something like that.

So the format, which is 12 slides, is -- thatfs fixed and Ifve said it many times but, you know, please use our template. Youfre welcome not to, you donft have to, but then you better have better taste than we do. So, I mean, even -- and therefs certain things you just canft do because itfs not acceptable and itfs amateurish and stuff like that. And you all know what Ifm talking about.

So, okay, so wefre gonna finish up our absolutely last topic which is branch and bound methods. These are methods for global optimization. So in global optimization you have a non-convex problem but youfre going to give up -- youfre not gonna give up a globalness. Thatfs not a word, I just made it up.

But youfre not gonna give up globalness -- globality? Youfre gonna give up neither globalness nor globality but you are gonna give up speed. So whatfs gonna happen is these are gonna be methods that are slow but they donft lie. They will produce a -- at any point you can stop them and exactly like a convex optimization method they will have a lower bound and they will have an upper bound.

And theyfre not approximate, they are correct and they terminate when the lower -- when the upper bound minus the lower bound gets less than some tolerance and thatfs global. So this is a huge field. You can take entire classes on it. So this is just your taste of global optimization and itfs basically just to give you the rough idea of how these things work.

There are other methods but theyfre all kind of related to this and then bits and pieces get very sophisticated. And even here Ifll show you where therefs lots of room for personal expression in these methods.

So, okay, so last time we started talking about this and the basic idea is this. Itfs gonna rely on two methods in your problem. Youfre gonna somehow -- youfre gonna parse up the region, you know what, therefs actually amplification still on in here but itfs cool. Actually itfs not, but I mean, it canft be that hard to turn off the amplification.

Okay, so youfre gonna have two methods which over a region of the feasible set given some description of a reason of a subset of the feasible set will compute a lower bound and an upper bound.

The lower bound, of course, is gonna be -- thatfs gonna be the sophisticated one. Well, it can be sophisticated. Thatfll often be computed a Lagrange relaxation, by a duality, something like that. Oh, dear. Ah, the pleasures of -- wow, now itfs -- I used to -- well, a long time ago I did rock and roll sound so I know about this. These are bad monitors anyway.

So, okay, so the upper bound can also -- can be done by a variety of methods ranging from extremely stupid and simple, for example, herefs an upper bound. If your region is a rectangle you simply go to the middle of the center of the rectangle and you evaluate the objective there and the constraint functions. If that point is infeasible, you return the upper bound plus infinity, which is valid but not that useful. If it is feasible you turn the objective value at the center of the interval as the upper bound.

So thatfs, you know, they canft -- it canft get any simpler than that. Itfs just evaluating the function at the center. You can do other things, too. Like, you can run a local optimization method starting from there you can do whatever you like to get a better point. Anything will work.

Matter of fact, these can have a huge effect on a real method and would be if you actually implemented some of this you would do this. Wefre not even asking you to do this on your last homework problem.

Okay, so this is the basic idea is youfre gonna partition the feasible set into convex sets and then find lower and upper bounds for each. So thatfs the idea -- and wefll quit. And wefll actually look at two specific examples of the general idea and once youfve seen these two, which are a bit different from each other, I mean, actually theyfre kind of the same, youfll figure out how to do this in much more general -- in the general case because itfs really the ideas and not the details that matter here.

So herefs the way itfs gonna work. First wefll do -- wefll just do simply unconstrained, non-convex minimization. Actually itfs silly; it could be constrained because you could build right into F the constraints by assigning F the value plus infinity outside the feasible set.

Okay, so wefre gonna optimize over this m-dimensional rectangle to some prescribed accuracy epsilon. Itfs gonna work like this, wefre gonna have Q methods a -- well, sorry, Ifll get to the Q methods in a minute but wefre gonna define phi min of Q as the global optimum of F, the global minimum of F over the rectangle.

So wefre just looking to compute F*, thatfs what wefre actually gonna compute here. Okay, so wefre gonna have two upper and lower bound functions. So itfs gonna be a lower bound function and upper bound function. They must be above and below this minimum value and they have to be -- one attribute they have to have is they have to be tight as the size of the rectangles shrink.

That basically even the stupidest method would satisfy this, so, the simplest lower bound, I mean, extremely bad would be the following. The simplest upper bound is the value of F at the middle of the rectangle and the simplest lower bound by far is to subtract from that number a Lipschitz constant, the diameter of the rectangle or the radius of the -- diameter of the rectangle divided by 2 multiplied by a known Lipschitz constant on F. That does the trick.

Now that stupid one has the property that this -- has this property that if a rectangle gets small enough then the gap between these two is less than your epsilon. By the way, you could use that as your safety backup lower bound, meaning that you can run a sophisticated lower bound based on convex optimization or something like that and then use this one if itfs better. And that means that it inherits the proof in that case. Such a method would inherit -- such an algorithm would inherit the proof and so you would be safe from the proof police in that case.

So if there was a raid and someone said, gCan you absolutely prove your method works?h Youfd point to a line of code and say, gYes, it does.h So thatfs really the only reason you would do that, by the way, would safety from them.

Okay, all right, so the idea is that these should be easy to -- they should be cheap to compute because, of course, they could just be equal to this and thatfs -- but then theyfre impossible to compute. So, in fact, the tradeoff here is gonna be something like this. You want cheaply computable -- you want bounds that are cheap to compute but good.

Good means merely that they are close enough to each other in the instances youfll look at that branch and bound will run quickly. So thatfs sort of the key to everything here is getting cheaply computable bounds.

Okay, so letfs look at the branch and bound algorithm, it works like this, basic one in this case goes like this. You -- I call my lower bound method on the initial rectangle and I call my upper bound method and I call these U1 and L1.

Obviously I can terminate if U1 minus L1 is less than epsilon because then Ifm done and Ifm absolutely done. By the way, this method can also return a point that achieves this upper bound. So -- if you wanted to say, gOkay, Ifm terminating and I want to return an X then it will be the job of this thing to return the bound.h

By the way, itfs the job of the lower bound to return a certificate proving it. So if you want to make the algorithm sort of really formal and correct and all that when it quits it should quit returning two things, a certificate that the upper bound -- that this value -- that this upper bound is actually truly and upper bound.

Best certificate being to demonstrate a point which has that objective value and which is feasible and a lower bound. Wefre gonna find out what the lower bound looks like in a minute. Itfs much more sophisticated than merely a dual feasible point which is what you have in convex optimization.

Okay, so thatfs -- wefll see what this is in a minute. Okay, now if this does not hold -- so in other words, your upper and lower bounds are not less than your tolerance what youfre gonna do is youfre gonna split the rectangle into two subrectangles.

Okay? So -- and youfre gonna do that by choosing a variable to split on. So a rectangle, of course, is something that looks between -- itfs the rectangle is described by two vectors, an L and a U, a lower and an upper bound. You choose a component to split on and then in fact in more fancy versions you could decide how you want to split it.

Do you want to split it evenly or not evenly and this is where all the personal expression goes into these methods. So if you had some clever method where there was any reason you didnft want to split it evenly that would be fine.

But youfll partition it like this and then youfll call the lower bound and upper bound methods on these children. And, in fact, this is -- let me just draw a picture here to show how this works in R2. I mean, itfs silly in R2 but herefs the point.

So herefs your initial rectangle like this and you evaluate the upper and lower bound and if theyfre not within tolerance you split it. And you could either split it along these variable and youfre gonna partition two rectangles, you could split it along X1 or along X2 like this. And letfs say you decide to split it along X1 you can further decide how you want to split it. But here it doesnft say, it doesnft specify so therefs a splitting like that.

Now what you do is you calculate the lower bound here and the upper bound here and let me just do a -- Ifm gonna fill in some numbers just so we can see how this looks. And, in fact, if I do this example youfll kind of understand absolutely everything about this. So letfs start with this one. I call the upper bound and I get ten, I call the lower bound and I get six.

So thatfs the -- so we know that the optimal value of the function in here is somewhere between six and ten. Thatfs all we know, you donft know anything else. What can you say about the function value like at this point here? What is it?

[Student:][Inaudible].

Itfs bigger than -- well, what do you mean itfs bigger than six and ten?

[Student:]Itfs [inaudible].

Ah-ha, okay. I thought you were gonna say that. It was a trap. I wanted you to say that. Itfs false. Half of it is true. Itfs bigger than six because the minimum I can provide that this six means I can prove that on this rectangle the function never gets smaller than six. Why? Because I have a lower bound on the function of six. Okay?

Whatfs the -- so I can tell you if I pick a point here the function value here is bigger than size. I cannot say itfs less than ten. What can I say though? I can say this, there is a point in here, maybe not that one, but there is a point in here which has a function value of less than or equal to ten, that I can say.

By the way, Ifm skipping, you know, Ifm assuming the [inaudible] and the [inaudible] are achieved in all that. You know, I mean, itfs true anyway, the F is -- letfs make F continuous or whatever. It doesnft matter.

So there is a point and, in fact, it would be the job of the upper bound routine to return that point in case it were challenged. Actually, in case our -- suppose our epsilon were five in which case wefre done. Wefve calculated the global optimum within five it would be the job of -- so there is a point, letfs call it there.

But this doesnft really matter. Okay? So, all right. So now wefre gonna partition -- wefre gonna go like this and Ifm gonna call my lower bound function here and here and my upper bound function. And letfs actually -- if I go through a couple of -- Ifll just ask you some questions and I think then youfll know everything there is.

And let me switch these around so the lower bound comes first. Okay. So here letfs see what would happen -- well, let me ask you a couple questions. Letfs call the lower bound function and letfs suppose it were five here. Any comments? Thatfs the lower bound. Is it a valid lower bound?

[Student:]Itfs a valid lower bound.

Yes, itfs a valid lower bound but --

[Student:]Itfs of no use.

- itfs of no use. And, in fact, if I got five there what could I do with the five? Immediately replace it with --

[Student:]Six.

- six. Okay. So the point is we donft require -- we do not require that the lower bound and upper bound function should return better answers than their parents. But, in fact, we can just quietly copy -- in other words, calculating this lower bound was a complete waste of time if we get five. Everybody got that?

So if you get this -- I could just replace it with six because basically -- and if someone challenged you and says, gHow do you know the function is bigger than six in this whole region?h You say, gLook, I know itfs bigger than six in a bigger region. Therefore itfs bigger than 6 in here.h Okay, good. So thatfs one discussion.

Okay, so letfs suppose itfs seven here and eight is the upper bound. Okay? So any comments? By the way, what if this were 11? Be very careful. So whatfs that?

[Student:][Inaudible].

It could happen. You canft say anything stupid has happened yet but I can now. Right? Letfs look at that. What can you say now? Does it bother you? How much does it bother you? Is it impossible or merely stupid? But which one is it? Are these valid? Could these be valid bounds? Yeah, sure. Okay.

So you can insist on the following, when you call the upper bound method on the children at least one of them is as good as the upper bound in the parent. Everybody got that? The reason is this, the -- in fact, when you call the upper bound on the parent you could ask for which -- for the location of the point that achieved that number then that child -- whichever child contains that point canft have an upper bound thatfs worse.

So this canft be. One of these two can be modified to be 10. Everybody follow? Okay, by the way, itfs just -- once you understand all this you understand everything. I mean, but you actually really have to think about these things because theyfre not obvious.

So, I mean, well, they are obvious. Sorry. Itfs just theyfre confusing but you have to draw this picture and then think about it very carefully.

All right, letfs do one more. Howfs that? Itfs fine. Okay? And now let me ask you, suppose this is what the two children -- so youfve taken the two children, youfve called the lower and upper bound method on both children and theyfve returned these bounds.

Now I want to know whatfs the global lower -- whatfs the new lower bound? What can you say if someone tells you -- asks you, you just -- letfs see, in the first iteration you called both of these methods once each, right? Now youfve done it three times. So youfve got three times the work invested now and the question is, gWhat is the new lower bound -- what do you know how that you didnft know before?h

[Student:] Itfs between seven and nine.

Itfs between seven and nine.

[Student:][Inaudible].

Okay. Hang on, letfs just go very slow. Whatfs the new lower bound?

[Student:]Seven.

Seven. Okay. And the argument -- and thatfs better than it used to be which was six. So originally it was six, meaning that whatever else happened we knew that the minimum had to be bigger than or equal to six. Now we know itfs bigger than seven which is the minimum of these two numbers. Right?

Because in this region we trust these methods. It says that the function value is never smaller than seven here, itfs never smaller than eight here. By the way, do you know which side the minimum is gonna be in?

No, not yet. Wefre getting there, okay? No, you donft know. You still donft know. But your new global lower bound is seven. Whatfs your new global upper bound? Well, it canft be -- well, it could be 12, itfs valid. I started by saying, look, the optimum value is absolutely less than or equal to ten. Now what can I say?

[Student:][Inaudible].

Ten?

[Student:][Inaudible].

Yeah, no, wefve agreed on it could be either side. You know therefs still amplification on? Well, itfs a good way to end a year of --

[Student:][Inaudible].

What? What? What? What? Itfs good now. Okay, great, great. Letfs just -- okay. Yeah, so whatfs the new upper bound?

[Student:]Nine.

Nine. Explain it to me.

[Student:]Therefs a point [inaudible].

Good. Okay. So if I told you, gNo, no, no, no, no, the global low -- you know, no, no, no, no, F* the minimum on the whole thing is 9.5.h Then this thingfs lying. So therefs a point on the left whose value is nine and therefore the global -- so we went from six nine after this iteration to seven nine. So that was our -- thatfs literally the -- so the interval of ignorance was this and it went down to this.

Everybody got this? Okay. So, I mean, these are not complicated you just have to go to a quiet place figure out the mins and the maxes and all the logic. Itfs elementary but as you can see you actually have to think about it for a minute to figure out what it all means.

And let me just do one more thing just for fun. Letfs do this. Thatfs 9.5, okay? Now what can you say now?

[Student:][Inaudible].

What can you say?

[Student:][Inaudible].

The optimal point is on the left side, okay. And what are the new bounds?

[Student:][Inaudible].

Seven and nine. So which is the same we had a moment ago except wefve actually now made an additional statement which is that the optimal solution must or can lie in the left-hand side. Must, right? Okay, and the -- whatfs the argument? Whatfs your argument? How do you argue it?

[Student:]Thatfs the point of the left side that has a value lower than the lower bound on the right.

Yeah. So the point is that there is a point in here which has a value of nine. Every point over here has a value that exceeds 9.5 and therefore this whole thing goes away and wefre back down to -- and now wefve actually learned something at least in terms of the location of it.

And so this is called pruning. Wefre gonna get to all of this but if you understand all these ideas of which is about five or six, theyfre all quite elementary and all that, you understand branch and bound. Thatfs -- basically that picture, thatfs all of it.

So but letfs go over it now. Okay, so herefs what happens. Okay, so youfre gonna split it, youfre gonna update the lower bound so the lower bound is gonna be the following. Itfs going to be the minimum of the lower bound; the new global lower bound is the minimum of the lower boundfs returned by the children.

And the upper bound is also the minimum of the upper bound returned by the children. And by the way if you wanted to also put in the U1 and L1 you could do that as well here. The new -- because you canft -- you could query the children, get two answers back and effect you could have no progress whatsoever towards improving things. Right? None.

Itfs nothing in the semantics of the lower and upper bound methods that requires you to make progress. And so I wonft go back to that example and show how that works.

Okay, you find the partition and repeat steps three and four and let me just ask a couple of -- well, wefll get to that. Okay, so thatfs how this works. Okay, now as I said you can assume without loss of generality that the upper bound is not increasing an LI is non -- is also non-increasing. Okay? So thatfs right.

So -- have I got that right? So as you go down the lower -- the upper bound is gonna go down. By the way it has the option of staying level if you donft get anything better. And LI is -- I want to say that LI is non-decreasing, donft I? I do. Thatfs a typo. LI is non-decreasing. Okay.

So what happens is when you repeat this several times, what you do is you have a binary tree and so let me just show you over here what thatfs gonna look like in this case. So letfs go back to this and letfs suppose now I choose to split this guy and I split it like so and then I split this one and I get that -- something like that. Then what Ifm really developing in this case is a tree, a binary tree. And so it would look something like that.

Let me draw this, Ifll have to make it a very fat tree. So you get something that looks like that and this node corresponds to this original rectangle. This node corresponds to this left rectangle, right? And I could even label this cut as L and R for left and right, okay?

Then this node corresponds to this rectangle which I then split and that happens to be top and bottom. So I can call this Top and Bottom, for example. And then these nodes -- this node corresponds do this rectangle and the bottom corresponds to this rectangle. This one was further split like that and then this would be L and R, okay.

So this partially developed binary tree corresponds to this partition here and let me just make a couple of comments about it. So the leaves of this tree correspond exactly to this set of rectangles, okay. So thatfs what the leaves are. By the way, the non-leaf nodes correspond to rectangles also in here but ones that are further split, right? So thatfs what this thing looks like.

Okay, on every node here Ifve calculated a lower -- every node here Ifve called the lower and the upper bound method. So I have a lower bound in all of these and if you have a lower bound -- if you look at the leaves, right? The leaves constitute a rectangle partition of the original set.

In other words, itfs a set of rectangles whose union gives you the original rectangle and whose intersection has -- intersection of any pair has non-empty interior. Thatfs a rectangular partition. Did I say non-empty? I meant to say empty interior, okay. So thatfs a rectangular partition here. So you have this thing.

Okay, now if the lower bounds on these things were, for example, you know, 5 -- 5.5, you know, 4 and 8 what can you give? What is the lower bound for the entire thing? Whatfs the lower bound on the whole function? I just drew the lower bounds on those nodes.

[Student:][Inaudible].

What is it? What?

[Student:]Eight.

Thatfs the lower -- I want the lower bound on the optimal value of the parent -- the top rectangle.

[Student:][Inaudible].

Whatfs that?

[Student:]Four.

Itfs four. Do you know where it is? Well, not until I draw some upper bound there. If I draw upper bound youfll know where it is. You might, you might not. Every upper bound there could be 20 and that just means itfs weird but, I mean, itfs perfectly valid. Your lower bound is four, okay. And now we can actually describe -- I can tell you exactly what a certificate of the lower bound looks like in a non-convex problem.

If I send a halt message to this process and say, gStop, Ifm done.h Letfs see, you just did one, two, three, four, five, six, seven, you just did -- did an effort of solving seven. Letfs say each lower bound is a convex problem youfve solved. So you just solved seven convex problems, say, gThatfs it. Ifm out of time. I quit.h

It returns a lower bound of four here. And then you say -- then you go back to the method and you say, gProve it.h Right? So how do you prove it? So in a convex problem you prove it by producing a dual certificate. How do you prove the lower -- what data -- what object do you hand back that proves it?

[Student:][Inaudible].

No, therefs no -- this is abstract, therefs no Lipschitz constant, you donft know anything. I mean, itfs an abstract lower bound method.

[Student:][Inaudible].

Therefs no point -- if there a point that achieves it youfre done. If you have a lower bound -- if you know the global optimum is bigger than or equal to four and you have a point whose value is four youfre done.

You donft have a point. The -- you might not even have a feasible point yet. All the upper bounds everywhere could be labeled plus infinity. So how would you prove it? If someone said -- if you said, gI happen to know that the function value in this big rectangle is bigger than four.h Someone would say, gProve it.h How would you do it?

[Student:][Inaudible].

Okay, but so? You have to return a -- you can say, gHere my proof. My proof is this that in this region every point in that region has a function value bigger than five. Every single one in this one has a function value bigger than 5.5. Everything here has a function value bigger than four and everything here has a function value bigger than eight.h

So what you return is you actually return the partition with a lower bound on each one. Everybody -- so thatfs your certificate of proof. So, in fact, when you finish a branch and bound method whatfs -- instead of giving the actual certificate proving your lower bound is actually gonna be a partition of the original space with each element in the partition will have its own lower bound.

And if you want to certify that lower bound you have to go to whoever provided that lower bound and it could be Lipschitz, could be duality, Lagrange. I mean, who knows what it is, right? It could be anything you like, any lower bound method you know.

But that would be the matter of the lower bound method. That particular lower bound method; it could be different lower bounds by the way for each one, right? Yeah?

[Student:]Based on the lower bound with the non-leaf nodes?

Oh, no, I have a lower bound here, too. Yeah, definitely have a lower bound there. Here, Ifll draw it. Itfs 4.5 here, something like that. There. Yeah, letfs put some lower -- and when I did the whole thing I started with three and then this could be also 4.5.

[Student:]You have the lower bound to be 4.5.

In this case? Uh-oh, youfre right, sorry. Ifm doing it the wrong way. Thank you. Sorry. Yeah, I shouldnft make it four. I meant to the other way around. I was working on it. How about 3.8 and youfre gonna have to help me on this -- three -- how about that? That look reasonable?

Yeah, but the way I drew it, it would have been 4.5 and thatfs because wefre -- despite whatever this slide says in the top line wefre actually assuming that the LIfs are increasing because thatfs always a possibility, right? So if you call a lower bound method on a subrectangle and you get a worse lower bound than the parent you just take the parents lower bound. So, okay? Everybody got this? I mean, these are -- itfs very, you know, itfs simple and all that but you actually -- it can easily get confused. Make sense?

[Student:][Inaudible].

Where? Over here? Itfs quite likely. Well, what is it? You donft like it? Oh, you mean this?

[Student:]Okay, about [inaudible].

No, no, thatfs okay. Thatfs cool.

[Student:][Inaudible].

Yeah. Thatfs fine. It means basically that the function value -- so whatfs the problem with it?

[Student:][Inaudible].

There probably is one but -- tell me what you donft like about it. You should all be checking this, by the way, this reflects on you. In fact, it reflects on you more than me because I donft really care.

But imagine what other people will think if they watch this video and they think, gYou gotta watch this.h Itfs like, gTherefs this whole class from Stanford they -- this guy said something so stupid itfs amazing and they just sat there happily.h So itfll reflect on you more than me. I think itfs cool. What do you think? Everybody cool with it? All right. Yeah?

[Student:]What is the lower bound [inaudible] is, like, like solving the same kind of problem but therefs no [inaudible]?

No, no. Itfs totally abstract. This actually -- heterogeneous methods for lower bounds could be being run for each node and totally different. One could be based on a Lipschitz constant; one could be based on Lagrange duality. You could fire up four lower bounding methods on one, you know, for one region and return to the caller the best of them. One could be like an SDP bound; one could be a SDP relaxation, one a Lagrange dual. I mean, it makes no difference.

So, no. And then you have the option if you get a bunch of lower bounds and youfd pick the best one. You can also pick the best one of the calling parent because thatfs also a stupid lower bound, right? Because if you look at a subregion it canft have a lower bound -- well, it could be worse, but itfs just silly than the [inaudible]. So, okay?

So did we reach stationarity? I think wefre cool. Okay, so -- okay. All right. So letfs see -- so this is the basic idea. In fact, all we did was we walked through -- whoops. This, this business here. And then this would go -- this actually now would go recursively through the tree. And so in fact itfs the same as saying itfs the minimum of all of the leaf nodes. Okay?

So to -- by the way to make this algorithm -- to full specify it you need a couple of rules. You need to know things like this, which rectangle do you split? So you have this binary tree -- well, you have a partition and you can split a rectangle so thatfs -- you have to choose which one do you -- so for example, on the next step someone says, gOkay, I give you one more step. You have to split like this guy, you know, one of the leaves here youfre gonna split, so one of the four.

Then when you decide to split a rectangle youfd have to decide to split it like, you know, along which variable? In the 2D case you want to split it either vertically or horizontally but in the M dimensional case which I guess is this, you choose which of the M variables youfre gonna split on. Okay?

And, you know, itfs immediately obvious you can do things like if you had eight processors split could mean you could not divide it in half but divide it into eight sections and send -- and then send the 8 subrectangles or whatever to your eight processors or whatever. So, you know, these are all kind of obvious things.

Okay, so here are some rules -- this is where the personal expression -- this is one of the areas where personal expression comes in is in choosing these things. One is you split rectangle with the smallest lower bound along the longest edge and in half. I mean, thatfs kind of just a default method.

But in any particular application maybe you can think of a better way and you can experiment with some and find that one will work really, really well and stuff like that.

And you can mumble all sorts of idea about justifying this but they are absolutely nothing, youfre just mumbling. I mean, therefs no reason to prefer one of these -- I mean, you can talk about that therefs probably stupid methods but this -- therefs lots of other methods, other splitting rules and things like that that can be justified just as well as this one.

[Student:]So in every example we split one of the leaves?

Yeah.

[Student:]And wefd get new upper and lower bounds on that leaf and probably get them all the way up to the root or no?

Yeah. So letfs see what happens when you split. Letfs choose one and split it. I mean, assuming, you know, that wefre not in -- Ifm already in some big trouble here or whatever.

So in this case if we follow this rule we would take this four here and I would split this four. And so thatfs gonna be this guy, I think, right? And so I split it like that and then it would -- I would develop my tree this way and now my two diagrams have hit each other. So I would get this -- this was 4 and now youfre gonna have to help me make some consistent things here.

So letfs see what would happen. Letfs make it interesting and letfs imagine progress is made in lower bound and I would do that by saying this is 4.5 and I have to be very careful, is that right?

Am I doing it right? Yeah. And then this one could be 4.2. Okay? And if that were my two new lower bounds whatfs the new global lower bound? 4.2. So we just made progress in the lower bound. Okay?

So thatfs how that works. So thatfs -- so the idea -- the rough justification, I mean, this is like a depth-first search or something like that. So the rough justification of this is youfre going after -- pulling the lower bound up as soon as possible. Okay, so thatfs it. Okay, so herefs an example but wefve already done an example so -- yeah?

[Student:]What happens if they return the same lower bound?

No problem, itfs fine. You want me to do it? Here, letfs go over here and do that. Yeah, so the lower bound of what? Like, you want 4.0 and 4.0? Like that? You tell me, what just happened? Tell me, what happened? That can happen.

[Student:][Inaudible] the lower bound [inaudible].

Well, itfs not worse.

[Student:]No, itfs not.

It means you just called those two methods -- how much did you learn?

[Student:]Nothing.

Nothing. At least looking at the lower bounds. In terms of lower bound you made no progress. Itfs fine, no problem. Thatfs perfectly fine. Itfs nothing wrong with that. So thatfs -- yeah, thatfs fine. Thatfs just not a problem. Okay, letfs see. Oh, what if the lower bound had been five on one of those? What would that mean?

[Student:]Just [inaudible]?

Whatfs that?

[Student:]If one of the smaller [inaudible] of five just go back and replace it with 4 again.

Well, you could but you could also just label that leaf. I mean, you can now cross off that node -- that rectangle, and say -- can you? No, you canft.

[Student:][Inaudible].

See?

[Student:]It depends on --

I fooled myself. Okay, all right. All right, scratch that. This would be a good time to turn on some feedback in here, by the way. I could blame it on that. Okay, no donft, please.

Okay, so this is the picture. Okay, so wefve already talked about this -- pruning goes like this. It says that if therefs a rectangle whose lower bound exceeds the upper bound -- the known upper bound across the whole thing then it can be marked -- it can be pruned.

And that means you can sort of put an X -- well, it means lots of things. It means actually everything you can now prove you know for sure that the solution is not in that point. And that -- sorry, in that rectangle. Okay?

And that can actually happen while youfre running and that would allow you to free memory, for example. Actually it would have -- if youfre using -- if youfre splitting on the lowest lower bound it -- youfll never split that rectangle anyway because itfs got a high lower bound. So youfll never split it. Youfll be splitting others.

So, in fact, it doesnft change the algorithm in the slightest. What it does do is allows you to free memory. So what would happen is if all of a sudden a point were discovered with value -- uh-oh, now I have to be super careful here.

If I -- suppose the -- these are all lower bounds, I havenft talked about upper bound. Letfs suppose that in this set I found a point with upper bound 4.2. Now letfs be super careful. By the way whatfs our global lower and upper bound at that point?

I mean, itfs at least as good as 4, 4.2. Right? Because I have a point with value 4.2, itfs in -- left, right, thatfs top -- itfs in this set, itfs in this rectangle but -- and I know that across the whole thing the bound is 4.0, okay. Now what can I -- now letfs work out what I can conclude. You do this, too. I did this as the examples, not prepared and these things are tricky. So help me. Tell me, what can I conclude?

[Student:]You [inaudible].

I can get rid of what?

[Student:]The rectangle.

I can get rid of which one?

[Student:]The left one.

This one here?

[Student:]Yeah.

Absolutely. So it is now known absolutely certainly that the global solution does not lie in here. So this one is pruned officially.

[Student:][Inaudible].

This one is pruned. Thatfs gone. This one is now officially gone. And so that means, letfs see, youfre not here, thatfs top, youfre definitely not here, thatfs - is it this one?

[Student:]Right.

Like that. And that says that at this point still in the running are these two, okay. Everybody got this? Now actually, by the way, you can even go up a tree farther and prune something below that. So, by the way, this is not gonna change the iterations, especially if youfre going after the lowest lower bound first.

Itfs not - it wonft - because you donft choose things with high lower bounds. What it will allow to do is call free on a bunch of these and just free the memory. It also, by the way, if somebody stops and says, gWhatfs the progress on the algorithm?h You could say, gWell, I had,h letfs see, gOne, two, three, four, five - I had five active rectangles two of which,h or something like that. I donft know. gBefore the algorithm I had five or something and now I have only two, so it went down.h

And you could also talk about the total volume. In this case the total area. So you could actually say -- well, actually you can say something now. You can say the global solution is in this little -- itfs in this rectangle here, period. Everybody see?

[Student:]And we just like to destroy your certificate or is there another way?

Have I what? Destroyed what certificate?

[Student:]Of --

Oh, if I free those?

[Student:]Yeah.

No, I store them. If this is -- if itfs like lawyers around and Ifm gonna need it in the end to make my certificate I store a copy of them, yeah. But, by the way, had I developed this node I can safely destroy those records, right? So I can safely destroy the records that went below this but I have to save that one in case a lawyer asks me to prove when I terminate that the lower bound is bigger than 4. Right?

So I keep those records but I can destroy everything below them. So - okay. So this is pruning. And, like I said, it doesnft affect the algorithm but it can reduce the storage requirements or whatever. And then you can track the progress had been total pruned volume or unpruned, and the number of pruned leaves in the partition. So -- and that gives you a rough idea of how complex the problem is, right?

Because when I terminate and say, you know, gOkay, Ifm done. The lower bound is 4.11, the upper bound is 4.18,h and you stop and someone says, gReally? Prove the lower bound.h If I say, gOh, yeah, no problem. By the way, itfs a convex problem. I give you one dual point and Ifm done.h Right? Or something like that.

If itfs a non-convex problem we go, gOh, yeah, sure. Let me tell you how I know the lower bound is bigger than 4.18.h You say, gHere is a partition of the original rectangle into 40,000, you know, 40,346 rectangles. And each one, by the way, Ifve attached a list -- a lower bound for each one and the minimum of all those numbers is 4.18.h

And so thatfs how you -- that would be the certificate. Now that actually tells you sort of how complex your function is essentially and you can actually work that out. I mean, if itfs something with a bunch of lower bounds, I mean, sort of minimum or something like that it would have to look something like that.

Okay, so letfs do the convergence analysis quickly. So if you donft prune every time you split a rectangle you take a child -- you take a leaf, sorry, you take a leaf, and then you append two children to it. So itfs no longer a leaf but what had been one leaf is now two so the number of rectangles after K steps is K - the number leaves which is the number of rectangles in a partition is K.

And the total volume of all the rectangles and certainly the volume of the initial rectangles and that says that the minimum volume of all your rectangles is less than or equal to the initial volume divided by K.

Itfs actually probably a lot smaller but thatfs a lower bound. And that would only occur if you split these, you know, I mean, you could get a much, much better lower bound if youfre actually splitting things in half so the volumefs going down by a factor of two you could probably -- itfd be a log in there or something like that. But it doesnft matter. I mean thatfs the -- this is good enough.

And what that says -- because this is gonna be a really, I mean, crappy proof. Itfs just gonna basically say it works and not much more because actually therefs no point investing and having a fancy proof that gets a better complexity of result but theyfre all gonna be terrible. Theyfre all gonna be exponential in the end. So it doesnft -- it really hardly matters then who has the best exponential bound.

So this says the following. After youfve done a large number of iterations therefs at least one rectangle with small volume. Now wefre gonna show that small volume implies small size.

Now, of course, in general thatfs completely false, right? If you keep splitting a rectangle -- just in R2, if you keep splitting a rectangle, you know, vertically then itfll have small volume eventually and its diameter will still be the same.

So you have to -- wefll see that youfre gonna have to -- it has to be something in your selection rule which controls for that. Now, if you have a rectangle that has small diameter then by definition it -- sorry, by our assumption it says that our -- the bounds there are small, okay.

Now thatfs interesting because when you picked that rectangle L was the leading candidate, was the lower bound. And if that was the global lower bound when you picked it and you got a U thatfs close to it, that means that your global upper bound is very close to your global upper bound and that means that UK-LK is small. So this is gonna -- thatfs how that proof is gonna go. And these all require little bits and pieces of the assumptions there. Wefll see.

Okay, so to prove that the -- to insure that the -- if you want insure that small volume implies small size then you need to control essentially the condition number. And the condition number is -- for a rectangle itfs easy, itfs just the longest edge divided by the shortest edge.

And what you need is the following, if your splitting rule is you split along the longest edge then youfre absolutely guaranteed that the condition number of the new rectangle is less than the condition number of the previous one in two.

Now therefs many other rules that would satisfy this and it really hardly matters because these are not -- in some ways these algorithm are in the worst case theyfre extremely slow. So itfs not interesting that they converge, of course they converge, I mean, unless you do something stupid, they converge.

And you generally canft prove that they converge faster than exponentially so itfs -- Ifm not exactly sure, I mean, this is just enumerating some of the intensely stupid things you could do to make this not work.

But, okay. So -- and let me just explain this because itfs not totally obvious but itfs actually true. Itfs this -- if I have a rectangle, letfs take a rectangle like that, whatfs the condition number on that? Just roughly? Whatfs the condition number?

[Student:]Four.

Four, fine. And if I split along the longest edge like this whatfs the condition -- the maximum condition number of the children?

[Student:]Two.

Two. So I made progress. My condition number went down. Everybody -- okay. Now the question is, can you split a rectangle and have the condition number go up?

[Student:]Yes.

Yeah, like what?

[Student:]I could split this.

Split what?

[Student:]What you had horizontally.

No, no, Ifm sorry, yes, sorry, I meant to say this. Can you split a rectangle along its longest edge and have the condition number go up? Could you?

[Student:]A square?

Yeah, letfs take a square. Whatfs the condition number on that? One. Letfs split it only -- and letfs say that this edge is 1.0001. Okay? So thatfs the longest. I split. Whatfs the condition number on the children?

[Student:]Two.

Two. Okay. So the condition number can go up when you split along the longest edge. However, it canft go more than two. So youfd have to argue that this is the worst thing that can happen and thatfs not too hard to do. That is true. Okay?

So it says when you split a rectangle along its longest edge the following is true. The condition number is less than or equal to the maximum of the condition number of the rectangle you split, two. And the two would be achieved if the condition number of the parent had been one, which is to say it was a cube.

Everything cool on that? I mean, I didnft show it but, you know, itfs like arithmetic. So thatfs what that is, okay. So that says if you use the longest edge splitting rule the condition number will never be worse than the initial condition number and the max of that in two, so period.

Therefs lots of others, it doesnft -- the only thing you canft do is you canft keep splitting in the same direction or something like that so that the volume goes to zero and the longest -- so every now and then you have to split against the longest edge or something like that. I mean, it doesnft matter.

If you bound the condition number you can bound -- then youfre done because you can bound the diameter. So you would have this, I mean, the volume is this thing and thatfs bigger than or equal to I can assume the worst thing would be -- the smallest it could possibly be would be to have one of these things have the max and all the others be at the min.

Thatfs this thing and so you can bound this by condition number is hardly surprising. And so this tells you that if the condition number is bounded, which it is if we use the longest edge splitting rule, then it says that the size of Q is small.

And so that actually finishes it. Thatfs done. So thatfs the whole proof now and therefs a few things I didnft show. Oh, I know itfs not -- I didnft formally show that when you split a rectangle its condition number is no worse than the parent or two, whichever is the worst of those two. So thatfs all. So thatfs it. Okay, so that is -- thatfs branch and bound.

Wefre gonna look at one more example of it, just a different flavor, exact same ideas. This will be more specific about it. So itfs gonna be mixed Boolean convex problems. These come up all the time. So itfs a problem that looks like this. You minimize a function and wefre actually gonna assume that these functions are all convex in both X and Z.

Now a little bit weird here because these functions donft actually have to be defined for the Zfs except Boolean Zfs, right? So and in fact they -- if theyfre not defined for those you have to extend the functions FI to make sense when the Zfs are in between, okay.

And therefs actually many ways to do that but that has to be done. So okay, the X is called the continuous variable and the Z is called the Boolean variable. By the way, it could be a problem with just Boolean variables.

By the way, if therefs no Boolean variables thatfs called a convex problem and we can solve it very effectively. And what happens is this, if you commit to the Boolean variables here, so in other words if Ifve got ten of them and I commit to them, I take one of the 1024 patterns of Booleans this problem becomes convex in the Xfs and therefore itfs easy to solve.

So, by the way, if N here is ten then you can always solve this problem by just taking all 1024 variations on pattern -- bit patterns on Z, solving those convex problems. Right?

Okay, so thatfs the brute force method is you simply evaluate -- you simply solve this problem for all two to the N values of Z. And if Z is less than ten or these are small problems and you have a lot of friends with idle machines and, you know, you know how to distributes jobs on different machines or something, you know, that can work fine, I mean, provided N is, like, small, like less than 20 or something like that. Thatfll work fine.

But -- well, wefll see what that corresponds to. By the way, the partition of the feasible set is actually gonna be a discrete partition. It depends on the values of Z. Okay, branch and bound -- if you run branch and bound on this whatfs gonna happen is in the worst case youfre gonna end enumerating stuff anyway.

So itfs -- thatfs -- therefs no -- and itfs not hard to create problems where thatfs exactly whatfll happen except with more overhead than just writing a bunch of for loops that goes through and tries every value. Because you maintain some big tree and the tree just fills up. You make a full binary tree and then you are exactly the same as if you had -- you just filled it initially or something like that. But the idea is that itfll work much better and it generally does.

So in this case we can talk very specifically about how to find a convex relaxation. The simplest one by far is the linear relaxation. So you take Z, which had been in the set squiggly, you know, left bracket zero, one and now you make it in the interval, square bracket zero, one. Thatfs the interval here.

Now, you know, if anyone -- and people ask you what youfre doing you can make up all sorts of cool stuff. You could say, gThis is the quantum mechanical interpretation. You see the Zfs before had been true or false now they have some -- theyfre some number between zero and one.h And if they buy it, you know, great.

But, anyway -- or in communications you would call this a soft decision, right? And youfd say, gNo, no, pardon me but Ifd like to know whether that bit is a zero or one.h And you could say, gIfm working on it. At the moment itfs a .8.h Thatfs a soft decision or -- actually, do they -- they have these in these [inaudible], right? People have seen that, no, somewhere?

So thatfs -- so itfs got all sorts of names in different application areas where they make it sound like itfs more sophisticated and more useful than actually the zero, onefs. But anyway thatfs a good excuse.

Those are good techniques to learn. I mean how to relax a problem and then convince the people youfre working with that although youfre no longer solving the original problem youfre solving something thatfs more sophisticated and actually has more information in it, you know?

Like in fault detection, they could say, gI just want to know if the fault has occurred or not.h And you go, gHa, thatfs a very unsophisticated way to look at it.h Ifm saying itfs occurred, you know, .8 and they go, gWell, what does that mean?h And you go, gWell, itfs more sophisticated. I mean, I -- it means itfs probably occurred.h Or anyway -- so we wonft go into -- I wonft go into that. Letfs go on.

Okay, now obviously when you solve this problem which is convex you get a lower bound on P*, thatfs obvious. And you can get plus infinity, thatfs actually a very, very nice lower bound because that means that the original problem is infeasible. Now, by the way, how would you get an upper bound? How would you get an upper bound for a problem like this?

[Student:][Inaudible] the combinations, right?

Yeah, yeah. You can test any, right? By the way, how would you get it though? Tell me some practical methods for this thing. Well, here we can look at this several ways but we can -- Ifll go over some of them but herefs one. The simplest method by far would be to round each relaxed Boolean variable to zero or one, okay, which, by the way, can destroy feasibility at which point your upper bound is plus infinity, okay.

Another option is you could round them and once youfve rounded them go back and solve for Xfs. That can only make things better. You could, for example, restore feasibility, reduce the objective value, okay. Thatfs your other option.

You could use a randomized method, I mean, this is -- you would generate a random ZI and 01 with probability equal to this relaxed value. So now the .8, the soft decision, makes sense. So you generate random ones and try this and so on. Letfs see, I could say -- let me say one more thing probably more useful in practice than a randomized method which, however, will impress people. So Ifd recommend it on that end for that reason.

But therefs actually a much better way to do this. What you can do is you can do a local optimization. So once -- assuming you have a feasible Boolean point you simple cycle through the Zfs, you flip each bit. So if Z17 is one you flip it to zero and then -- and see if actually things got better. If it got better you keep it.

So, I mean, youfre just talking about you do some really greedy algorithm for this, can only improve your upper bound, canft make it worse. So, by the way, methods like that often work -- I mean, just basically in general convex relaxations followed by the stupidest local optimization methods you can think of, the stupidest, greediest methods work shocking, just shocking, well. So thatfs actually way to get a good upper bound.

Okay, how do you branch? Thatfs easy. You pick an index K to branch on and you do the following, you pick index K and you split your problems into two, one where ZK is zero and one where ZK is one, okay.

And you relax -- how do you get the lower bound and upper boundfs on the thing? The lower bound you relax these, you get a lower bound here; you relax these you get a lower bound here. Upper bound you can do whatever -- however you like. You can round the relaxation followed by a local optimization, thatfs gonna work very well.

Okay, so these are just Boolean convex problem within -1 Boolean variables because you can eliminate the chosen variable if you like and you get exactly the same thing as before. So you can just run branch and bound. How do you get the new lower bound? I mean, this is the same as before so Ifm not even gonna go into it because itfs kind of obvious. You get these new lower bounds.

So herefs the branch and bound algorithm for a mixed convex Boolean problem. You do the following, you just form this binary tree, youfre splitting, relaxing and calculating bounds on the subproblems. So each -- now each node is labeled -- when you split the binary tree, each -- the edges are labeled by a certain Boolean variable either equal to zero or one. That doesnft say the left and the right sides in the tree.

And so actually a node is very -- a node in the tree is very interesting in that case. So in that case this is the wrong picture and in this case it would look something like this. There, so therefs a tree and it basically says that you first split on variable 17 and so this would be Z17 equals zero, this is Z17 equals one. This is Z13 equals zero. Z13 equals one and so on, okay.

So now the meaning of a node is quite -- very interesting. So it basically means -- it says here if I go to this node here it means that two out of M of my Boolean variables have been fixed. Two of them, and theyfve been fixed to the values 1 and 1 because I took this thing.

Here theyfre fixed to the values one and zero here and then below this. But the others are still floating. I havenft committed to them yet so thatfs the picture. And if you develop the full Boolean tree then congratulations you just did brute force on it. So, okay. So there is no convergence proof because itfs stupid at most when youfve filled out two to the N leaves you just did brute force. So itfs silly.

Obviously you can prune. Same thing, you can pick a node with a smallest L and to pick a variable split thatfs actually if you read about things -- again, this is where, you know, personal expression comes in, so one of the places. The other is in the -- when you actually implement the methods that produce the lower the upper bound. Thatfs where the -- honestly thatfs probably where the more important personal expression comes in.

But this is also important and therefs two, actually, youfd find defended in the literature. One would be the least ambivalent. So youfd take the ones where you -- or 01, the idea is to prune that quickly, to just prove that the solution is not there. And so thatfs one method.

Another one is maybe the most ambivalent and herefs what you do is you choose the value of K for which ZK* minus half is minimum. If, by the way, you get to -- whoa, what does it mean if you get to a node and the lower and upper bound are equal? Actually, what if you get to a node and at that node when you do the -- solve the relaxation itfs a 01 solution in the relaxation?

It means the lower and upper bound are equal and it means you now know the global solution on that node. In other words, if those binary variables leading from the top down to your node have those values you now know the optimal value below it, okay. So but the most ambivalent would be to pick the one for which thatfs minimum, I mean, thatfs one method.

Okay, herefs a small example just to see how this works. I think youfre gonna do exactly this by hand on the homework. So itfs the only way to really clarify your mind about these things and that way you can say youfve done branch and bound. You can even have a nice pause then so the person gets it and then you can lean forward and say, gBy hand.h

So which very few people can say that actually. So itfs a cool thing to be able to say and then if they looked shocked you can say, gI mean, I didnft solve the QPfs by hand but I did do branch and bound by hand.h But anyway, okay.

So herefs an example, we start off -- and letfs just even back out what on earth this means. Itfs a three variable Boolean LP, this is stupid, I could have solved 8 LPfs and be done with it. Okay? So I could have. But letfs see what this means. Letfs just see what these numbers mean to see if they make any sense. I solved the original relaxation and I found out that the -- I relax all three Boolean variables I find out the lower bound is -.143. Whatfs the infinity mean?

[Student:]Infeasibility.

What was infeasible?

[Student:][Inaudible] that one was one the problem.

No, no, this infinity. What does that mean? It has a meaning. Oh, it means -- yeah, it means infeasible but whatfs the precise meaning of that infinity? It has a very precise meaning. I mean, it sounds informal but itfs completely precise.

[Student:][Inaudible] infinity means nothing.

I means that whatever upper bound method I used -- rounding, whatever, couldnft have been that great actually but whatever upper bound method I used it did not produce a feasible point. In which case the upper bound remains plus infinity.

By the way, it couldnft have been a very good upper bound because therefs only 8 -- but it doesnft matter. So the point is it could have been just I rounded the relaxed solution, evaluated, violated constraints which are N plus infinity. I split on Z1 and I got herefs 0 and 1. I got -- and by the way, what does this mean? That means something, too.

[Student:][Inaudible].

It means this says that when I solve the relaxation with Z1 equals one, by the way, the relaxation there is Ifm relaxing Z2 and Z3. Therefs just three variables here, itfs kind of a stupid problem, right?

So I relaxed those two and that LP was infeasible and you know what that tells you? That tells you that if Z1 is zero therefs no feasible point. And so we will never -- basically you know what that says? That tells us at that point we -- at this moment we know exactly what Z1* is. Well, itfs still -- we still donft know, by the way, the problems even feasible. So I should say Z1* is either nan or 1 and thatfs gonna -- wefre only gonna find that out later.

But at the moment it cannot be zero. Itfs either nan or one, okay. So herefs z1 equals one and I solved this LP, the relaxed one, and I find the lower bound is .2 which means that Ifve actually gained information on the lower bound but I still have yet to produce a feasible point. You know, who knows why? Because I have a very bad upper bounding mechanism or something like that.

Then I split on Z2 is zero and one, this canft be the answer and then here I get 11 and now Ifm done. And letfs figure out what I -- how much work did I save myself? Actually, how much work did I save myself by running branch and bound?

Well, letfs see, I could have just solved eight LPfs and been done with it but instead I solved one, two, three, four, five, okay. So, I donft know, I cut it by a factor of two. I mean, itfs a stupid example, right, but thatfs not a significant one, but okay.

Wefll see significant ones. Now wefre gonna see a significant one. So wefre gonna go back, wefre gonna solve the same problem we were solving in the L1 lectures. There we were doing heuristically. We want to minimize the cardinality of X, subject in a -- we want to find the sparsest vector in a polyhedron.

And so you write that as a mixed Boolean LP, you have lower and upper bound on the Zfs and Ifll get to those in a minute. Those you get simply by bounding the box and I mean, putting a box -- the smallest box around the polyhedron, okay.

So the relaxed problems are simple enough. If you exactly relax this it comes out to this. This, by the way, we saw. Itfs the sophisticated version of L1 heuristic for minimum cardinality when the box is asymmetric with respect to the origin or something. By the way, if any of the ranges -- if L1 is positive or U1 is negative the sign -- sorry, whether or not that variable is zero or not is done, okay. So thatfs fixed.

Okay, so this is -- wefre gonna run -- wefre gonna split the node with the lowerest bound. Oh, there is one thing you can do. When youfre solving this minimum cardinality problem the outcome of value is clearly an integer. So if I tell you that the -- if I solve that LP or whatever it was and I get a lower bound that is 19.05. What is the actual? I can actual immediately say that the lower bound on the cardinality is what?

[Student:][Inaudible].

Twenty, itfs 20 because the cardinality, which is obviously an integer, itfs bigger than 19.05 and the next integer is 20. So this is obvious.

Okay, so wefll do a small problem. This one has got 30 variables and 100 constraints so -- but the number is, you know, these are not small numbers, right? Two to the 30 is about a billion or something. And it turns out it takes eight iterations to find a point with global minimum cardinality. Thatfs the good news.

Now the bad news -- and this is extremely typical of branch and bound. It took a lot more iterations to prove that the minimum cardinality was 19. And by the way, these numbers get even more crazy when you put in a sophisticated local search because then basically itfs very typical, you find it in six iterations or something like that, you know, very fast and then 80,000 iterations later youfve now proved that the point you found on the sixth iteration is actually like 5 percent suboptimal or whatever your thing is.

Okay, so this took 309 LP solves, thatfs including the 60 to calculate the lower and upper bounds. And so these were actually just done by Jacob and actually all the Python code is on -- you do not want to write this in matlab. That would be a joke. Well, not joke it wouldnft be funny at all for you. It would be funny for other people but not for you.

So herefs what sort of the tree looks like at various points. This is kind of what it looks like. And by the way, when it finally returns and says itfs 19 and someone says, you know, gHow --g or whatever it is, it wasnft 19, whatever the minimum cardinality is 30 something. Is it 19? The minimum cardinality is 19.

It basically says, gLook, you know, how can you prove this?h You would say something like this -- youfd have to return this thing. Actually, youfll see what you would have to return the certificate proving it.

This just shows the global upper and lower bound. The dash one shows the true upper bound. You can see it starts at 12 and ends up here at 18 in 60 steps or something. And then you canft see it but it terminates right there when this thing goes up and youfre done.

So thatfs sort of the picture and you might, by the way, this kind of puts it all in perspective. It basically says that these L1 heuristics are awfully good, right? Because youfve produced a point with a cardinality of 21 and the global minimum was 19. By the way, had you done an iterated L1 or a local search here you almost certainly would have got a point with cardinality 20 and you would have got it just in a handful of LP solves. So -- but it took a whole lot more effort to prove it, so this is very common.

This shows sort of the portion of non-pruned values. Out of the 2 to the 30, this shows you the fraction. And, I mean, itfs not -- itfs just something to kind of look at and see how progress goes. And the number of active leaves in the tree; I guess it terminates at 50 something or other. So what that says if that if someone says, gProve that the optimum -- the minimum cardinality is 19.h Then the way youfd do it is youfd say, gNot a problem. Here is an X with 19 non-0fs that satisfies the N equality.h

And they go, gFine. That means itfs no more than 19. How do you know therefs not a point with 18 non-zeros?h And youfd say, gNo problem,h and you would return this data structure which is a tree with 50 some odd, 53 different -- a tree with 53 nodes which is a partition of this space and on each one of those you would have solved this convex problem, youfd have left the evidence or the certificate for that there and youfd say, gThere you go. Therefs your proof.h

So your certificate is a complicated object in this case, okay. This is a larger example, Ifm just gonna zoom through it because wefre -- well, wefre out of time. But -- and this is just in the interest of intellectual honesty just to show that if you try to solve larger problems -- by the way, these are problems with just not many variables, right? Convex problems with 50 variables are joke. As you know, you can solve a convex problem with 50 variables and a hundred constraints, what are the units?

[Student:][Inaudible].

Okay, milliseconds. Ifll accept that, at the way small end of milliseconds. I would -- Ifm going for microseconds on that one, but no problem. By the way, thank you for saying that on the last day of the year. That makes me very happy.

So but the point is here, you know, the minute you go to the non-convex problems even like 50 variables, 100 variables, these are now very -- these are large numbers. And you can be lucky, of course, and solve gigantic problems again if the gods of global optimization branch and bound are smiling on you, you can actually solve very large problems.

But you better understand itfs only by luck or something like that, that that happens. So I think I wonft go into this. I mean, therefs a huge problem and this problem is great because it kind of -- at least it sets the record honestly.

So this was run 5000 iterations and at that point herefs what you know about the global solution. It is between, you know, something like 135 and 180 or something like that. And this is really the way these -- this is kind of how it -- when it fails, this is what it fails like. This is the way it looks.

Notice how much better your point was with all that effort. So and this picture would be a very good endorsement of these L1 methods as heuristics. This is why itfs better off saying, gNo, Ifm vague about scarcity. I donft really need the absolute sparsest.h In which case youfre way better off right down here.

So we are out of time. Youfre gonna hear another communication from us about the exact -- wefll set the time and wefll probably give you the poster format for Monday and well, maybe wefll see you tomorrow and then maybe -- definitely Monday.

So oh, and I have one more thing I have to say. I have to thank the TAfs very much for creating all the new lectures. One very important thing. Someone not here but who has, I mean, helped enormously in the last two classes is Michael Grant. So some of you know this by saying something doesnft work and having the build number increment because of you, literally within an hour.

So we all owe a huge debt of gratitude to Michael Grant who -- Ifm not even gonna tell -- hefll never even find out. Somebody will point him to this part of the lecture then hefll hear about it.

Okay, well, thanks and wefll see you Monday.