Stochastic Linear Programming

by Kall, Peter; Mayer, Janos

• ISBN13: 9780387233857
• ISBN10: 0387233857
• Format: Hardcover
• Copyright: 2005-01-30
• Publisher: Springer Verlag

Summary

Peter Kall and Jànos Mayer are distinguished scholars and professors of Operations Research and their research interest is particularly devoted to the area of stochastic optimization. Stochastic Linear Programming: Models, Theory, and Computation is a definitive presentation and discussion of the theoretical properties of the models, the conceptual algorithmic approaches, and the computational issues relating to the implementation of these methods to solve problems that are stochastic in nature. The application area of stochastic programming includes portfolio analysis, financial optimization, energy problems, random yields in manufacturing, risk analysis, etc. In this book, models in financial optimization and risk analysis are discussed as examples, including solution methods and their implementation. Stochastic programming is a fast developing area of optimization and mathematical programming. Numerous papers and conference volumes, and several monographs have been published in the area; however, the Kall and Mayer book will be particularly useful in presenting solution methods including their solid theoretical basis and their computational issues, based in many cases on implementations by the authors. The book is also suitable for advanced courses in stochastic optimization.

Table of Contents

Notations	ix
Preface	3	(4)
Basics	7	(68)
Introduction	7	(6)
Linear Programming Prerequisites	13	(47)
Algebraic concepts and properties	13	(3)
Geometric interpretation	16	(3)
Duality statements	19	(3)
The Simplex Method	22	(5)
The Dual Simplex Method	27	(2)
Dual Decomposition	29	(8)
Nested Decomposition	37	(16)
Regularized Decomposition	53	(3)
Interior Point Methods	56	(4)
Nonlinear Programming Prerequisites	60	(15)
Optimality Conditions	64	(2)
Solution methods	66	(9)
Single--Stage SLP Models	75	(118)
Introduction	75	(17)
Models involving probability functions	92	(52)
Basic properties	96	(2)
Finite discrete distribution	98	(2)
Separate probability functions	100	(2)
Only the right--hand--side is stochastic	102	(1)
Multivariate normal distribution	103	(8)
Stable distributions	111	(6)
A distribution-free approach	117	(3)
The independent case	120	(2)
Joint constraints: random right--hand--side	122	(1)
Generalized--concave probability measures	122	(10)
Generalized--concave distribution functions	132	(4)
Maximizing joint probability functions	136	(1)
Joint constraints: random technology matrix	136	(5)
Summary on the convex programming subclasses	141	(3)
Quantile functions, Value at Risk	144	(2)
Models based on expectation	146	(20)
Integrated chance constraints	149	(1)
Separate integrated probability functions	149	(5)
Joint integrated probability functions	154	(4)
A model involving conditional expectation	158	(1)
Conditional Value at Risk	159	(7)
Models built with deviation measures	166	(12)
Quadratic deviation	166	(3)
Absolute deviation	169	(5)
Quadratic semi--deviation	174	(3)
Absolute semi--deviation	177	(1)
Modeling risk and opportunity	178	(2)
Risk measures	180	(13)
Risk measures in finance	182	(2)
Properties of risk measures	184	(5)
Portfolio optimization models	189	(4)
Multi-Stage SLP Models	193	(80)
The general SLP with recourse	193	(5)
The two-stage SLP	198	(50)
Complete fixed recourse	201	(25)
Simple recourse	226	(17)
Some characteristic values for two-stage SLP's	243	(5)
The multi-stage SLP	248	(25)
MSLP with finite discrete distributions	249	(6)
MSLP with non-discrete distributions	255	(18)
Algorithms	273	(102)
Introduction	273	(1)
Single-stage models with separate probability functions	273	(3)
A guide to available software	275	(1)
Single-stage models with joint probability functions	276	(25)
Numerical considerations	277	(4)
Cutting plane methods	281	(3)
Other algorithms	284	(1)
Bounds for the probability distribution function	284	(8)
Computing probability distribution functions	292	(1)
A Monte-Carlo approach with antithetic variates	293	(3)
A Monte-Carlo approach based on probability bounds	296	(3)
Finite discrete distributions	299	(1)
A guide to available software	299	(1)
SLP problems with logconcave distribution functions	299	(1)
Evaluating probability distribution functions	300	(1)
SLP problems with finite discrete distributions	301	(1)
Single-stage models based on expectation	301	(13)
Solving equivalent LP's	302	(1)
Dual decomposition revisited	302	(5)
Models with separate integrated probability functions	307	(2)
Models involving CVaR--optimization	309	(2)
Models with joint integrated probability functions	311	(3)
A guide to available software	314	(1)
Models with separate integrated probability functions	314	(1)
Models with joint integrated probability functions	314	(1)
Models involving CVaR	314	(1)
Single-stage models involving VaR	314	(1)
Single-stage models with deviation measures	315	(1)
A guide to available software	316	(1)
Two--stage recourse models	316	(40)
Decomposition methods	317	(1)
Successive discrete approximation methods	318	(2)
Computing the Jensen lower bound	320	(1)
Computing the E--M upper bound for an interval	320	(3)
Computing the bounds for a partition	323	(3)
The successive discrete approximation method	326	(5)
Implementation	331	(6)
Simple recourse	337	(4)
Other successive discrete approximation algorithms	341	(1)
Stochastic algorithms	342	(1)
Sample average approximation (SAA)	342	(6)
Stochastic decomposition	348	(4)
Other stochastic algorithms	352	(1)
Simple recourse models	353	(1)
A guide to available software	353	(3)
Multistage recourse models	356	(12)
Finite discrete distribution	356	(2)
Scenario generation	358	(2)
Bundle--based sampling	360	(1)
A moment--matching heuristic	361	(6)
A guide to available software	367	(1)
Modeling systems for SLP	368	(7)
Modeling systems for SLP	368	(1)
SLP-IOR	369	(1)
General issues	370	(1)
Analyze tools and workbench facilities	371	(1)
Transformations	372	(1)
Scenario generation	372	(1)
The solver interface	373	(1)
System requirements and availability	374	(1)
References	375	(20)
Index	395