Consider the following problem (a) In this example, the L -shaped method selects x1 = (0,0)T as starting point (Step l of Iteration 1). The L -shaped method can however be used with any other...

Consider the following problem

(a) In this example, the L -shaped method selects x1 = (0,0)T as starting point (Step l of Iteration 1). The L -shaped method can however be used with any other reasonable starting point. Take x = (1,5)T as starting point. Show that the L -shaped then finds an optimal solution in three iterations (which means adding only two optimality cuts). (b) Show that exactly the same steps are taken if the starting point is any point within the region 4 ≤ x2 ≤ 6+x1 .

(c) Consider any stochastic program where the only first-stage constraints are bounds on the variables. Explain why the L -shaped method needs at least two cuts to terminate, unless at least one variable is at a bound at the optimum.

(d) Prove that the optimality cuts can also be constructed from the primal solutions of the second stage programs

(e) Show that the first-stage feasibility set K₁
= {0 ≤ x₁
≤ 10 , 0 ≤ x₂
≤ 10} can be partitioned in four regions, each one yielding a different optimality