Well, this is -- wefre all supposed to pretend itfs Tuesday. Ifll be in Washington, unfortunately. So today Ifll finish up and give a wrap up on the Analytic Center Cutting-Plane Method, and then wefll move on to, actually, one of the coolest topics that really kind of finishes this whole section of the class, and thatfs the Ellipsoid Method. So wefll look at this, and Ifll try to make clear what is useful and whatfs not. The Analytic Center Cutting-Plane Method is useful. When you have a problem that you need to solve where you really do only have access to something like a cutting plane or sub-gradient oracle, and for whatever reason -- you have to look at those reasons very carefully.

But if you have such a problem, this is an awfully good choice, and itfs going to beat any sub-gradient type method very much. This is going to have much more computation, obviously, per step, more storage, all sorts of stuff like that, compared to sub-gradient method, which involves essentially zero computation and zero storage. Theyfre way, way, way, way better than sub-gradient methods. Okay, so herefs the Analytic Center Cutting-Plane Method. Youfre given an initial polyhedron known to contain some targets which might be feasible points, might be epsilon sub-optimal points.

Doesnft really matter what it is. You find the analytic center of the polyhedron, which is to say more precisely, you find the analytic center of the linear inequalities that represent the polyhedron. And you query the cutting-plane oracle at that point. If that point is in your target set, you quit. Otherwise, you add, you append this new cutting-plane to the set. Of course, what happens now is your point X (K+1) is not in P (K+1) by definition. Well, sorry. It might be in it if itfs a neutral cut, but itfs on the boundary.

What you need to do now is at the next step youfll need to calculate the analytic center of that new set, and I think -- I wonft go through this. Therefs a lot of different methods. Infeasible Sartinutin Method is the simplest one. Maybe not the best, but wefll go on and just go to a problem, and Ifll show how this works. So this is a problem wefve looked at already several times. Itfs piecewise linear minimization. Itfs a problem with 20 variables and 100 terms, and an optimal value around one. Let me add, just to make sure this is absolutely certain and clear. If this problem were -- if you just had to solve a problem like that, it goes without saying you would not use something like an analytic center.

Youfd just solve the LP. Letfs bear in mind that every one of these iterations requires an effort thatfs at least on the order of magnitude of simply solving this problem to ten significant figures right off the bat by Barrier Method. So your code from last quarter, your homework code which shouldnft have been too many lines, will actually solve this problem very, very quickly. In fact, anyone want to take a cut at how fast it would be?

You have to solve -- you have to minimize piecewise linear function 20 variables and 100 terms. Itfs gonna be an LP -- when you add another variable, itfs an LP with, I donft know, what is it, 21 variables and 100 constraints. Something like that. So letfs say itfs 20 variables, 100 constraints. Dominating cost is gonna be actually forming like A transpose HA. So forming a 20 by 20 matrix, which is actually a matrix -- 100 by 20 matrix multiply, or something like that. So thatfs 100 times 20 squared, and youfre gonna do maybe 20 steps. Thatfs an interior point method. How fast would that be, just an order of magnitude?

What do you think? Microsecond. Well, itfs good. Youfre guessing sort of the right numbers now. You might be a little bit low. Actually, when you get down into the 10 and 20 variables, the N cubed, the various blast extrapolations start falling off. But letfs -- based on blast extrapolation -- well, I can tell you how Ifd do it. Itfs 20 squared times 100, and the way I do it is I think 1,000 cubed. Letfs just say a second. Thatfs way more ecause a Cholesky factorization in this -- I donft know. Itfs .18 seconds on my laptop, so itfs not a big deal.

But something else matrix [inaudible] might be half a second. So letfs call it a second. Letfs round up and say 1,000 cubes is a second. Youfd get a factor of ten right here because youfre doing 100. You get ten, and then you get 50 squared, 2500. So itfs 25,000 times faster than one second. Letfs say thatfs 40 microseconds, and letfs be generous and say youfre gonna do 20 of those steps. I think I did that. So 40 microseconds [inaudible] 20s. So the answer is a millisecond, so if there wasnft a microsecond, but your answer was in the right spirit.

All this is just to point out that this particular problem could be solved easily through very high accuracy in under one millisecond. These are very good things to know, by the way. Very few people know this, I promise you. If you go around and ask people who -- if you ask the authors of widely used packages, they have no idea how fast you can solve small problems.

[Student:]Is this leaving -- every time you make a cut, is this leaving?

Yes. So in this example, this is gonna leap all constraint. So it must be understood here that when you start, we probably had 40 constraints because we probably put a box around it or something. I donft -- Ifm sure we did that. So we probably put a box around it. This has forty constraints, and in the classic ACCPM thing, how many constraints have you got over here? Thatfs it. 240. So the number of -- back to the size of the problem solved over here is six times as big as the problem here. Itfs 240. So wefll get to a bunch of this. Wefll talk about it and just see how it works.

Nice thing you see here is you donft see that horrible slow-down you donft see in a sub-gradient method where you kinda go like this, and then kinda slow -- get into this nice, one over K, very slow convergence. What you do is you see something that looks much more like an interior point method, except that would not be 200 steps; itfd be 20, or something like that. Youfd see nice, geometric, linear conversions.

Okay, now the previous one shows -- this is F of X, K -- F*, and what this shows is the best of those. So this is probably what matters because when you terminate the algorithm at any point, youfre actually -- of course, what youfre gonna return is the best thing youfve seen so far. These long things here -- of course, well actually, what do they mean? What does the long horizontal -- what does a segment mean in this picture? This is iteration number versus sub-optimality. Your best one.

[Student:]Trying to satisfy the constraints.

No, this is -- we keep all constraints. What does it mean?

[Student:]Itfs infeasible?

No, it canft be infeasible, right? Because we just -- well, if itfs infeasible, we stop. But that canft happen for this piecewise linear minimization problem. No, what this means here is that your F-K best has not changed. It means, in this case, that for ten steps you produced points that actually were worse than the best thing youfve already seen. This is just underscoring the fact that this is a non-descent method. So a flat part means that some people might say that you failed to make progress, unless you failed to make progress in terms of finding a point with a better objective value. Actually, how have you made progress? What actually did happen in one of these little steps?

[Student:]You have a more constrained space.

Yeah, so your P-K got smaller. So, technically speaking, your ignorance was reduced over that step, but you failed to produce a point. You were lucky. You had a good point, but your ignorance -- and that ignorance is going to translate into future good point values. So thatfs what those mean. Okay, now if you want to compare this to Newtonfs steps -- and I think if we go back and forth, we can look at the two pictures. Thatfs about 200 iterations, and here you can see that we did about, I donft know, about ten, eleven Newton steps. About eleven Newton steps per -- so it took, on average, about eleven Newton steps to recalculate a new analytic center.

