Blog for Math 340, Fall 2014 September 3: Classes start. WE BEGIN TOPIC 1: read the supplemental article "Matrix Games and Poker" and look at the matrix games in Washburn's book to which "Matrix Games and Poker" refers. September 8: How to compute the value of a 2 x 2 matrix game. Septmeber 10: Minmax and maxmin, Alice announces versus Betty announces, dominant strategies, irreducible games, second remarkable theorem and the 2^(52) x 2 game, exchanging Alice and Betty, symmetric games (their values). September 19: Begin simplex method September 22,24: Simplex method: pivots, basic and non-basic variables. September 24: Shall look at (1) an unbounded example: max x_1 + x_2 s.t., x_1 <= 6 + x_2 , x_1,x_2>=0; (2) an infeasible example: max whatever, s.t. x_1 <= -2 , x_1>=0; (3) a feasible example that requires two phases: max (whatever), s.t. x_1 >= 2, x_1 <= 6, x_1,x_2>=0. Examples (2) and (3) illustrate Chapter 2, Section 3: "Initialization." In all examples: the simplex method should give "proofs" of correctness. September 29: Dealing with degenerate pivots, via the perturbation or lexicographical method. Remark: Game theory solvers usually have degenerate pivots. The perturbation/lexicographical method takes care of degenerate pivots and of ties in the leaving variable, and zeta (the objective) always increases in terms of constant + epsilon1 * constant + epsilon2 * constant + ... October 8: We use the simplex method (which shows that any feasible and bounded LP has a final, feasible dictionary where the zeta row has all negative coefficients), to show that in an m by n matrix game with m > n (we took m=7 and n=2 in class), Alice has an optimal strategy where she plays at most n rows. October 10: Begin Chapter 5 of Vanderbei: Duality Theory. - To every linear program there is a dual linear program - Namely: max c.x subject to Ax <= b and x >= 0 (so x,b,c are vectors, A is a matrix, and c.x means the dot product of c and x) has dual linear program: min B.y subject to A^T y >= c and y >= 0 , or, in standard form: max -B.y subject to - A^T y <= -c and y>= 0. In other words, to change from primal (original) to dual we take (c,A,b) and substitute (-b,-A^T,-c). Remark: Vanderbei does not use the above vector notation, which is conceptually very simple (I have no idea why he omits this...). Vanderbei's text writes the whole thing out longhand... (See Section 5.2 of Vanderbei.) We get some immediate conclusions: any dictionary for the original problem has a dual dictionary for the dual; the dual of an optimal dictionary is an optimal dictionary for the dual. Hence: an LP that is feasible and bounded has a dual which is feasible and bounded with max c.x equalling min b.y . Remark: the dual LP expressing Alice's optimal mixed strategy is just the LP expressing Betty's optimal mixed strategy. Proof: Assume that all of A's entries are positive. The LP for Alice's best strategy is max v subject to p^T A >= [v v ... v], p_1 + ... + p_m <= 1. In standard form this is max v s.t. A' x <= b, x >= 0, where x = [v p_1 p_2 ... p_m], and A' is given in block form by A' = [ e A^T ] [ ] [ 0 1 1 ... 1 ] e is all 1's, and b is all 0's except a 1 in the final row. Now we dualize. We remark that if A does not have all positive entries, then we have to use v_1 - v_2 instead of v, and have to write p_1 + ... + p_m is both >= 1 and <= 1. This works similarly. --------- Complementary slackness: The dual problem gives an upper bound for the LP: max c.x s.t. Ax <= b and x >= 0 essentially by multiplying by a non-negative column vector, y, on the right: Ax <= b implies that (Ax).y <= b.y for any y. It follows that if y* is an optimal solution for the dual problem, then (Ax).y* <= b.Y* must hold with equality when x=x* is optimal; hence (Ax*-b).y* = 0. For any optimal solution, x* and y*. In other words: If x* and y* are optimal solutions, then (Ax*-b).y* = 0, and hence if a y* entry is positive, then then corresponding slack variable entry of w* = Ax*-b must be zero; similarly if a value of w* is positive, then the corresponding entry of y* must be zero. Similarly for x and the slack variables of the dual linear program. Conversely: if these "complementary slackness" conditions hold, then x* and y* are optimal solutions. Note: We can use "complementary slackness" (in "non-degenerate cases") to determine the optimal dual strategy from a guess for the optimal primal strategy. Special cases: (1) Our standard LP: max 4x_1 + 5x_2 s.t. x_1+x_2 <= 5, x_1 + 2x_2 <= 8, 2x_1 + x_2 <= 8, and x_1,x_2 >= 0. (2) Game theory: if Alice has a mixed strategy p, such that p^T A >= [v v ... v] for some v, and if Betty has a mixed strategy q such that A q >= [w w ... w]^T for some w, and if v=w, then p and q are, indeed, optimal mixed strategies. Example: (1) Let's say we guess that x_1=2, x_2=3 is an optimal solution for our standard LP. Then we have x_1,x_2, and w_3 > 0 in this optimal solution (w_3 being the slack variable w_3 = 8 - 2x_1 - x_2 , which at our guess has the value 8 - 2(2) - (3) = 1 > 0 ). Hence for the dual we expect that z_1=z_2=0 and y_3=0, for the dual LP min 5 y_1 + 8 y_2 + 8 y_3 s.t. 4 <= y_1 + y_2 + 2 y_3 , and 5 <= y_1 + 2 y_2 + y_3 (and y_1,y_2,y_3 >= 0, as usual) (and where z_1, z_2 are the slack variables corresponding to the two inequalities in the usual fashion.) So z_1 = 0 means that 4 = y_1 + y_2 + 2 y_3 , z_2 = 0 means that 5 = y_1 + 2 y_2 + y_3 , and y_3 = 0 means that we have 4 = y_1 + y_2, 5 = y_1 + 2 y_2. Solving the last part gives y_1 = 3, y_2 = 1. We can check that this is dual feasible, so we are done. (2) Let's say we think Alice will play [ 1/2 1/2 ] in the game [ 1 4 9 16 ] A = [ ] [ 16 9 4 1 ] Then we see that Betty will choose columns 2 and 3. Is this complementary slackness? October 27: Started other applications, especially: Weighted Bipartite Matching (which Vanderbei calls the Assignment Problem, Section 15.2 of Vanderbei's textbook). First we formulate the "relaxation," maximize sum over i,j from 1 to n of c_{i,j} x_{i,j} where x_{ij} hopefully will be 0's or 1's, where x_{ij} = 1 means that person i will be matched with task number j. It is called the "relaxation" because the x_{ij} are real numbers which we can bound between 0 and 1 , but they could possibly have values that are reals numbers strictly between 0 and 1 (intuitively meaning that if x_{ij} = .4, then we have 40% of person i doing task j. We claim that if the assignment problem has all positive weights, we can write a linear program for this assignment problem where the final dictionary of the simplex method will have 2n basic variables, exactly n of which are slack variables and n of which are decision variables. Seeing this is a bit tricky... If all the c_{ij} are positive, we claim that we can write the constraints that person i does one task as: x_{i,1} + x_{i,2} + ... + x_{i,n} <= 1 we really want equality, but we claim that the positivity of the c_{ij} will mean that we will always want to play each "row sum" to a maximum of 1. We get n slack variables corresponding to the rows: wRow_i = 1 - x_{i,1} - x_{i,2} - ... - x_{i,n}. Similarly we get slack variables wCol_i = 1 - x_{1i} - x_{2i}- ... - x_{ni}. Using the fact that the sum of the row slack variables (wRow_i) is the sum of the column slack variables (wCol_i), we see that in the final dictionary we can't have all slack variables being non-basic, for this would mean that the basic variables do not have a unique representation in terms of the non-basic variables. Then we can use induction from there... Here we must use the fact that if A_B is the part of [ A | I ] that corresponds to the basic variables, then A_B is invertible. ---------------------- Start November 14 or 17: More linear programming without linear programming [meaning that we learn something about the simplex method just using the fact that A_B (above) has to be invertible, and/or other general facts not specific to a given linear program]: (1) What happens when we have a variable that could be positive or negative? (2) What happens when we replace an equality by an inequality? Note: (1) are (2) are dual: if (1) happens in the primal, then (2) happens in the dual and vice versa. Answer to (1): say we replace a variable, v, by the expression v1 - v2, where now we can say that v1,v2 are non-negative but we have used two variables instead of one. We note that the columns of the "big A" matrix corresponding to v1 and v2 are opposite in sign. Hence only one of them can ever be basic. Answer to (2): this gives two slack variables and two inequalities, but the sum of these slack variables is zero. Hence at most one of these two can be non-basic. ---------------------- LATER: MORE APPLICATIONS OF LINEAR PROGRAMMING MAYBE SOME ALGORITHMIC ASPECTS TOPIC 4 ON THE BLURB