simplex attempt 3

Simplex Attempt 3 PhL 11.28.04 [ In this document, I review the previous Simplex 2 presentation, and then discover the idea of adding M to the matrix equation. I then do battle with Scheid's notation but don't get happiness with it. ] Review of #2 document. We start with a simple example where the feasible region is in E2 (a polygon which includes the origin), and there are three far boundaries so the co-space is E3 . This example is n=2 and m=3. We define some conventions for writing the equations which make the slack variables be directly interpretable as distances from their boundaries in the E2 space. We draw the most general polygon that fits into the mold of our sample problem. We think of the E2 variables as parameters, and the E3 space then has a 3x3 system that we can solve for the slack variables. We then study this mapping of E2 E3. Various properties are derived which probably apply to any linear transformation: points, lines and planes map into same. Distances and angles are not preserved, but convexity is preserved. We find that our polygon in E2 maps into a tilted polygon in E3 that lies in the first octant. Most of the points of this polygon (all but one in fact) lie on the "walls" in E3. The reason is that the walls represent the boundary lines, and only the origin vertex (x,y) = (0,0) is then not on a wall. We then show that you can move around the polygon from vertex to vertex by doing a specific sequence of variable swaps. That is, you exchange a variable in the E2 space with one in the E3 space. The reason this takes you on a tour of the vertices is this: a vertex is in fact a place where two boundary lines meet, and those two lines have variable names like (x,u). The vertex here is then has x=0 and u=0. So you are moving your E2 space origin from one vertex to the next. In the E3 space of the other 3 variables, we find that the Simplex table has simple unit vectors. Why do we get these unit vectors? In the original problem statement, each equation gets one slack variable, so in the starting position we do have 3 unit vectors in E3 which are for (u,v,w). If we take (x,y) = (0,0), we find that (u,v,w) = (3x3 identity)(cu,cv,cw), so the slack variables take their max values. Question " Why does a coordinate swap move a unit vector from one column to another? Answer: In our original system we had these equations, u = cu - au*x - bu*y v = cv - av*x - bv*y u = Mx + c (1) w = cw - aw*x - bw*y Our E3 variables are those on the LHS. Since these equations are solutions for those variables, in each equation the variable appears just one time with coefficient unity. That is the reason that we get the unit vectors in our matrix equation: (2) Now, when we "swap a pair of variables" what we really mean is that we are swapping one variable on the LHS of (1) for one variable on the RHS of (1). Consider y u. We are then looking for a new set of solution equations that have (y,v,w) on the LHS and (x,u) on the RHS. This means we have to somehow eliminate y so it does not appear anywhere on the RHS, and u appears in its place. We need to find an expression y = y(u,x). This comes from the first equation. I will do the general case soon. We then replace all the y's with this expression, and we then have our solution, which is y = x + u + => y - x - u = v = 'x + 'u + ' => v - ' x - ' u = ' w = "x + "u + " => w - " x - " u = " This is "after swap". Again, since these are solutions for the three variables on the left, we know that the three columns in the matrix (2) for these variables will have the unit vectors! Very good. So yes, a swap just moves a unit vector from the one column to another. If course data in the other columns is also altered. In the above case we now have: The altered data is in the columns that lie under the new "parameter" variable headings, because all the other columns have unit vectors. Now, let's try to add the M equation. I had M = - Ax - By + C (to be general say). We can just add this equation to the list above. Here: u = cu - au*x - bu*y v = cv - av*x - bv*y u = Mx + c (1) w = cw - aw*x - bw*y M = C - A*x - B*y It really is on a completely equal footing. Since we have a "solution" for M as well as the other three variables, the M column in the table or matrix will always be 0,0,0,1. Let's write this down: I like it! Now the unit vectors are extended to one more dimension because we have solutions of four equations. Now if we do a swap (but never swap M) between a variable on the left side and one on the right side of the little line, what will happen is the unit vector will move from the original cospace column to the column of the swapped out variable on the left. What numbers get changed in this process? The row fiddling is just a graphical method of solving the equations for the new variables, nothing more and nothing less. So look at the above equation and think about what will change if we swap y and u. I circle things that will get changed: We will first scale the first equation to make bu1, which changes all the other nonzero values in that row, so I circle them. Then we will add multiples of this first row to all the other rows. This changes the other rows only where the first row has non-zero values, so that accounts for the rest of the circles. The second column of course will end up being 1,0,0,0. So the answer is: a variable swap changes all entries in the "other" parameter columns on the left side (here, that is only the x column), and changes the entries in the formerly unit vector column ( that of the variable swapped out of the right, and finally the constants column on the right. Said another way, all columns change except the unchanged unit vectors. This is pretty reasonable, we are changing basis and we expect all vectors to have new components in the new basis. More on this soon. Now once we have done this swap, we are going to examine things when all the variables on the left are 0 and we hope that is a vertex in our En space. The above equations are then diagonal and we have the solution u = cu', v = cv', w = cw', M = C'. So the right column IS our solution at this vertex. Now how do we decide which columns or variable pairs to swap? I will answer that later. But what about the observation about the M solution. In the above example, suppose A and B are positive. We see this last equation as -Ax - By + M = C. Suppose we trying to minimize M. We can see that increasing x or y will do this. We could then benefit from swapping out either one of these because after the swap, our new coordinates on the left will be (x,u) say, and our test point will still be (0,0) so x=0, but we know that we will end up with some positive y value, so we know M will be smaller after this swap. So, there are several issues here. One is that we sort of look at the bottom row to see which variable on the left we would like to swap (perhaps one with largest + coefficient if we are trying to minimize M). But then we have to select a variable on the right to swap it with. We would like to do that in a way that moves us to a new vertex. I see how to do that in our test problem, but not in the general case. OK, here is the rule on picking the variable on the right side to swap with. We want to pick the one that is going to first "hit a boundary" as we increase y. Look again at our equations, u = cu - au*x - bu*y v = cv - av*x - bv*y w = cw - aw*x - bw*y As we have x = 0, and we increase y, which one hits first? u = cu - bu*y = cu(1 - y/y1) y1 = cu/bu v = cv - bv*y = cv(1 - y/y2) y2 = cv/bv w = cw - bw*y = cw(1 - y/y3) y3 = cw/bw These are the values where each equation will hit the limit, like u=0. Suppose y1 is the smallest. Then we will hit u=0 in the first equation with y1. In the second, (1 - y1/y2) will be >0 so we end up with some positive v and so on. So the rule is this: compute the ratios shown on the right and pick the smallest. That tells you which variable to swap. And you will end up at the u=0 boundary with x = 0, so you will end up at a new vertex (I think). Modification of this rule: if the yi ratio value is infinite, then for that variable increasing y has no effect, so we ignore it. And if yi is negative, increasing y increases the variable, so we are never going to hit the u=0 boundary. We are assuming here that the three cx are > 0. So we only consider ratios which are positive and finite. That is how the rule needs to be modified. How would this rule work in my problem: I start off at v1. I think about increasing y. With x = 0, I can see clearly that I am going to hit the u line before I hit the w line and then the v line, so u is my swap choice. And I do get then to v5. Now, when you find the smallest ratio, that row is the variable you are going to swap with so that location is where you want to cause a 1 to appear. This point is called the pivot. In the blue book example, her first swaps out z with v, then swaps y with w. Since the bottom row numbers are all positive now, he says no more swaps will help. How do we know that? On page 67 bottom, he knows that increasing x will worsen his situation due to the sign. Notice that, at this point, columns x, v and w are now "left side" columns, so we are thinking now about the point (x,v,w) = (0,0,0) and this is a certain vertex. The variables are all zero at this vertex. In doing another swap, we can only increase one of these three. But increasing any of them hurts, so we are done! So yes, I like his rule for doneness. Once you get to a vertex such that increasing any of the LHS variables hurts, you know you are done! Thus, you don't really have to exhaust all the vertices. Now what on earth is Scheid doing in his writeup? He adds the slack variables. Now I see what he calls them xn+1 through xn+m, because he wants them to be on an equal footing with the other ones. Compare to x,y and then w,u,v. Once Scheid has his matrix with the m unit vectors on the right, and the filled columns on the left. He rewrites the entire matrix equation in column vector notation. The n left variables are the physical ones we start with, the m rightmost variables are the slack variables. Now for the starting point I would have taken the first n variables to be 0, as we set (x,y) = 0. However, he instead takes the last n variables to be 0. In my example, that is like taking (v,w) = 0. That is OK, it is still a vertex somewhere. Then the first m variables are nonzero and we get the simplified equation with the zeroed out terms missing. This would be my 3x3 system in (x,y,u). It is certainly possible to write H in terms of the (x,y,u) variables. He has an mxm problem with a selected m active coordinates, so H is a function of the m active coordinates. So equations (1) and (2) are just fine. In (3) he says he can write any column vector as a lincom of the m independent ones, and he calls the coefficients vk which is fine by me. Now I think I better understand. When we writes "include a piece pxk for k > m" : the leftmost m variables are active so are on the "right side" of my usual picture. The "left side" variables in my picture are now all zero. We want to think about increasing just ONE of them, the way blue book increases z from 0. We now come to the infamous equation (5). It still is unclear, so let me now try to rewrite Scheid the way I would do it. I will go ahead and set the last n variables to 0 as he does, even though some of these are slack variables. This corresponds to picking a vertex out in the volume somewhere far from the origin. Any vertex is OK to start. I agree with (1), and I agree with (2). I agree with (3) . Equation (4) at this point is just a definition. But suppose I add my last row to his matrix, it would look like this: c1 c2 ........... cn+m then M in the variable vector, and some constant bm+1 on the right. This would imply that we have x1c1 + x2c2 + ..... + xn+m cn+m + M = bm+1 Now if the last n variables are 0, we get x1c1 + x2c2 + .... xmcm + M = bm+1 so we identify H1 = bm+1 - M. I am unclear as to why he puts the 1 subscript on H. Now again we must face up to equation (5), the great barrier! Look back at (1) which is our matrix equation with the last n x's variables set to 0. There is some vk vector of course, so suppose we "move out" into our feasible space by moving p units away from our starting vertex in the "k" direction. Then yes, we are just adding a term to equation (1). But look at what we have added: p vk = p [ !Syntax Error, I vik vi ] = amount added on the right of equation (1) We have displayed the amount added as a sum of m pieces, each associated with one of the basis vectors. So if we subject this off, then (6) is exactly the same as (1). Here is what equation (1) was saying: !Syntax Error, Ixi vi = b (1) So do this !Syntax Error, Ixi vi - p vk + p vk = b which says !Syntax Error, Ixi vi - p !Syntax Error, I vik vi + p vk = b which says !Syntax Error, I(xi - pvik) vi + p vk = b (5) So we are over that hurdle! At this point, we have m+1 columns active in our matrix, but he is going to get rid of one of these columns by choosing p such that (xi - pvik) for some i. So what exactly is happening here? We have the rightmost n variables = 0, the leftmost m are active. We are exploring activating one of the zero variables. If we turn it on by amount p, then we have to reduce the coefficients of the other basis vectors exactly as shown. One of our assumptions is that we insist that ALL n+m variables are 0. Now why do we require that (xi - pvik) 0 ? I know that we want xi 0 for all i. Let's rewrite (5) in this way !Syntax Error, Ixi'vi + xk vk = b Who says that the feasible space must have positive coefficients? Well xi' is the value of the xi coordinate after we add our vk piece. As we move in the k direction, all the other coordinates are going to maybe decrease, and we have to make sure we don't hit the wall on any of them. So we require xi' 0 because we require that the value of the vi variable be positive. So in our current framework, we select p = min (xi/vik) for only vik > 0. Notice that the vik are not yet displayed in any matrix. I think he should have used some other letter for vik such as dik . For example, I know that v11 = 1 and v22 = 1 from the expansion of unit vectors equation, but a11 1, etc. But fine, I will stick for now with his vik notation. ( it causes too many v's to be flying around! ) I agree to select p as in his equation (7). Now lets go back to equation (4) and see where it is coming from. If we included the "last equation" in our matrix, we would say this, as noted above. x1c1 + x2c2 + ..... + xn+m cn+m + M = bm+1 Now if the last n variables are 0, we get x1c1 + x2c2 + .... xmcm + M = bm+1 I can rewrite this as -M + bm+1 = x1c1 + x2c2 + .... xmcm = H1 Now as we turn on our k basis vector by amount xk, what is going to happen to the above equation, which is our last matrix equation. I am inclined to try this: x1c1 + x2c2 + .... xmcm + pck - pck = H1 Then we somehow think maybe the -xkck term can be written so this becomes true x1'c1 + x2'c2 + .... xm'cm + pck = H1 and this would say that !Syntax Error, I(xi - pvik) ci + pck = H1 but this also disagrees with (6) unless hk = 0. ******************************* Here I just repeat the last attempt with slightly different language, and conclusion is the same. NOW, imagine this equation as the bottom equation in his matrix, but not shown by him. We make all the vectors one longer with last components called ci. Then the transformation shown above, !Syntax Error, I(xi - pvik) vi + p vk = b takes this form on the last row, (nothing ever changes the rightmost unshown M column) !Syntax Error, I(xi - pvik) ci + p ck + M = bm+1 or !Syntax Error, I(xi - pvik) ci + p ck = H1 This looks like (7) but only if hk = 0, so something is wrong! ********************************************************** OK, the battle continues to rage concerning Scheid (4) and (6). What happens if I insert the expression (4) in for hk in (6) ? hk !Syntax Error, Ivik ci - ck (4) !Syntax Error, I(xi - pvik) ci + pck = H1 - phk (6) Combining these I get !Syntax Error, I(xi - pvik) ci + pck = H1 - p [ !Syntax Error, Ivik ci - ck ] Cancel the sums involving vik and we end up with !Syntax Error, Ixi ci + pck = H1 - p [ - ck ] which says !Syntax Error, Ixi ci = H1 So why does it work here but not when I did it before??? I think I made the wrong association with M. Given that we strictly define H1 as shown, let's compare (6) to my "last row equation" , !Syntax Error, I(xi - pvik) ci + pck = H1 - phk // (6) !Syntax Error, I(xi - pvik) ci + p ck + M = bm+1 // my last row equation I now make this connection: -M + bm+1 = H1 - phk Let's now replace "my" variables M and bm+1 with a new variable I will just call H. H = -M + bm+1 = H1 - phk So now we see that H1 was the value of H for our initial vertex selection! And if hk > 0, then our proposed motion in the k direction is helping us! Scheid's discussion is missing the mention of a variable like H and that is confusing as hell! Now, let's take a closer look at this "last row" business. I had this to start with x1c1 + x2c2 + ..... + xn+m cn+m + M = bm+1 as my last row, but all c's are zero after m, so the last row contracts to this x1c1 + x2c2 + ..... + xm cm + M = bm+1 Now, if we go a bit in the k direction, this row becomes this !Syntax Error, I(xi - pvik) ci + pck + M = bm+1 which we can write as !Syntax Error, I(xi - pvik) ci + pck = -M + bm+1 = H I think I now see what he is doing. We want to write H in a form that shows it is decreasing, so we write H = H1 - phk where we separate out the original H1 and define hk buy THIS equation. Then we solve and find what hk turns out to be. Suppose Scheid had chosen the last m columns to be his basis vectors, the ones that have unit vectors in them. And suppose he had chosen the first n variables to be the ones that are initially zero. Then turning on a new variable k, we would have k in this first set. What could we then say about the hk? (1) for j in the last columns of unit vectors, we have hj = vjjcj - cj = cj- cj = 0, and this agrees with my usual "starting position". His approach is just really ugly. Here is my rewrite: (1) Write the matrix as he has it, select the last m columns as the basis vectors, and choose the starting vertex to be the first n variables. Then equation (1) would become !Syntax Error, Ixi vi = b // because the first xi are 0 (1) Similarly, we would have that H1 = !Syntax Error, Ixi ci = 0 // again, because the first n xi are 0. (2) Then for (3) we would have this vj = !Syntax Error, Ivij vi j = 1 to n+m (3) Now what does the new hj equation look like? I think this: (first vij index goes over basis vectors) hj = !Syntax Error, Ivij ci - cj // notice same sum appearing (4) Now if j is in the range of the unit vectors, which is j = n+1 to n+m, we get vij = i,j j in n+1 to n+m and in this case we get hj = !Syntax Error, Ii,j ci - cj = cj - cj = 0 which agrees with the idea that in your initial stance, hj = 0 in the unit vector bottom rows. On the other hand, for j in the first n columns we have vij = aij j = 1 to m i = n+1 to n+m so we would find then that hj = !Syntax Error, I aij ci - cj