By the way, I should mention that wefre -- this is not tuned. We did have a fairly small tolerance for analytic centering. In other words we probably calculate the analytic center to land the squared less when you minus six or something like that. Needless to say, that means that the last three Newton steps we took in every one of our centering was a complete waste of time. Because remember, the goal here is not to calculate the analytic center. The goal is to get enough query point to -- so these numbers, you could probably get it down to five Newton steps. Ifm just saying if you actually wanted to do this.

So this is just sort of straight out of the box. No -- well, all the code is online, so you can look at it as well as I can.

[Student:]For the infeasible Newtonfs, donft you have to wait until you get feasibility?

Yeah, and in fact, we donft have that here, but I might actually go back in the code and actually get some of the statistics. Like how many steps on average -- the feasibility. Precisely right, that would be a really good thing to know. I may go back and do that. Itfd be fun. You can, by the way, since the code is all there. Yeah, so that would be one question. And you can see, by the way, a little curvature means that as this thing progresses, the centering are getting a little bit harder. Therefs certain -- youfre on a pretty steep thing like this for a while, and then the slope here is half as -- if you compare the beginning and the end, the centering have gotten harder.

By the way, what is the effort per Newton step? Is this a valid -- does this track time well? Is that -- I mean, thatfs Newtonfs step. Does it track time? Is that a valid -- so, actually, how does time grow with these?

[Student:]Well, youfre adding an extra constraint.

Absolutely.

[Student:]Every time, so yeah. I think itfs --

So itfs going linearly. The problem size. Whatfs the competition complexity of the Newton step as a function of the number of inequalities? Itfs what? You guys have to get good at this. Here, you want to know the sloppy way to do it? Someone just walks up to you on the street and says, gQuick, quick, whatfs the complexity?h The big number times the small number squared because thatfs the answer for lease squares and any problem like that, right?

By the way, thatfs conditioned on the fact that youfve done it right. So if in fact itfs the big number squared times the small number then itfs wrong. So thatfs my quick rule of thumb. Then later, when you can go catch your breath or whatever, you can go work out the Newton step, and therefs 20 of these. But thatfs just a good working number. You know, if M is bigger than N, itfs M-N squared. Thatfs the answer for Lease squares, by the way. Lease squares, Lease norm, everything. So therefore, the cost per Newton step -- whatfs happening is you have 20 variables.

Thatfs a small dimension, and then you have the big dimension is the number of constraints. And it starts at 40 and ends at, I donft know, 240. What did we say? Goes up by factor of six, and roughly speaking, itfs growing linearly. So as you go along here, thatfs a six times bigger problem in terms of big dimension. Therefore, if you do things right, itfs a big dimension linear, quadratic in the small dimension. The cost of a Newton step from here to here actually goes up by a factor of six, linearly. So what you do is youfd do a quadratic distortion of this axis to give you the actual time. Make sense?

Because each step over here costs six times what a step over here costs. A step in the middle costs three times. So all I would do is take these numbers and spread them out quadratically. Ifd have an affine expansion. Everybody cool on this? So that would be time. We didnft have it here, but it doesnft matter.

All right, so this just shows you again. This is the base line, nothing funny, no constraint dropping, no nothing, just basic ACCPM, right out of the box. So here what we have done is we have plotted two things. This is the true optimality. Now, of course, when youfre running, you do not know this thing. We obtained this by using CVX to solve this in not one millisecond. Letfs see what CVX had us interpret it overhead. Itfs gonna swamp everything. I guess by the time it gets down to STBT3, itfs probably 30 milliseconds here.

Wait, super fast. Wefve got the actual solution, and then use that to judge our progress. This however -- so this you do not know in real time. What you do know is that, this number. This is the best upper bound. By the way, the lower bound is also -- does not go up monotonically, right? In an interior point method, right, what happens is that every step when you do a centering is you get a better point as your objective value goes down. And not only that, your dual value goes up. So you get the beautiful things where your best point and -- you donft distinguish between your best point and your current point because the current point is always the best one. Itfs a descent method.

But youfre lower bounds also go up, so you have no logic in an interior point barrier method, or whatever, that says keep a hold of the last point because it may be a while before you see one thatfs better. Or in terms of lower bounds, you donft keep track of the best lower bound youfve seen because the next 15 you see are actually worse than the one you have. So here, though, you do know this one, and you can see itfs off by some factor. I donft know, a factor of eight or something like that, or whatever. So thatfs all. Thatfs all that this is.

So your stopping criterion might be based on the red dash thing, although I should probably say something. The sub-gradient method has, in general I think itfs fair to say from a practical point of view, no stopping criterion. But usually when youfre running sub-gradient methods, itfs in some situation where youfre so desperate to have anything thatfs all -- that does anything, that youfre just happy to have something. If things get better after 50 steps, or ten, you know. Thatfs good enough, right? So stopping criterion is a luxury that you, generally speaking, donft actually have when you apply one of these.

The same might be true here in these. Maybe less so, but you still have the same thing. Okay, now we do constraint dropping. All right, so here what we did is -- now by the way, keeping 3-N is actually quite interesting because we start with 40 constraints. We start with a box on X. X is in our 20. We put it in a box. Ifm guessing that, but one of you with a laptop could actually look at the code and find out. You have a laptop. You donft have to, but I presume thatfs how we initialize it is with 40 constraints, which are BOTS constraints. So -- and this is the progress if you do no constraint dropping the blue thing.

And remember, when you know dropping up here, your polyhedron has 240, or whatever it is. Wait a minute. Yeah, up here. It has 240 inequalities. So thatfs this thing at R-20, polyhedron at R-20. Kind of a small one, by the way, at this point. Itfs quite small, and itfs got 240 inequalities. By the way, I have no idea how many of the 240 are redundant. I presume the original 40 are redundant. The original 40 were the boxes, and the idea is we just made a big old box. So it would kinda be bad if those were still active. So those 40 are probably redundant. Probably a lot of redundant, but I donft know. We didnft do that calculation.

But we keep 3-N. So wefre going to keep 60 at any given time. So by the way, a polyhedron in R-20. Whatfs the minimum number of inequalities that would give you a bounded polyhedron in R-20?

[Student:]Forty?

Forty, well that -- in R-20. A 40 would do it, absolutely, if you have a box, but thatfs not the minimum number. Whatfs the minimum number? Can you do it with eight?

