A novel feasible discretization method for linear semi-infinite programming applied to basket option pricing

Abstract

In this exposition a novel feasible version of traditional discretization methods for linear semi-infinite programming problems is presented. It will be shown that each – usually infeasible – iterate can be easily supplemented with a feasible iterate based on the knowledge of a Slater point. The effectiveness of the method is demonstrated on the problem of finding model free bounds to basket option prices which has gained a significant interest in the last years. For this purpose a fresh look is taken on the upper bound problem and on some of its structure, which needs to be exploited to yield an efficient solution by the feasible discretization method. The presented approach allows the generalization of the problem setting by including exotic options (like power options, log-contracts, binary options, etc.) within the super-replicating portfolio.

Keywords:

• semi-infinite programming
• feasible discretization method
• basket options

AMS Subject Classifications::

• 65K05
• 90C34
• 90C90
• 91G20
• 91G60

Acknolwedgements

We are most thankful for the highly valuable comments of the referees who helped to improve this article substantially, both in terms of clarity and theoretical insight. We further want to express our gratitude to participants in the stream Continuous Optimization of EURO 2009 for fruitful discussions.

Notes

Notes

1. No analytical solution to (LB₀) is known so far for m ≥ 3.

2. To be more exact, they showed that the duals (UB₀) and (LB₀) can be reformulated as LPs with O(m) and O(m ²) variables and constraints.

3. A spread option on two assets has, for example, the payoff (S ₁ − S ₂)⁺, which is a very popular derivative in foreign exchange or interest rate markets.

4. Static means that the portfolio is not dynamically changed between the initial valuation time 0 and the maturity τ.

5. For the exact definition of an arbitrage-free market in the general case, we refer to 14.

6. For simplicity of presentation, the exponent α = 2 is used, but other exponents α > 1 are also feasible. For more details on power options, let us refer to 9, Section 4.4].

7. This first call takes place in the second iteration after the solution of an initial LP in the first iteration.