90C15 Stochastic programming
Refine
Year of publication
Language
- English (24)
Keywords
- Stochastic programming (9)
- chance constraints (5)
- scenario reduction (5)
- scenario tree (4)
- stability (4)
- two-stage (4)
- discrepancy (3)
- mixed-integer (3)
- multistage (3)
- probabilistic constraints (3)
Chance constraints represent a popular tool for finding decisions that enforce a
robust satisfaction of random inequality systems in terms of probability. They
are widely used in optimization problems subject to uncertain parameters as they
arise in many engineering applications. Most structural results of chance constraints (e.g., closedness, convexity, Lipschitz continuity, differentiability etc.) have been formulated in a finite-dimensional
setting. The aim of this paper is to generalize some of these well-known semi-continuity and convexity properties to a setting of control problems
subject to (uniform) state chance constraints.
Uncertainty is inevitable when solving science and engineering application problems. In the face of
uncertainty, it is essential to determine robust and risk-averse solutions. In this work,
we consider a class of PDE-constrained optimization problems in which the PDE coefficients
and inputs may be uncertain. We introduce two approximations for minimizing the
conditional value-at-risk for such PDE-constrained optimization problems. These approximations are based
on the primal and dual formulations of the conditional value-at-risk. For the primal problem,
we introduce a smooth approximation of the conditional value-at-risk in order to utilize
derivative-based optimization algorithms and to take advantage of the convergence properties
of quadrature-based discretizations. For this smoothed conditional value-at-risk, we prove
differentiability as well as consistency of our approximation. For the dual problem, we
regularize the inner maximization problem, rigorously derive optimality conditions, and demonstrate
the consistency of our approximation. Furthermore, we propose a fixed-point iteration that takes
advantage of the structure of the regularized optimality conditions and provides a means of calculating
worst-case probability distributions based on the given probability level. We conclude with numerical
results.
In this paper a condition number for linear-quadratic two-stage stochastic optimization problems is introduced as the Lipschitz modulus of the multifunction assigning to a (discrete) probability distribution the solution set of the problem. Being the outer norm of the Mordukhovich coderivative of this multifunction, the condition number can be estimated from above explicitly in terms of the problem data by applying appropriate calculus rules. Here, a chain rule for the extended partial second-order subdifferential recently proved by Mordukhovich and Rockafellar plays a crucial role. The obtained results are illustrated for the example of two-stage stochastic optimization problems with simple recourse.
A mixed-integer stochastic nonlinear optimization problem with joint probabilistic constraints
(2013)
We illustrate the solution of a mixed-integer stochastic nonlinear optimization problem in an application of power management. In this application, a coupled system consisting of a hydro power station and a wind farm is considered. The objective is to satisfy the local energy demand and sell any surplus energy on a spot market for a short time horizon. Generation of wind energy is assumed to be random, so that demand satisfaction is modeled by a joint probabilistic constraint taking into account the multivariate distribution. The turbine is forced to either operate between given positive limits or to be shut down. This introduces additional binary decisions. The numerical solution procedure is presented and results are illustrated.
We consider convex optimization problems with $k$th order stochastic dominance constraints for $k\ge 2$. We discuss distances of random variables that are relevant for the dominance relation and establish quantitative stability results for optimal values and solution sets in terms of a suitably selected probability metrics.Moreover, we provide conditions ensuring that the optimal value function is Hadamard directionally differentiable. Finally, we discuss some implications of the results for empirical (Monte Carlo,
sample average) approximations of dominance constrained optimization models.
In this paper, we deal with a hydraulic reservoir optimization problem with uncertainty on
inflows in a joint chance constrained programming setting. In particular, we will consider inflows with
a persistency effect, following a causal time series model, and examine the impact of the ”Gaussian”
assumption for such inflows. We present an iterative algorithm for solving similarly structured joint
chance constrained programming problems that requires a Slater point and the computation of gradients.
Several alternatives to the joint chance constraint problem are presented. In particular, we present an
individual chance constraint problem and a robust model. We illustrate the interest of joint chance
constrained programming by comparing results obtained on a realistic hydro-valley with those obtained
from the alternative models. Despite the fact that the alternative models often require less hypothesis
on the law of the inflows, we show that they yield conservative and costly solutions. The simpler models,
such as the individual chance constraint one, are shown to yield insufficient robustness and are therefore
not useful. We therefore conclude that Joint Chance Constrained programming appears as a technique
offering a good trade-off between cost and robustness and can be tractable for complex realistic models.
We provide lower estimates for the norm of gradients of Gaussian
distribution functions and apply the results obtained to a special class of
probabilistically constrained optimization problems. In particular, it is shown
how the precision of computing gradients in such problems can be controlled
by the precision of function values for Gaussian distribution functions. Moreover,
a sensitivity result for optimal values with respect to perturbations of the
underlying random vector is derived. It is shown that the so-called maximal
increasing slope of the optimal value with respect to the Kolmogorov distance
between original and perturbed distribution can be estimated explicitly from
the input data of the problem.
We define a risk averse nonanticipative feasible policy for multistage stochastic programs and propose a methodology to implement it. The approach is based on dynamic programming equations written for a risk averse formulation of the problem.
This formulation relies on a new class of multiperiod risk functionals called extended polyhedral risk measures. Dual representations of such risk functionals are given and used to derive conditions of coherence. In the one-period case, conditions for convexity and consistency with second order stochastic dominance are also provided. The risk averse dynamic programming equations are specialized considering convex combinations of one-period extended polyhedral risk measures such as spectral risk measures.
To implement the proposed policy, the approximation of the risk averse recourse functions for stochastic linear programs is discussed. In this context, we detail a stochastic dual dynamic programming algorithm which converges to the optimal value of the risk averse problem.
Stochastic programming problems appear as mathematical models for optimization problems under stochastic uncertainty. Most computational approaches for solving such models are based on approximating the underlying probability distribution by a probability measure with finite support. Since the computational complexity for solving stochastic programs gets worse when increasing the number of atoms (or scenarios), it is sometimes necessary to reduce their number. Techniques for scenario reduction often require fast heuristics for solving combinatorial subproblems. Available techniques are reviewed and open problems are discussed.
In this paper, a model for (joint) dynamic chance constraints is proposed and applied to an optimization problem in water reservoir management. The model relies on discretization of the decision variables but keeps the probability distribution
continuous. Our approach relies on calculating probabilities of rectangles which is particularly useful in the presence of independent random variables but works for a moderate number of stages equally well in case of correlated variables. Numerical results are provided for two and three stages.