[Student:]No.

What? Someone said no. Why not?

[Student:]Itfs 20 --

So you need at least 20. If you have eight, then basically there is a 12 dimensional sub-space of things orthogonal to those. And so youfre unbounded this instantly in at least 12 dimensions, so youfre not gonna be bounded. So the answer is 21. You need 21, and a simplex is the smallest number of -- itfs the simplest polyhedron thatfs bounded. Simplest in the number of inequalities, and it requires N plus one.

So the point is it takes 21 inequalities. To just have a bounded polyhedron, wefre taking like 60, so itfs not like itfs a super -- this is not an exquisitely detailed description of a polyhedron. And the wild thing is you see this? Itfs just totally insane. The progress is identical. By the way, what is the change in computation time? Again, not that we would care, but lets figure that out. Whatfs the difference between solving -- computing the analytic center for the red guy and the blue. What is it there?

[Student:]Post for each Newtons.

Yeah, I know that, but I want to know the number. You can figure it out. Everything is here. You know all the dimensions, so I want the number. Of course the cost per Newton step is different. Thatfs what it is. Now I want the number.

[Student:]When you drop, or when you donft drop?

Both. The blue is no drop. The red is keep 60, so youfre dropping. What is it?

[Student:]B minus 6 --

Do 40 over 60. So the -- in this case, you analytic center 240 inequalities, 20 variables. In the red case, you analytic center 20 variables, 60 inequalities. So, again, big times small squared. Itfs linear and big. 240 versus 64 to one.

[Student:]What about the complexity of reducing the constraints?

Oh, that would solving like an LP per step. Oh, now we could actually do much more analysis in here that would sort of be fun. So you know an Analytic Center Cutting-Plane Method. At each step there is -- you get for free -- some constraints you can promise. You can actually guarantee are redundant with no further discussion. You donft have to avoid your complexity theorist friends or anything like that. Everything is cool because theyfre provably redundant. Actually, I would love to have figured out how many -- at each step we drop things, obviously. Well, we actually didnft drop things until here, right?

Because we started with 40, and then 41, 42, 43. When we got to 60, we started dropping, and then it looked like that, right? It would be a plot of the number of inequalities. So we didnft have to look the other way for the first 20 steps. After that, when we start dropping, the question is what fraction of the things we dropped were provably or actually redundant. All of those could be calculated by just solving some LPs. Those would be really good numbers to have. We should have them in here. Itfd be fun.

It is very unlikely that everything we dropped -- oh, would that be right? Oh, hang on. Oh, thatfs not true, sorry. I was about to say something that was wrong. Good thing I didnft say it. After all this discussion, though, let me make sure that the big picture points are clear. So the big picture points are the following. It obviously works just as well. You donft need the number -- therefs no particular advantage in convergence you are getting by keeping all these constraints. That by limiting it to 3-N, youfre getting the full power. Youfre getting perfectly good convergence.

The computational complexity like that means that the cost per set here is actually -- in one case itfs growing, and in another case itfs just flat fixed. So thatfs the main point. By the way, proofs of convergence that handle constraint dropping are quite complicated, as you might imagine. Theyfre quite complicated. So they exist. Ifm very happy somebody has done it so that I can tell you somebody has done it. Therefs a gap in between, I might add. Ifm pretty sure therefs a gap in between the things people do, and the things people have proof converged.

So I do not know if a method that were -- that keeping 3-N is actually convergence. I actually donft know that. Maybe it is, maybe it isnft. But Ifve seen ones where you drop things, and these are quite complicated, as you might imagine. Okay. Oh, I guess we figured this out on our own already, so therefs nothing to say about this. The sort of numbers steps, and the number of inequalities, itfs kind of a silly plot, right? But, anyway, itfs -- okay. So now we get to something interesting.

This is using a mega flop counter in Mad Lab which is notoriously bad and all that, and I think people donft even use it anymore, but it doesnft matter. Just to get a rough idea, we should be able to figure out -- actually, we should be able to guess a lot of these things really, really well. So letfs guess. Actually, Ifll tell you how we can guess this plot. Letfs go to the end, and ask what is the accumulated -- we already decided that the red thing at this point is six times more efficient than the blue.

[Student:]Four.

Four, okay, sure, whatever. Yeah, four. Okay, so itfs four times -- and how much faster is it in the middle. Oh, I donft know. Itfs 60 versus 40 plus 100, 140? Close to two. This is a street fighting method. This is quick, dirty methods, fast. If itfs four times more efficient and itfs two here, whatfs sort of the average inefficient? And it kind of grows linearly or something. Whatfs the average sort of advantage? Two, I donft know. What do you think? Well, itfs not eight, okay? And itfs not four, and itfs not one.

Letfs call it two-to-one, and letfs see if our prediction is pretty good. Our prediction is, oh, hey. What do you know? Think about 150 mega flops, and this took about 70. So thatfs the picture. So this shows that constraint dropping, if you care about time or whatever, it works this way. By the way, a lot of this doesnft matter so much because you usually use analytic center cutting-plane in a situation where the oracle calls. The sub-gradient calls are very expensive. For example, the oracle calls -- in many of the most interesting cases, this is when youfre doing distributed optimization.

These are like other computers on the other side of the world. All sorts of stuff is happening. So the analytic center cutting-plane stuff is just like zero. Even for a problem with 10,000 variables, or something. Thatfs how these things work. Okay, now if you do the epigraph analytic center cutting-plane method, now you have 20 variables and 100 terms. And what happens is you divide -- so this actually goes way down here.

So you actually are dividing the number of steps required by just a factor of four, or something. And thatfs it. I donft think Ifm showing F best here, am I?

Yeah, there we go. So this is the epigraph one, and herefs what it looks like versus Newtonfs steps, and I donft know what happens here. But you -- I mean, it looks like youfre doing -- therefs points here where your doing better, or something. And the word on the streets as I know is that you should -- is that the Epigraph Method is better. I donft understand it, to be honest. Ifm not quite sure why, but anyway. For whatever itfs worth. Okay, so this finishes up analytic center cutting-plane method.

By the way, I should say that we havenft really seen yet the really cool examples where you would want to use these methods. So -- and I admit that. Thatfs going to be the next chunk of the class, and wefll see some very, very cool applications where you really would want to use these methods. In fact, you will. So the next topic is just absolutely beautiful. You can guess where itfs from.

[Student:]Moscow.

