Math 340 blog--comments on the lectures, mainly where we are in class.
First 2-3 weeks: Poker, Taxes, Other Games, ...
March 9: Duality Examples:
Alice vs. Betty: this is easy to see from an example. E.g.
A = [ 3, 4; 5, 2] (this means A is 2 x 2, first row: 3 4, second row: 5 2)
for Alice:
max v s.t. 3 x1 + 5 x2 >= v, 4 x1 + 2 x2 >= v, x1 + x2 = 1. (x1,x2 non-neg).
Claim dual given by multiplying first ineq by y1, second by y2, third by w,
to get
(3 x1 + 5 x2) y1 + (4 x1 + 2 x2) y2 + (x1 + x2) w >= v(y1+y2) + w,
So provided that y1+y2=1 we get
v <= x1 ( 3 y1 + 4 y2 + w) + x2 ( 5 y1 + 2 y2 + w ) - w <= -w
provided that 3 y1 + 4 y2 + w and 5 y1 + 2 y2 + w <= 0, which is
Betty's LP:
minimize -w s.t. y1+y2=1, 3 y1 + 4 y2 <= -w, 5 y1 + 2 y2 <= -w.
Note: we have taken some liberties. Such as
x1 + x2 = 1 has a multiplier w that can be positive or negative. To see
this from what we know, x1 + x2 = 1 becomes
x1 + x2 <= 1 and -x1 -x2 <= -1. So multiplying by w1 and w2 gives
(x1+x2) (w1-w2) <= (w1-w2), and left-hand-side is involved in variables,
so corresponds to writing
(x1+x2) w <= w.
-----------------------
Another duality example:
(1) Matching and pricing.
(2) Shortest paths in graph and maximum distance to pull apart.
Say have vertices {1,...,n} with road from i to j length d_{ij}.
Min sum_{ij} a_{ij} d_{ij} such that
sum_j a_{1j} = sum_j a{j1} + 1, sum_j a_{jn}= sum_j a{nj} + 1,
sum_j a_{ij} = sum_j a_{ji} for all i other than 1 and n,
Multipliers b_i, i=1,...,n:
want: b_i - b_j <= d_{ij}
max: b_1 - b_n.
This is longest positioning distance of vertex 1 from vertex n with
positioning of all vertices such that distance from i to j <= d_{ij}.
----------------------------
April 13: Data Fitting (Chapter 14 of Chvatal):
The curve fitting / data fitting problem is that we are given data
(x_1,y_1), ..., (x_n,y_n) and a linear model
y = a_1 f_1(x) + ... + a_k f_k(x),
and we try to find a_1,...,a_k to fit the data exactly or approximately.
This would give us the linear equations
y_i = a_1 f_1(x_i) + ... + a_k f_k(x_i), i=1,2,...,n
Alternatively the text and we will often change the letters to make it
look like linear algebra:
Ax=b
where A is a given matrix and b is a given vector, and x is a vector of
unknowns. Typically this system will not have an exact solution, and
so we may ask to minimize
| Ax-b |
in some norm. Linear programming can solve this in case of the "L^1" norm:
| v |_1 = |v_1| + |v_2| + ...
and the "max" or "L^infinity" norm
| v |_infinity or | v |_max = max over all i of |v_i|.
The "L^2" norm (or "Euclidean" norm) minimizer x of | Ax-b |_2 is
well-known, called the "least squares fit," and has many nice properties.
There are reasonable algorithms to find it. The best L^1 or L^infinity
fit is not nearly as nice, either algorithmically or in other properties,
but linear programming can tell us a few things.
Consider, for example, the L^infinity minimizer, x; it is the solution of
the linear program:
minimize z subject to
sum over j=1,2,...,n of a_{ij} x_j - b_i <= z, for i=1,2,...,m
sum over j=1,2,...,n of a_{ij} x_j - b_i >= -z, for i=1,2,...,m
Typically we expect m much larger than n, and a (unique) solution with
non-zero z,x_1,...,x_n. In that case these decision variables will be
in the basis of a final dictionary; hence there will be n+1 slack variables
that will be non-basic and therefore zero in the optimal solution.
This are points at which the difference between the data and model
differ the most, and in many cases there are exactly n+1 such points;
in approximation theory the differences often oscillate between z and -z.