Optimization with recourse. In an optimization problem with recourse, also called two-stage optimization, the cost function and constraints depend not only on our choice of variables, but also on a discrete random variable s∈{1,…,S}, which is interpreted as specifying which of S scenarios occurred. The scenario random variable s has known probability distribution π, with πi=prob(s=i), i=1,…,S.
In two-stage optimization, we are to choose the values of two variables, x∈Rn and z∈Rq. The variable x must be chosen before the particular scenario s is known; the variable z, however, is chosen after the value of the scenario random variable is known. In other words, z is a function of the scenario random variable s. To describe our choice z, we list the values we would choose under the different scenarios, i.e., we list the vectors
z1,…,zS∈Rq.
Here z3 is our choice of z when s=3 occurs, and so on. The set of values
x∈Rn,z1,…,zS∈Rq
is called the policy, since it tells us what choice to make for x (independent of which scenario occurs), and also, what choice to make for z in each possible scenario.
The variable z is called the recourse variable (or second-stage variable), since it allows us to take some action or make a choice after we know which scenario occurred. In contrast, our choice of x (which is called the first-stage variable) must be made without any knowledge of the scenario.
For simplicity we will consider the case with no constraints. The cost function is given by
f:Rn×Rq×{1,…,S}→R,
where f(x,z,i) gives the cost when the first-stage choice x is made, second-stage choice z is made, and scenario i occurs. We will take as the overall objective, to be minimized over all policies, the expected cost
Ef(x,zs,s)=i=1∑Sπif(x,zi,i).
Suppose that f is a convex function of (x,z), for each scenario i=1,…,S. Explain how to find an optimal policy, i.e., one that minimizes the expected cost over all possible policies, using convex optimization.