Youfre right, actually Moscow and Kiev. So itfs from Uddin Nemerofsky Shore in Kiev, and so and so. Guess when. Close. Actually, it probably is 60s. They say definitely for sure early 70s, and yeah. Ifm sure they knew it in Moscow in the 70s, or some 60s. And itfs absolutely beautiful. By the way, itfs quite famous, too; not very well known in the West. By the late 70s it was on the cover of the New York Times front page because it was one of the first papers used to show that linear programs could be solved in polynomial time. By the way, with a little star, meaning you have to go read the fine print.

But that was 1979, and they had a hilarious article on the front page. It was really funny, actually, and it said gLinear programming runs the entire world, everything. All airlines are scheduled for it. Nuclear weapons are built by it.h It just went on and on and on, and said this is going to totally change your life because now, and by the way, I should add. At that point for 30 years, people had been solving linear programs unbelievably well using a simplex method, just so you know. Amazingly well. It was a non-issue.

They called some mathematician at Rutgers. I mean, actually, the poor guy wrote the article. All he said was there was a complexity theory result, and it was a pretty good one. By the way, up until that point, people didnft know what the complexity of solving linear program was, and they actually introduced a new class called LP, as in P. So youfd actually say this is class LP, and it was as easy to solve as an LP and vice versa. If you had a method for solving an LP, you could actually solve these things. You had to reduct the two-way reduction. So, yeah, they really did, and then it turned out P was LP or something.

What Ifm saying is that if you really look into these things youfll see itfs much more complicated and all that, and some of the things Ifm saying, if interpreted literally, are just wrong. So this is on the front page of the New York Times saying it was gonna change the world, and it didnft. Linear programming was on the front page again in 1984 for barrier methods. This is just absolutely beautiful, this method. This is the one I just talked about. This is Gocheon, who by this time was at Rutgers, used this to show polynomial salability of LPs. So, actually, youfre gonna see a code now.

Whatfs funny about this is that the sub-gradient method is to solve an LP. I think that maybe you wrote a -- I mean, itfs not hard to write a six line code for it, and a sub-gradient method. You can just write a sub-gradient method that solves any LP. Even more, if someone says, gThatfs ridiculous. Itfs hard to write an LP solver. These are big, giant pieces of software you have to know a lot.h The proof is like a paragraph because itfs the paragraph from sub-gradient method. Thatfs pretty cool. Slower than anything, right? But it is nevertheless cool that a six-line program with a two paragraph proof solves any LP.

This was gonna be eight lines, but even scarier according to the complexity theorists this is actually an efficient method. So -- and the proof is quite short, which is even more shocking. Each step is going to require cutting-plane or sub-gradient evaluation, so itfs the same as everything else. Youfre not gonna have mono-storage, which is to say itfs gonna be Ovan squared. Which by the way is, if you do analytic center cutting-plane method with dropping, the storage is N squared because you have N variables and you store three N, five N constraints. Thatfs all you need. The only state in that algorithm is the polyhedron. So your storage then is like, whatever. Six N squared. Thatfs it.

And your update cost, by the way, is N cubed in that one, obviously because itfs N squared. Whatever it is, itfs the big times the small squared. You can actually make it faster with rank updates, but thatfs another story. Okay, so itfs got mono-storage. In the Ellipsoid Method the update will involve solving no -- well, you will solve a convex problem, but it has an analytic solution, so -- and itfs gonna be order N squared. And sufficient in theory, and itfs slow in practice, but itfs actually something like the sub-gradient method, actually, except that itfs fed in the sub-gradient method. Itfs kind of slow in practice, but it is way robust.

You can blow off whole parts of it, and start it in the wrong place, initialize it wrong, and you can give it totally wrong sub-gradients many, many times. Itfll just happily lumber along, and work really well. So thatfs -- okay. So the motivation goes something like this. In a cutting-plane method, you need serious computation. I donft know. Do you really believe that? Itfs ten Newton steps. Each Newton step is a Lease squares problem. Okay, so itfs ten lines, but this scares people, and people make a big deal about an analytical formula. You know, like a Kalman filter update versus if there is a conditional or align surge, they get all weird about it.

Of course, thatfs completely stupid and idiotic if you think about it right because a Newton step is nothing but a Lease squares. So I donft know why people -- I mean, itfs fine to have an analytical formula, and thatfs all great and everything, but the idea that these are sharply divided is really, really dumb. Itfs a distinction that makes absolutely no sense. What only matters is how fast can you carry out that calculation, and what is the variance in that calculation. And nothing else matters.

The variance can range from zero if youfre doing a matrix multiply to a little tiny bit of -- if youfre doing a sparse matrix factorization, considerable. I mean, it depends on the -- with a not given structure you have huge variance because it depends on who did the ordering for you, and how much filling you get and all that kind of stuff. Do an Eigen Value calculation for dense matrix. It has a very small -- itfs order N cubed, but it has an N squared component -- or an order N component that is subject to some variation, which is the number of steps required to calculate the Eigen Value. Obviously, if itfs N cubed plus a random number times N, the way to summarize that is it has no variance.

Oh, we just talked about this at great length. The other issue is this, is that the localization polyhedron grows in complexity as the algorithm progresses. We already talked about that. Now, I have to say, if you keep it proportional to N, like this -- so this second bullet is not a problem in practice. If you do analytic center cutting-plane method, you are going to prune constraints. Okay? Thatfs the way itfs -- thatfs how theyfre done in practice. Thatfs how they work. They appear to work juts fine, in which case this is not an issue.

So this only irritates your aesthetic side, or your theoretical side or something like that. So thatfs all that is. The Ellipsoid Method is gonna address both. Itfs gonna have a constant data structure to summarize your ignorance at each step. Analytic center cutting-plane method has a variable size because itfs a polyhedron with a variable number of constraints, and in the no cutting method it just grows.

So herefs the Ellipsoid Method. The idea is that youfre going to localize the point youfre looking for in the ellipsoid instead of the polyhedron. By the way, thatfs actually kind of a very cool idea right there, and ellipsoid actually is -- whatfs required to describe an ellipsoid? Whatfs the size of a data structure in RN? What do you have to describe an ellipsoid? Therefs lots of different ways to do it? What do you need?

[Student:]Matrix and a vector?

Matrix and a vector. And a matrix is N squared over two, and a vector is like N, so -- in fact the matrix is like N and plus one over two. Itfs N squared over two. Thatfs the answer. So the number -- to describe an ellipsoid, the data structure for an ellipsoid requires about N squared over two elements. Oh, letfs see. Let me ask a couple more questions. Oh, and an ellipsoid is an interesting set. Theyfre very widely used in RN, for example, if you do statistics or anything like that, itfs sort of the first thing that gives you some direction. So letfs just talk about localization sets just for a minute.

