On the Solution of Complementarity Problems Arising in American Options Pricing

In the Black-Scholes-Merton model, as well as in more general stochastic models in finance, the price of an American option solves a system of partial differential variational inequalities. When these inequalities are discretized, one obtains a linear complementarity problem that must be solved at each time step. This paper presents an algorithm for the solution … Read more

A Sequential Quadratic Programming Algorithm with an Additional Equality Constrained Phase

A sequential quadratic programming (SQP) method is presented that aims to overcome some of the drawbacks of contemporary SQP methods. It avoids the difficulties associated with indefinite quadratic programming subproblems by defining this subproblem to be always convex. The novel feature of the approach is the addition of an equality constrained phase that promotes fast … Read more

On the Geometry Phase in Model-Based Algorithms for Derivative-Free Optimization

A numerical study of model-based methods for derivative-free optimization is presented. These methods typically include a geometry phase whose goal is to ensure the adequacy of the interpolation set. The paper studies the performance of an algorithm that dispenses with the geometry phase altogether (and therefore does not attempt to control the position of the … Read more

An Algorithm for the Fast Solution of Linear Complementarity Problems

This paper studies algorithms for the solution of mixed symmetric linear complementarity problems. The goal is to compute fast and approximate solutions of medium to large sized problems, such as those arising in computer game simulations and American option pricing. The paper proposes an improvement of a method described by Kocvara and Zowe that combines … Read more

KNITRO-Direct: A Hybrid Interior Algorithm for Nonlinear Optimization

A hybrid interior-point method for nonlinear programming is presented. It enjoys the flexibility of switching between a line search based method which computes steps by factoring the primal-dual equations and an iterative method using a conjugate gradient algorithm and globalized by means of trust regions. Steps computed by a direct factorization are always tried first, … Read more

Assessing the Potential of Interior Methods for Nonlinear Optimization

A series of numerical experiments with interior point (LOQO, KNITRO) and active-set SQP codes (SNOPT, filterSQP) are reported and analyzed. The tests were performed with small, medium-size and moderately large problems, and are examined by problem classes. Detailed observations on the performance of the codes, and several suggestions on how to improve them are presented. … Read more