On Complexity of Stochastic Programming Problems

By Alexander Shapiro, Arkadi Nemirovski. 2005

393 citations recorded by the source corpus.

Subfields: Control and Systems Engineering, Economics and Econometrics, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/3ee4aa848a472b639f9e0a304f82d79ffc55e75d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Control and Systems Engineering

In Economics and Econometrics

In Management Science and Operations Research

Citations in the corpus

Analysis of stochastic dual dynamic programming method (2011, background): “…Planning ProblemsHandbook of Networks in Power Systems IApplication of the Systems Approach to the Management of Complex Water SystemsOptimizing the Operation of a Multiple Reservoir System in the Eastern Nile Basin Considering Water and Sediment FluxesRobust Optimization in Electric Energy Systems”
Lectures on Stochastic Programming: Modeling and Theory (2009, methodology): “For a more recent discussion, in the framework of stochastic programming, we can refer to Shapiro and Nemirovski [249], and Georghiou, Wiesemann and Kuhn [84].”
Distributionally Robust Optimization and Its Tractable Approximations (2010, background): “Such problems are known to be difficult to solve exactly (see Shapiro and Nemirovski [35]), but are important in practice.”
From CVaR to Uncertainty Set: Implications in Joint Chance-Constrained Optimization (2010, methodology): “Soyster (1973) showed that the model can be represented as a polynomially sized linear optimization model.”
Increasing Supply Chain Robustness through Process Flexibility and Inventory (2018, background): “The quality of the SAA solutions depends on the number of samples, and the number of samples required for SAA solutions to achieve strong theoretical guarantees is often very large (Shapiro and Nemirovski 2005).”
A Robust Optimization Perspective on Stochastic Programming (2007, methodology): “One criticism is that a purportedly feasible stochastic optimization problem may not be feasible any more if one restricts the recourse function to a linear decision rule.”
Adaptive Distributionally Robust Optimization (2019, methodology): “Dynamic optimization models, where decisions adapt to the uncertain outcomes as they unfold in stages, typically suﬀer from the “curse of dimensionality” and are computationally intractable (see, for instance, Shapiro and Nemirovski 2005, Dyer and Stougie 2006, Ben-Tal et al. 2004).”
Scaling Up Robust MDPs using Function Approximation (2014, methodology): “When the objective of the SP is convex, and under additional technical conditions oñ p, p θ , and φ, efficient solution of (13) is guaranteed 4 (Shapiro & Nemirovski, 2005).”
Entropic Value-at-Risk: A New Coherent Risk Measure (2012, methodology): “For more details on the SAA method, the reader may refer to [41].”
Validation analysis of mirror descent stochastic approximation method (2012, background): “N 1 PN t=1F (x; t). Recent theoretical studies (cf., [2,14, 15 ]) and numerical experiments (e.g., [4,5,16])”
Convex optimization under inexact first-order information (2009, neutral): “, [30, 68, 69]) and numerical experiments (see, e.”
An optimal method for stochastic composite optimization (2011, methodology): “Recent theoretical studies (cf., [16,45,46]) and numerical experiments (see e.g., [23,27,51]) show that the SAA method coupled with a good (deterministic) algorithm could be reasonably efﬁcient for solving certain classes of two stage stochastic programming problems.”