Duality in stochastic linear and dynamic programming.

*(English)*Zbl 0598.90062
Lecture Notes in Economics and Mathematical Systems, 274. Berlin etc.: Springer-Verlag. VII, 295 p. DM 55.00 (1986).

The author considers some problems arising in stochastic linear programming (SLP) and in discrete-time stochastic dynamic programming (SDP) with a finite number of stages. The book consists of two parts. The first part (Chapters 1-3) has an introductory character. In Chapter 1 (Introduction and Summary) the author defines the subject of the book and gives a brief overview of the contents of the following chapters and informations on the interdependence of the various chapters.

In Chapter 2 (Mathematical programming and duality theory) the terminology of mathematical programming is introduced and a concise treatment of the duality theory of convex programming problems in abstract spaces is given. A sufficient condition for stability is formulated and necessary and sufficient conditions for optimality under the assumption of stability are given.

In Chapter 3 (Stochastic linear programming models) some SLP models are presented. Such models arise if some of the parameters \((c_ j,a_{ij},b_ i)\) in a linear programming problem are random variables. In this case the ordinary problem of linear programming applies no longer. Then the author studies the definition of ”feasibility” and ”optimality” in a random environment. A number of well-known preference criteria (minimize the expected cost, use the variance as measure for risk, minimize the probability of bankruptcy and maximize the expected utility) are formulated and their relationships are given. The final section presents multistage stochastic linear programming models and their relation to stochastic dynamic programming.

Beginning with Chapter 4 new results are presented. In Chapter 4 (Some linear programs in probabilities duals) a general framework for abstract linear programming duality is given. Three linear programs in which the decision variables are probbility measures are considered: i) a generalized moment problem, and variants of it, ii) a problem with given marginals, iii) an SDP problem with a finite number of stages. For each of these problems the dual problem is an approximation problem in a function space.

In Chapter 5 (On integrated chance constraints) a new SLP concept is introduced under the name ”integrated chance constraints” (ICCs) and the mathematical properties of this new concept are analyzed. Using a duality theorem it is shown that there is a natural equivalence between certain models with ICCs and certain recourse models.

Chapter 6 (On the behaviour of the optimal value operator of dynamic programming) deals with the dynamic programming algorithm (DPA) for the finite-horizon stochastic dynamic programming problem (SDP). Conditions guaranteing that DPA generates an optimal (deterministic Markovian) policy for SDP are formulated. It is shown that the conditions are useful for a rather general class of production-inventory control models.

Chapter 7 (Robustness against dependence in PERT) deals with one of the most famous SLP problems which refers to project planning. The duration of the activities are considered as random variables. The formulation of the SLP model is of the minimax type. Finally some numerical results are given, showing that the minimax approach to project planning is computationally feasible.

In Chapter 8 (A dual of a dynamic inventory control model: the deterministic and the stochastic case) the author considers a more general production-inventory control models than the one studied in Chapter 6 in the sense that it does not have to be Markovian. Two cases are considered: the deterministic and the stochastic case. In the deterministic case two dual dynamic programming methods are described. The first one is equivalent to the primal dynamic programming method whereas the second is obtained by application of conjugacy to the primal dynamic programming method. In the stochastic case it is assumed that the demands are random variables. The problem is formulated as a multistage stochastic linear program in function space. Therefore the abstract linear programming duality theory, developed in Chapter 4 is applicable here.

All the Chapters are followed by a number of references. A list of optimization problems and the subject index incomplete the book. The book is concise and well-written.

In Chapter 2 (Mathematical programming and duality theory) the terminology of mathematical programming is introduced and a concise treatment of the duality theory of convex programming problems in abstract spaces is given. A sufficient condition for stability is formulated and necessary and sufficient conditions for optimality under the assumption of stability are given.

In Chapter 3 (Stochastic linear programming models) some SLP models are presented. Such models arise if some of the parameters \((c_ j,a_{ij},b_ i)\) in a linear programming problem are random variables. In this case the ordinary problem of linear programming applies no longer. Then the author studies the definition of ”feasibility” and ”optimality” in a random environment. A number of well-known preference criteria (minimize the expected cost, use the variance as measure for risk, minimize the probability of bankruptcy and maximize the expected utility) are formulated and their relationships are given. The final section presents multistage stochastic linear programming models and their relation to stochastic dynamic programming.

Beginning with Chapter 4 new results are presented. In Chapter 4 (Some linear programs in probabilities duals) a general framework for abstract linear programming duality is given. Three linear programs in which the decision variables are probbility measures are considered: i) a generalized moment problem, and variants of it, ii) a problem with given marginals, iii) an SDP problem with a finite number of stages. For each of these problems the dual problem is an approximation problem in a function space.

In Chapter 5 (On integrated chance constraints) a new SLP concept is introduced under the name ”integrated chance constraints” (ICCs) and the mathematical properties of this new concept are analyzed. Using a duality theorem it is shown that there is a natural equivalence between certain models with ICCs and certain recourse models.

Chapter 6 (On the behaviour of the optimal value operator of dynamic programming) deals with the dynamic programming algorithm (DPA) for the finite-horizon stochastic dynamic programming problem (SDP). Conditions guaranteing that DPA generates an optimal (deterministic Markovian) policy for SDP are formulated. It is shown that the conditions are useful for a rather general class of production-inventory control models.

Chapter 7 (Robustness against dependence in PERT) deals with one of the most famous SLP problems which refers to project planning. The duration of the activities are considered as random variables. The formulation of the SLP model is of the minimax type. Finally some numerical results are given, showing that the minimax approach to project planning is computationally feasible.

In Chapter 8 (A dual of a dynamic inventory control model: the deterministic and the stochastic case) the author considers a more general production-inventory control models than the one studied in Chapter 6 in the sense that it does not have to be Markovian. Two cases are considered: the deterministic and the stochastic case. In the deterministic case two dual dynamic programming methods are described. The first one is equivalent to the primal dynamic programming method whereas the second is obtained by application of conjugacy to the primal dynamic programming method. In the stochastic case it is assumed that the demands are random variables. The problem is formulated as a multistage stochastic linear program in function space. Therefore the abstract linear programming duality theory, developed in Chapter 4 is applicable here.

All the Chapters are followed by a number of references. A list of optimization problems and the subject index incomplete the book. The book is concise and well-written.

Reviewer: I.M.Stancu-Minasian

##### MSC:

90C15 | Stochastic programming |

49N15 | Duality theory (optimization) |

90C90 | Applications of mathematical programming |

90B05 | Inventory, storage, reservoirs |

49L20 | Dynamic programming in optimal control and differential games |

90C05 | Linear programming |

90C39 | Dynamic programming |

90C48 | Programming in abstract spaces |

90C25 | Convex programming |

90C31 | Sensitivity, stability, parametric optimization |

90B30 | Production models |

90B35 | Deterministic scheduling theory in operations research |