Pricing American Stock Options by Linear Programming
研究用线性规划求解美式期权定价的有限差分近似，对比单纯形法和内点法与投影超松弛法，发现单纯形法在参数变化时更稳健。
We investigate numerical solution of finite difference approximations to American option pricing problems, using a new direct numerical method: simplex solution of a linear programming formulation. This approach is based on an extension to the parabolic case of the equivalence between linear order complementarity problems and abstract linear programs known for certain elliptic operators. We test this method empirically, comparing simplex and interior point algorithms with the projected successive overrelaxation (PSOR) algorithm applied to the American vanilla and lookback puts. We conclude that simplex is roughly comparable with projected SOR on average (faster for fine discretizations, slower for coarse), but is more desirable for robustness of solution time under changes in parameters. Furthermore, significant speedups over the results given here have been achieved and will be published elsewhere.