In this research effort, we study three exterior penalty function approaches for solving linear programming problems. These methods are an active set l2 penalty approach (ASL2), an inequality-equality based l2 penalty approach (IEL2), and an augmented Lagrangian approach (ALAG). Particular effective variants are presented for each method, along with comments and experience on alternative algorithmic strategies that were empirically investigated. Our motivation is to examine the relative performance of these different approaches based on the basic l2 penalty function in order to provide insights into the viability of these methods for solving linear programs. To test the performance of these algorithms, a set of randomly generated problems as well as a set of NETLIB test problems from the public domain are used. By way of providing a benchmark for comparisons, we also solve the test problems using CPLEX 6.0, an advanced simplex implementation. While a particular variant (ALAG2) of ALAG performed the best for randomly generated test problems, ASL2 performed the best for the NETLIB test problems. Moreover, for test problems having only equality constraints, IEL2, and ASL2 (which is a finer-tuned version of IEL2 in this case) were comparable and yielded a second-best performance in comparison with ALAG2. Furthermore, a set of problems with relatively higher density parameter values, as well as a set of low-density problems were used to determine the effect of density on the relative performances of these methods. This experiment revealed that for linear programs with a high density parameter, ASL2 is the best alternative among the tested algorithms; whereas, for low-density problems ALAG2 is the fastest method. Moreover, although our implementation was rudimentary in comparison with CPLEX, all of the tested methods attained a final solution faster than CPLEX for the set of large-scale low-density problems, sometimes as fast as requiring only 16-23% of the effort consumed by CPLEX. Average rank tests based on the computational results obtained are performed using two different statistics, that assess the speed of convergence and the quality or accuracy of the solution, in order to determine the relative effectiveness of the algorithms and to validate our conclusions. Overall, the results provide insights into selecting algorithmic strategies based on problem structure and indicate that while this class of methods is viable for computing near optimal solutions, more research is needed to design robust and competitive exterior point methods for solving linear programming problems. However, the use of the proposed variant of the augmented Lagrangian method to solve large-scale low-density linear programs is promising and should be explored more extensively. / Master of Science

This thesis is concerned with the investigation of numerical methods for the solution of the Hamilton-Jacobi-Bellman (HJB) equations arising in European and American option pricing with proportional transaction costs. We first consider the problem of computing reservation purchase and write prices of a European option in the model proposed by Davis, Panas and Zariphopoulou [19]. It has been shown [19] that computing the reservation purchase and write prices of a European option involves solving three different fully nonlinear HJB equations. In this thesis, we propose a penalty approach combined with a finite difference scheme to solve the HJB equations. We first approximate each of the HJB equations by a quasi-linear second order partial differential equation containing two linear penalty terms with penalty parameters. We then develop a numerical scheme based on the finite differencing in both space and time for solving the penalized equation. We prove that there exists a unique viscosity solution to the penalized equation and the viscosity solution to the penalized equation converges to that of the original HJB equation as the penalty parameters tend to infinity. We also prove that the solution of the finite difference scheme converges to the viscosity solution of the penalized equation. Numerical results are given to demonstrate the effectiveness of the proposed method. We extend the penalty approach combined with a finite difference scheme to the HJB equations in the American option pricing model proposed by Davis and Zarphopoulou [20]. Numerical experiments are presented to illustrate the theoretical findings.