Pricing American stock options by linear programming

We investigate numerical solution of finite difference approximations to Am erican option pricing problems, using a new direct numerical method: simple x solution of a linear programming formulation. This approach is based on a n extension to the parabolic case of the equivalence between linear order c omplementarity problems and abstract linear programs known for certain elli ptic operators. We test this method empirically, comparing simplex and inte rior point algorithms with the projected successive overrelaxation (PSOR) a lgorithm applied to the American vanilla and lookback puts. We conclude tha t simplex is roughly comparable with projected SOR on average (faster for f ine discretizations, slower for coarse), but is more desirable for robustne ss of solution time under changes in parameters. Furthermore, significant s peedups over the results given here have been achieved and are published el sewhere.