Herefs one: bounding box. So you have a box. Someone says to you during a calculation, gAre you doing navigation?h and you say, gOkay.h And someone says, gHow accurate are you?h Youfd say, gWell, give me plus minus two meters east west plus minus north south in elevation, such and such. Plus minus eight meters or something.h

Thatfs a bounding box. Widely used. How many -- how big is the data structure required to describe a bounding box? An RN. Itfs two N. Itfs an L vector and a U vector. Thatfs it. So thatfs two N. Okay, so thatfs -- these are at the simple methods, right? Herefs an even simpler one. How about just a ball? What do you need to describe a ball?

[Student:]N plus one.

N plus one. You have to give the center and a radius, so itfs N plus one. So these are order N data structures that describe geometric sets, and they have uses. They have plenty of uses. Actually, for most people this is the simple -- they shouldnft be made fun of. Theyfre extremely useful when somebody says, gHow are you estimating the velocity of that vehicle?h and you can say, gPlus minus .1 meters per second.h

Everybody understands that. It makes total sense. An ellipsoid is already the first sophisticated thing. You see it in statistics because you talk about confidence ellipsoids, and what it captures is in statistics correlations. So it allows you to capture the idea that you could know X plus minus a meter, Y plus minus a meter, but for some weird reason, you know, X plus Y to ten centimeters. Thatfs this kind of ellipsoid, right? So thatfs what an ellipsoid does. Thatfs what an ellipsoid gives you. So youfre into the N squared things.

How about a simplex just for fun? Just roughly whatfs the data structure? Think of the simplex. Not a unit simplex, a general simplex. Convex hold and plus one points. I just gave it away. Itfs N squared, roughly. Then it turns out you have to adjust for that because theyfre symmetric. Itfs order N squared. Itfs actually a big jump when you go from an order N to an order N squared data structure described geometric set. You actually go from not the inability to universally approximate to ability to universally approximate.

Universally approximate means you can -- I can give you any old convex set, and you give the inner approximation of whatever data structure you choose that has some bound that says that if give an outer one, if you shrink it, it lies inside. Ellipsoids do -- bounding boxes do not do that because you make a little razor thin thing that goes at a 45 degree angle, and youfre in big trouble because that bounding box is huge, and you have to shrink it infinitely spar before it fits inside. But an ellipsoid, you have a bound. We did it last -- or we saw it squared in, or whatever. N is the factor for an ellipsoid. Squared N of the symmetric. Okay, lets go on, itfs just an aside.

So herefs whatfs going to happen. You know -- the idea is that you have an ellipsoid to summarize your ignorance. You know the optimum point is a current ellipsoid. Now the nice thing about an ellipsoid is therefs no long discussion about centers. Itfs sort of like an interval, an ellipsoid. So you can say, gWell, letfs calculate the analytic center of an ellipsoid. Letfs calculate the CG. Letfs calculate whatever you want.h

Theyfre all the same. In fact, if you have a center of an ellipsoid and itfs not the center, then Ifm deeply suspicious of your definition of center. So the point is there is no real discussion there. Therefs just the center of an ellipsoid, and you evaluate a sub-gradient at that point. And what you do -- that tells you instantly of a cutting-plane. So what happens is you know that your optimum point -- youfre in an ellipsoid. You have sliced off a half-plane, and you have a half ellipsoid. And now you know -- now, if you did this a standard cutting-plane method, youfd calculate now -- by the way, you have a half ellipsoid, and you start about the center. Now the center is varied.

Therefs an analytic center. Therefs a CG. Then you do it two steps, and you have now a set, which is an ellipsoid sliced by two planes, and thatfs -- so in fact, therefs another step that goes like this, and this is the main point. Herefs what you do. You have a half ellipsoid, and in order to preserve constancy of the data structure, youfre now going to do something thatfs equivalent to constraint dropping or whatever. Youfre gonna set E-K plus one be the minimum volume ellipsoid that covers your half ellipsoid. Okay?

So step four -- step three is where you get your knowledge, your ignorance decrease. So this is ignorance decrease, and in fact, by the way, how much does the volume go down between E-K and this localization set?

[Student:]Factor two N?

Yeah, a factor of two. If itfs a neutral cut, if itfs a deep cut, itfs more than a factor of two. So in step three you get at least one bit. In other words, log two of the volume of the localization set, and step three goes down by at least one. The worst thing that could happen is your ellipsoid is cut in half. No matter how you cut an ellipsoid, every plane going through the center of an ellipsoid cuts the volume exactly in half. Your volume goes down exactly by half here. Now, in step four your volume goes up. So four is actually an ignorance increasing step, and then therefs just a big drum roll to find out whether or not the ignorance increase in step four is more or less than the ignorance decrease in step three.

Thatfs basically the method. Yeah?

[Student:]How are we finding that minimum volume ellipsoid? Are we keeping track of half-planes?

No, Ifm gonna show you. Therefs gonna be just a formula for it, yeah, worked out by some Russians. The basic one is simple, but they did things like two cuts, and they actually had formulas for deep cuts, and parallel cuts, and crazy things. And then you get into some analytical formulas for those. Those are formulas that believe only a Russian person would work out, I believe. But there are formulas for it. But this one is gonna be simple, and I think youfre gonna work it out because wefre gonna stick it on the homework. Do we have an exercise on that? We just calculate the minimum volume ellipsoid that covers a half ellipsoid.

[Student:]We have one on that.

Oh, we do? Okay, but not yet assigned?

[Student:]No.

How convenient. What do you know? So herefs the picture. Picture goes like this. Here is your ignorance at the K step. Now, by the way, some points in this thing could not be optimal because remember, youfre cycling between steps that decrease ignorance and then increase it. So first you decrease ignorance. You call, you get a -- this is a neutral cut, like this, and basically, this half ellipsoid, we do not have to look in ever again. So actually, at this half step, we can say that the solution lies in this half ellipsoid. Okay? Our ignorance just went down by exactly one bit.

Now the next step is we calculate the minimum volume ellipsoid that covers it. Wefre gonna get an analytic formula for that. Here it is. Itfs this thing. And whatfs cool about it is things like this and this are very interesting. Thatfs just slop. We have now -- before this step, we know the solution cannot be in this little thing here. It cannot be there, and yet, wefre going to include it in our localization step as we move forward. Okay? So thatfs the bad part. Thatfs the slop.

