September 18th, 2003, 7:30 am
The terms 'dual' and 'duality' are used in many contexts with different meanings. In this case, I believe 'duality' is to be understood in the context of optimization. Pricing of American or Bermudan options can be restated as an optimal stopping problem, i.e. finding an exercise strategy that maximizes the value of the option (as a function of the exercise strategy). A dual problem to his maximization problem is a minimization problem on a dual space, defined by the same data, and with the property that the objective function of the maximization problem (primal problem) is less than or equal to the objective function of the dual problem (s.t. the same holds for the respective optima). Now, the interesting dual problems are of course those for which the supremum of the primal problem equals the infimum of the dual problem, and even more so for problems where these optima are attained. This can be done for linear and convex optimization problems - the most prominent example being linear programming in euclidean spaces - but the theory can be extended to infinite-dimensional linear vector spaces (viz. Luenbergers book 'Optimization by vector space methods'), but the concept of duality can be extended to non-convex optimization as well by the concept of dual functions (as opposed to dual multipliers). Indeed, one can define a hierarchy of dual problems, by restricting the subset defining the set of feasible solutions of the dual problem. This gives a tradeoff between selecting a dual problem that is computationally tractable versus one that gives tight bounds at higher computational costs