The proposed project addresses modeling, duality, approximation, implementation and application of stochastic programming problems with many time stages. The typical so-called multi-stage stochastic program tends to be modeled as an extension of a two-stage problem (often referred to as a stochastic program with recourse). This misses some important features of a problem with many time stages, including a description of the dynamics inherent to the problem, the structure of information, and the degree to which one may respond to that information at a given time stage. A typical problem from mathematical finance will be framed in a many- stage stochastic programming setting, allowing for a description of the dynamics. The classical pricing results of mathematical finance and extensions to more complicated problems will be obtained using the new model. This model will be generalized to be applicable to a much broader range of many-stage stochastic optimization problems, highlighting duality results and their significance. In conjunction with this will be an investigation into problems that could be modeled in a continuous time framework, and problems with infinitely many time stages. New stochastic programming models, and approximation techniques using the tools of variational analysis, will be developed for these respective problems. Finally, an investigation into the structure of many-stage problems that include a description of system dynamics will be undertaken, leading ultimately to the development and implementation of algorithms for solving them.
Decision making under uncertainty and the theory and techniques of mathematical programming merged in the 1950's to create the field now known as stochastic programming. A stochastic program is a mathematical program (e.g. a linear program) that includes in its formulation a probability distribution to describe uncertain parameters. Research consists largely of understanding problem structure, deriving duality results and optimality conditions, developing approximation techniques, and exploiting the structure and theory in the development of solution schemes. The field's development began with a two-stage recourse model, where the cost of a decision made now (e.g. production) is affected by an uncertain outcome in the future (e.g. demand), and the possibility of taking recourse action once the future is revealed (e.g. overtime). A typical problem is to determine the present decision that minimizes expected cost. While much knowledge has been gained from the investigation of two-stage models, a limited view of many-stage stochastic programming has resulted in which multistage problems are considered as simple extensions of the two-stage case. This fails to address the inherently dynamic nature of problems with many time stages. Additionally, two-stage applications tend to come largely from areas such as production and manufacturing, whereas the bulk of problems with many time stages arise from financial, economic, and environmental planning applications and other problems where dynamics are driving a system. Thus, much of the new many-stage theory should be geared toward these sorts of applications. The proposed research will explore the additional dynamic structures, theory (duality, approximation), and questions regarding implementation, of stochastic optimization problems involving many (possibly even infinitely many, or a continuum of) stages. This will be motivated primarily by financial applications.