Now compared to a cutting-plane method, you can state various things like localization set doesnft grow more complicated, itfs easy to compute a query point -- well, yeah because itfs actually part of the data structure of the ellipsoid, right? An ellipsoid is given by a point, the center, and some positive, definite matrix. Okay, fine. Itfs an access into a field of a data structure. The bad part is, of course, wefre adding unnecessary points in step four. Anyway, I wouldnft be here telling you about this if it didnft actually work. Wefll get to that.

So the first thing is ellipsoid method in R reduces it by section. Good, very good. So R, whatfs an ellipsoid in R? Itfs an interval. And then it says go to the center of that interval, and get a sub-gradient. It basically tells you the left or the right is your new localization center, and indeed you have gone down by one bit exactly. And now you have an interval, and you call a method that says please find for me the smallest length interval that covers this interval. So I can write that method, thatfs easy. In that case there is no slop. But this example back I just showed the visual example shows immediately. In R-2, theyfre slop. You are adding points into your localization set that you know for sure cannot be optimal.

Okay, so wefll get to the formula -- the update formula. Thatfs easy. Now it turns out that this -- the new localization set can actually be larger than this in diameter, but itfs always smaller in volume. This is how the drum roll ends, and itfs in fact more than that. It turns out that the volume of the new ellipsoid is less or equal to E to the minus one over two N time the volume of this one. Now, the good news about this number is itfs less than one. Thatfs the good news. The bad news is that itfs very close to one. Shockingly, that is enough to give you a polynomial time result, which wefre just gonna do in a few minutes.

So does that make sense? So compare this volume reduction factor. In CG, what number goes here? Oh, I already gave it away, itfs a number. Sorry. So what expression do you put in CG here?

[Student:]163?

163, right, which does not degrade, which first of all is a very respectable number. It is not .999. Thatfs number one. Number two: It does not degrade. The CG method does have a few problems. For example, the sub-routine that you have to call to calculate the CG is far harder than solving the original problem. But still, you can see what happened. So this is a very slim amount. MVE you get something that is much better. I forget. Itfs something like one minus one over N. Is that right? Itfs in the notes. You just have to look back on a lecture, but letfs say itfs something like that.

It degrades with MVE, but nothing like an exponential. So letfs look at an example and see how it works. So you canft see it, but therefs some sub-level sets of convex function here. Itfs not exactly polyhedral, so I donft know what it is. I probably logged some X for something like that. So you start here, and sub-gradient -- probably gradient in this case points that direction. And that says that this half circle cannot contain the optimum. I think the optimum is somewhere around here. Okay?

Thatfs your localization set, intermediate. This is half circle, and you take that half circle, and you cover it with the smallest volume ellipsoid that covers it, and thatfs this thing. Then you move over here. Thatfs this one. You go to the center. You call sub-gradient. You get this. This half ellipsoid has now been ruled out, and you have this half ellipsoid, and then you jump over here. And I think just looking at these, since this is obviously -- I reject the idea that there is, I mean -- there is no problem minimizing convex function in R-2 because you just grid things. Thatfs a non-problem.

But still, the fact where you have a non-problem, you can sort of visually see that itfs going to be slow. Itfs sort of a hint on these things, and I wonft trace through these, but thatfs the next three steps. You kind of get the idea. So now letfs talk about how you update an ellipsoid to cover half an ellipsoid. By the way, Ifm doing -- this is the formula for a neutral cut. So how do you cover a half ellipsoid with a minimum volume ellipsoid?

We also do deep cuts, and in deep cuts you have to ask how do you cover a cap? Not a half ellipsoid, but something where you cut a fraction off by a minimum volume ellipsoid. Therefs a formula for that. Itfs not too bad. But letfs look at this one where you update the ellipsoid this way, and I can -- let me just tell you why. This is going to be on your homework anyway, so Ifll just say a little bit about why itfs not that big a deal. Let me ask you this. I can change affine change of coordinates, and this problem is the same.

If I create an affine change of coordinates for an ellipsoid -- when I do an affine change of coordinates, all volumes get multiplied by the determinant -- the absolute value of the determinant of the transformation matrix, right? Therefore minimum volume -- I can transform coordinates, minimize the volume, transform back, and I got the answer because everything just got multiplied. So basically, I donft have to consider this a general thing. I can transform any half ellipsoid I like to half of the unitfs sphere, half of the unit ball just pointing upwards, or whatever X one bigger than, or X-N bigger than zero.

So that makes it simple. Now letfs just do this visually, and you have the homework problem. If you have half an ellipsoid, itfs completely symmetric in the remaining and minus one dimensions. In one dimension itfs got to be positive, but the other one. So that says that the ellipsoid you cover it with has got to actually be symmetric in those dimensions as well. Thatfs a standard thing wefve seen in where convex authorization. If the problem has symmetry, the solution must in convex authorization. It has to have the same symmetry.

By the way, that is absolutely false for non-convex problems. So, for convex problems, any symmetry in the problem, you can immediately assume that the solution will also be symmetric under that group of symmetries. Okay? So in this case, since you have a half ball that is sticking a cap like this, sticks like that. Then itfs symmetric in all of these other dimensions, and therefore that means that the P matrix is down to one variable or something. I think you have two variables to mess with. By the time youfre down to two variables, itfs calculus time. Itfs not a big deal. Itfs what you learn calculus for. Itfs the only thing you learn calculus for.

So here is the update. Oh, for N equals one, we do know the minimum volume ellipsoid that covers a half ellipsoid. Thatfs easy. Thatfs basically itself because an ellipsoid is an interval. A half ellipsoid is another interval, and I know the minimum length that covers an interval. So, okay, the minimum volume ellipsoid looks like this. Herefs the update. Let me just say a little bit about what the data structure is that wefre gonna use to describe. Lotfs of ways to describe ellipsoids, right? Lotfs of ways, or at least I know three or four. Image of uniball, inverse image of a uniball, quadratic function, and lots of things.

But wefll do it this way. Wefre going to parameterize it by the center, and a matrix P thatfs positive definite. In this formulation here, things like the volume is proportional to something like [inaudible] to the, I guess, square root, or something. So the bigger P is -- I guess the point is that roughly speaking, the bigger the P is, the bigger the ellipsoid. Did I get that right? Yeah because if P is big, it basically says P-N versus small, and you can go Z minus X can get very big before this thing runs up against a limit of one.

[Student:]What part of P is vague?

