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.