The Mathematics of Financial Modelingand Investment Management

7-Optimization Page 215 Wednesday, February 4, 2004 12:50 PM

Optimization 215

a two-stage program that seeks to minimize the cost of the first-period

decision plus the expected cost of the second-period recourse decision. In

Chapter 21 we provide an example related to bond portfolio manage-

ment.

To cast the stochastic programming problem in the framework of LP,

we need to create a deterministic equivalent of the stochastic problem.

This is obtained introducing a new set of variables at each stage and tak-

ing expectations. The first-period direct cost is cTx while the recourse

cost at the second stage is dT

i yi where i = 1,...,S represents the different

states. The first-period constraints are represented as Ax = b. At each

stage, recourse is subject to some recourse function Tx + Wy = h. This

constraint can be, for example, self-financing conditions in portfolio

management. It should be noted that in stochastic programs the first-

period decision is independent of which second-period scenario actually

occurs. This is called the nonanticipativity property.

A two-stage problem can be formulated as follows

S

minimize c T x + T

∑ pidi yi

i = 1

subject to

Ax = b

Tix + Wiyi = hi, i = 1,...,S

x ≥ 0

yi ≥ 0

where S is the number of states and pi is the probability of each state

such that

S

∑ pi =^1

i = 1

Notice that the nonanticipativity constraint is met. There is only one

first-period decision whereas there are S second-period decisions, one

for each scenario. In this formulation, the stochastic programming

problem has been reduced to an LP problem. This formulation can be

extended to any number of intermediate stages.