Well, yeah. Thatfs vague. What does it mean so -- I was being vague. When you say a matrix, a positive of a matrix -- P is big. When you pin somebody down, it can mean lots of things. It can mean big in determinant, big in diameter, big in the smallest Eigen Value, so I just mean hand waving. What Ifm doing. You can talk about which directions itfs big in, right? You can talk about the Eigen. So the Eigen values of P tell you -- for example, the condition number P tells you how non-isotropic or an-isotropic that ellipsoid is. It tells you if the condition number is like two. It says in one condition itfs twice as big as it is in some other. If itfs 10,000, it says something else and so on. All right.

So letfs look at it. Herefs your -- the new ellipsoid looks like this, and itfs really cool. Ifll give you another interpretation of this in a minute. So the new ellipsoid looks like this. The center -- of course, itfs very interesting. Itfs a step in the direction P-G. Ifm gonna talk about that. You step not in the direction G -- negative G. But in the direction P-G, so in a sort of change of coordinates you step in a different direction. Thatfs this. Step length is one over N plus one, and the new ellipsoid looks like this. And I want to dissect the different parts. Remember, P big in matrix sense roughly corresponds to E big.

So lets talk about the different parts. Letfs forget the scaling, and letfs focus on this. This -- by the way, what is this matrix here? Whatfs the rank of that guy?

[Student:]One?

One, rank one. Itfs an outer product. Itfs like P-G times the transpose, okay, with a constant in front. This is actually -- thatfs a rank one down date. In other words, you take a positive definite matrix, and you subtract a rank one thing. I mean, you canft subtract -- this thing is carefully -- well, by definition this cannot be positive. This is, again, positive definite. You know what that means? If I ask you about -- suppose letfs take the ellipsoid defined by P, and then the ellipsoid defined by that. What can you say about the second ellipsoid? What can you say about all the Eigen values of that matrix compared to the Eigen values of that matrix? You can guess.

[Student:]They must have gotten smaller.

Thatfs true. They all got smaller. This matrix is less than or equal to P in the matrix sense. It got -- it shrunk. Actually, it only shrunk in one direction. It actually shrunk in the direction P-G, or whatever direction this is. It only shrunk in one direction, okay? But it got smaller, therefore this is -- thatfs the good part. This is the good part where P gets smaller. Then you multiply it by this, and what happens to the ellipsoid? Now what happens to the ellipsoid when this happens? You increase it. So basically, I donft know if people have seen this in Kalman filtering, but basically what happens is -- again, this is only if youfve had these classes. If you havenft, then donft worry about this.

Youfd have two steps, right? What happens is first you take a measurement. So you take a measurement, and based on the measurement your estimate of the current state gets better. So your co-variance matrix goes down. It had to. You just got some information, and if you know how to process the information correctly, how could your estimate get worse? So your area co-variance matrix goes down, okay? Then the next that happens in sort of like a Kalman filter is you multiply. You propagate it forward by the dynamics, and add some unknown process noise, and what happens then is that in that step -- thatfs the dynamics update. Your ignorance increases.

And the hope is when youfre running this whole thing after many steps is that the amount of increases in ignorance -- in that case measured by a co-variance matrix, is overwhelmed by the amount of decreases in ignorance that come every time you take a measurement. So thatfs whatfs happening. You have a vehicle or something youfre tracking. Itfs being disturbed by something you donft know. Thatfs a process thatfs leading to increased ignorance at each step, but you get noisy measurements of it, and thatfs a process which if you process those measurements correctly can lead to decreasing ignorance.

This is the same thing. Thatfs the decrease, and the decrease came from kind of a measurement. If you want to call this a measurement, well you can. Thatfs a measurement, and then thatfs your slop, so thatfs how this works. I can actually -- let me give another interpretation of this. Anyway, youfre gonna prove this formula, so herefs what Ifm gonna do. Ifm gonna write down an interpretation of that, and once you see this interpretation, you donft need to know anything else. So itfs this. Let me see if I can -- I just want to interpret the step.

So this is how it goes. You have an ellipsoid like this, and herefs your point. And you get a sub-gradient, and letfs say the sub-gradient points this direction, okay? Thatfs the sub-gradient. Now suppose you were doing a sub-gradient method. Where would you step in the sub-gradient method? Youfd step somewhere along here. Now where depends on your step length on that step, and your step length can be as stupid as one over K, right? So youfd step in this direction. Letfs actually see where you step here. Where do you step here? Thatfs the question. Ifll just draw it geometrically.

It turns out what you do is you go in the direction -- you solve, actually, a problem. This direction that you step in solves this problem. Herefs how you get the direction. You minimize G transpose V, where V is a direction subject to V in your ellipsoid. Okay? So you go as far as you can in this direction in this ellipsoid, and in that case -- Ifm going to try to draw it, and Ifll probably get it all wrong, but anyway. It looks something like that, and so it might be here.

So in fact this is the direction -- if thatfs G, thatfs minus P-G. You know, roughly. I mean, forget the scale factor. This guy down here is minus G, and so what you see is --you can think of it as a distorted -- itfs like Newtonfs method. Itfs exactly like Newtonfs method. Instead of going in a negative sub-gradient, youfre twisting it by a positive definite matrix. Okay? This make sense? And you can check that this is -- that P-G is sort of this direction here. And therefs a beautiful way to interpret it, and itfs this. And itfs interpreted in change of co-ordinance.

So change of co-ordinance interpretation goes like this: Here is your ellipsoid at step N, or K, or whatever they call it. It doesnft matter. Here is your ellipsoid at some step, and what this says is -- you know, the ellipsoid tells you your ignorance. If itfs round, it says youfre equally ignorant in all directions, right? If itfs little pencil like things then it means that you have very good knowledge of the solution in some directions, and very poor in others, right? So what you do is you say no, and you change co-ordinance. And by the way, you change co-ordinance in the original thing by multiplying by P to the half.

So you use co-ordinate Z equals P to the half times X. You change co-ordinates to make your ignorance round. To make it isotropic so youfre equally ignorant in all directions. You change co-ordinates. When you change co-ordinates, you get a transformed G. Letfs call that G, I donft know, G -- G had been pointing some direction. Well, it doesnft matter. This is your new -- I em gonna call it G bar. Thatfs G, but transformed by this P to the one-half, or whatever. Okay? Now in this case, the question would be which way to step?

And so the correct step in a situation where your ignorance is isotropic -- so youfre equally ignorant in all directions. The correct step is to go minus G bar -- and itfs even funnier than that. Itfs basically divided by N plus one. This constant step like whatever N plus one. Thatfs it. Thatfs what the ellipsoid method is. The original discussion of ellipsoid method, which was, I guess, by Shore, had this name. In fact, it had a very long name Ifm trying to remember because itfs really funny when translated into English. Itfs sub-gradient method with space dilation in the direction of the gradient.

