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