Math 582DA
Stochastic Programming Duality: Analysis and Applications
Lisa Korf
Winter 2003, Monday/Wednesday/Friday, 11:30-12:20
Stochastic programming is one methodology for modeling and solving
optimization problems under uncertainty. Stochastic programs are
mathematical programs in which a probability distribution is incorporated
to describe the uncertain parameters present in the problem. A typical
application is that of a producer who wants to know how many of various
products to produce to maximize his expected profit under uncertain
customer demand. Recently stochastic programming has been applied to a
variety of problems arising in finance.
Stochastic programming models have a special structure due to the
inclusion of the probability distributions in their formulation.
Studying duality in stochastic programming leads to an understanding of
what happens to the problem under various perturbations of this structure.
Duality in stochastic programming is a useful tool for problem analysis
(e.g. dual variables interpreted as prices of information), as well as
solution methodologies. A major issue that arises is that, because a
probability distribution is present in the problem, the problem takes on
an infinite-dimensional character. Standard finite-dimensional duality
techniques do not apply.
We will explore duality in stochastic programming of both the
finite-dimensional and infinite-dimensional variety. Various forms of
duality will be explored, along with interpretations. Some issues we will
consider once a firm foundation is established are relative duality gaps
for nonconvex (including integer) stochastic programs dependent on the
type of Lagrangian relaxation considered, and interpretation of dual
variables in applications, in particular as applied to portfolio
optimization and the pricing of financial derivatives.
Prerequisites: Real Analysis (524/525/526), an Optimization course such
as 407, 408, or 515. Some knowledge of Probability Theory is helpful but
not required.
Related reading:
- Rockafellar, R.T., Conjugate Duality and Optimization, CBMS-NSF
Regional Conference Series in Applied Mathematics, SIAM, Philadelphia,
1974.
- Rockafellar, R.T. and Wets, R., Stochastic convex programming: basic
duality, Pacific Journal of Mathematics, Vol. 62, No. 1, 1976, pp.
173-195.
- Rockafellar, R.T. and Wets, R., Stochastic convex programming:
relatively complete recourse and induced feasibility, SIAM J. Control and
Optimization, Vol. 14, No. 3, May 1976, pp. 574-589.
- Korf, L.,
Stochastic
Programming Duality: L∞ multipliers for
unbounded constraints with an application to mathematical finance,
2002.
- King, A., and Korf, L.,
Martingale
pricing measures in incomplete markets via stochastic programming duality in the dual of L∞, 2002.