So this is space dilation because when youfre changing co-ordinates -- and then, by the way, the dilation is only in one direction in each step because when you do just a rank one update, youfre actually just scrunching space. Actually, youfre expanding it. Well, you shrink the ellipsoid, and that has equivalent in the change of co-ordinates of accentuate of dilating space in the direction of the sub-gradient.

So when you look, if you were to go to Google or to look at some of these early Russian books from the e60s and e70s -- some of which are actually in English and are superb books, youfd have a -- instead of ellipsoid method, youfd hear ellipsoid method with space dilation in the direction of the -- and various other things translated like that. This make sense? The thing you donft do in the sub-gradient method that you do do in ellipsoid is once you step this way, this ellipsoid gets shrunk.

You learn about stuff in this direction so you shrink a little bit, and you re-pull it apart. You do a change of co-ordinates to re-balance or isotropize your ignorance. Thatfs definitely not a word in any language. Make it isotropic. This make sense? So this is the picture. So in some senses whatfs funny about this is itfs a little bit like Newtonfs method. Because if someone says, gWhatfs Newtonfs method?h and you can write down some formulas and stuff, and they, gWell, why would anyone want to do that?h and you can blabber on and on.

But if someone says, gYeah, but whatfs the idea of Newtonfs method?h you can say that idea is that the gradient method, although itfs the first thing you could think of -- itfs greedy, and it might look like a good idea to go downhill the fastest way that way, but it might turn out that you should really be going about 45 degrees over that way, or more commonly, 89 degrees that way. And someone saying, gWhy?h and thatfs because you draw a valley and all that. And then you say that Newtonfs method is basically the gradient method applied after a change of co-ordinates makes the curvature locally isotropic. Thatfs what it is.

So the one case when greedy is good is when your ignorance or function has kind of an equal curvature in all directions, and this is a sub-gradient method with this. In fact, people have a beautiful term for these things. Itfs called variable metric. The metric tells you about the topology of the space, so you would talk about how Newtonfs method is a variable metric, gradient method. And in fact, youfd talk about [inaudible] as a variable, metric, sub-gradient method. It has this other interpretation, and so on.

The stopping criterion is pretty simple, and the way that the stopping criterion -- let me just draw that over here, and then let me tell you something embarrassing about the stopping criterion. So here is your current ignorance level, and suppose I give you a sub-gradient like that. Well, if you were gonna do another step, youfd cover this with an ellipsoid, and that would be your next point. And actually what youfd do -- now you know geometrically what youfd do. Youfd solve the LP of going as far as you can in that direction here, and in fact that would give you to this point, right?

So in fact your next step direction, now you know how to construct it, is here. And then the step length is somewhere along here, given by some formula. But youfre not gonna do that. Youfre gonna terminate, and what you do is you stop, you send a signal to this process, and you say, gDone. Time is over. Give me your current point.h And theyfd say, gPlease give me a lower bound on how far you are from optimal.h

Well, what you do is this. You -- of course you have this. This is just your basic formula for -- everything is based on this formula. Itfs the definition of a sub-gradient. Everything is based on that. So what you do is this. X star is in this ellipsoid. The ellipsoid is a localization region. Therefore, this thing couldnft be -- has to be bigger than or equal to the infimum of this linear affine function here over the ellipsoid, like that. It just has to be. You can just analytically work this out. I mean, what the worst thing is. In fact, the worst thing is -- in fact, literally, what youfre doing is youfre solving this formula here.

Youfre calculating this point, and then when you put that back in -- this just has an analytical formula. Itfs this. So itfs absolutely beautiful. Square root of G transpose P-G is actually a guaranteed sub-optimality bound. Couldnft -- and itfs absolutely beautiful. Do you know what it is in this transformed space? Itfs this. Itfs the norm of the sub-gradient in the current co-ordinate system if you change co-ordinates. It kind of just makes beautiful sense, and itfs a guaranteed sub-optimality. It makes sense because if someone walks up to you on the street, and you say, gListen, consider a unit ball.h Thatfs kind of your standard ignorance set.

You say, gI have a unit ball. I evaluated the sub-gradient at the origin of a function, and I got this. I know the minimum is somewhere in the unit ball. How far could I be off?h You get this. Itfs the norm of G. Thatfs how far you are off. Okay, so itfs a beautiful stopping criterion, and especially because I think you calculate that as a side calculation anywhere. So you have to calculate this anyway. You calculate it right here. So basically, you calculate this. If itfs less than a threshold, youfre out. Otherwise, you update.

Okay, and I do have to tell you one thing about this. Well, herefs the ellipsoid algorithm. Ifll show you the whole algorithm. I have to admit something about it. So you start with an ellipsoid containing X star, you know, typically in the same way an ACCPM might be some box or something. You know, this might typically be a ball of radius capital R. Thatfd be very common. Okay, herefs what you do. You evaluate a gradient. If the gradient in the scaled norm is less than epsilon, you return X -- and thatfs actually certified. Therefs nothing fuzzy about that at all.

Otherwise you update the ellipsoid like this, and you repeat. Thatfs the ellipsoid method, and now I have to tell you the truth. No, itfs not the truth. Wefre not lying. It is not know, as far as I know, and I spent a week last summer with a bunch of people from Moscow and Kiev in the e60s. They were all there. Enough of them spoke English, so everything was cool. There was a lot of vodka, so that was on the other side, but itfs not clear. Anyway, they claim the following: There is no proof that the exit criterion to will actually be satisfied.

So therefs no reason to believe it. So the only actual stopping criterion is the one that comes from the complexity theory. Actual means that you can absolutely prove that it will be reached. However, this works invariably in practice. I think we already talked about this, so we already -- okay. So herefs an example of ellipsoid method. This is our now famous ellipsoid method, and you can kind of look and see how itfs working. Each step is ordered in N squared, or something like that. Letfs go back and see what the ellipsoid step is. Yeah, it looks to me like itfs ordered N squared. Everybody else seeing N squared here for the ellipsoid?

The numerical update, I think, is N squared. The reason itfs N squared is -- I donft know. Here, you have to write all the entries of P out, so therefs N squared right there. And other than that, I donft see anything fancy except Ifm seeing [inaudible] vector multiplies. So itfs order N squared. This just shows kind of how it works slowly, and so on. This is the lower bound, which is indeed getting better. So I think what wefll do is wefll quit here, and wefll sort of finish this up next time, which will be next Thursday.