DATE: Thursday, May 11, 2006
LOCATION: E40-298
TIME: 4:15pm
Reception immediately following in the Philip M. Morse Reading Room, E40-106
ABSTRACT
We consider the case of a stochastic control problem in discrete
time with a linear dynamics and convex constraints on the
controls. The uncertainty is described by a stochastic process
independent of the controls. The process is discrete in time
and values and is represented by an event tree. The essence of
this class of problems is that uncertainty gradually unfolds with
time. The successive decisions (controls) are adaptive, i.e., based
on the information of past history, but keep facing uncertainty.
Problems in that class are usually approximations of similar problems with
continuous time and value stochastic processes. The approximation
is often built by sampling on a continuous process.
Sampling almost surely results in a fan of scenarios, a degenerate
tree, in which the scenarios meet in only one point, the origin
node. In this discrete approximation resulting in a fan,
the decision process associated n becomes purely deterministic
as from stage 2; it looses the essence of the problem. To
overcome this shortcoming, one usually replaces the fan by
a tree than opens up gradually in time, or in terms of a
stochastic processes, one approximates the stochastic process
represented by a fan by one that is more fit to the decision
problem.
Rather than approximating the stochastic process, we propose
to keep the fan as it is, but to approximate the decision
process itself, by means of decision sets and decision rules.
A decision set at a given stage is simply a collection of
scenarios, and the set of all decision sets at that stage
forms a partition. In the new decision process, the elements
(scenarios) of a decision set are undistinguishable. The
decision process consists in assigning the same control
to all scenarios belonging to the same decision set. We speak
of a decision rule. If at any stage, the partition is a refinement
of the partition at the preceding stage, the problem looks very
similar to a standard stochastic programming one. In our work we propose
to drop the constraint of increasingly refined partitions, to avoid
an exponential growth of the partition sizes.
We apply this formulation to a classical 3-state newsboy problem.
We compare the new approach to a standard stochastic programming
one, with respect to a large initial tree. We provide computational
evidence that the new scheme performs as well as the standard stochastic
programming approach. With these results in mind, we propose to
solve problems with many more stages, something that would become
an issue with standard stochastic programming.
