Refine
Year of publication
Language
- English (21)
Keywords
- chance constraints (5)
- Stochastic programming (3)
- probabilistic constraints (3)
- Kolmogorov metric (2)
- calmness (2)
- discrepancy (2)
- mixed-integer (2)
- scenario reduction (2)
- stochastic programming (2)
- two-stage (2)
We study perturbations of a stochastic program with a probabilistic constraint and r-concave original probability distribution. First we improve our earlier results substantially and provide conditions implying Hölder continuity properties of the solution sets w.r.t. the Kolmogorov distance of probability distributions. Secondly, we derive an upper Lipschitz continuity property for solution sets under more restrictive conditions on the original program and on the perturbed probability measures. The latter analysis applies to linear-quadratic models and is based on work by Bonnans and Shapiro. The stability results are illustrated by numerical tests showing the different asymptotic behaviour of parametric and nonparametric estimates in a program with a normal probabilistic constraint.
The paper provides a structural analysis of the feasible set defined by linear probabilistic constraints. Emphasis is laid on single (individual) probabilistic constraints. A classical convexity result by Van de Panne/Popp and Kataoka is extended to a broader class of distributions and to more general functions of the decision vector. The range of probability levels for which convexity can be expected is exactly identified. Apart from convexity, also nontriviality and compactness of the
feasible set are precisely characterized at the same time. The relation between feasible sets with negative and with nonnegative right-hand side is revealed. Finally, an existence result is formulated for the more difficult case of joint probabilistic constraints.
Discrete approximations to chance constrained and mixed-integer two-stage stochastic programs require moderately sized scenario
sets. The relevant distances of (multivariate) probability
distributions for deriving quantitative stability results for such stochastic programs are $\mathcal{B}$-discrepancies, where the class $\mathcal{B}$ of Borel sets depends on their structural properties.
Hence, the optimal scenario reduction problem for such models is stated with respect to $\mathcal{B}$-discrepancies. In this paper,
upper and lower bounds, and some explicit solutions for optimal scenario reduction problems are derived. In addition, we develop
heuristic algorithms for determining nearly optimally reduced probability measures, discuss the case of the cell discrepancy (or
Kolmogorov metric) in some detail and provide some numerical experience.
This paper concerns second-order analysis for a remarkable class of variational systems in finite-dimensional and infinite-dimensional spaces, which is particularly important for the study of optimization and equilibrium problems with equilibrium constraints. Systems of this type are described via variational inequalities over polyhedral convex sets and allow us to provide a comprehensive local analysis by using appropriate generalized differentiation of the normal cone mappings for such sets. In this paper we efficiently compute the required coderivatives of the normal cone mappings exclusively via the initial data of polyhedral sets in reflexive Banach spaces. This provides the main tools of second-order variational analysis allowing us, in particular, to derive necessary and sufficient conditions for robust Lipschitzian stability of solution maps to parameterized variational inequalities with evaluating the exact bound of the corresponding Lipschitzian moduli. The efficient coderivative calculations and characterizations of robust stability obtained in this paper are the first results in the literature for the problems under consideration in infinite-dimensional spaces. Most of them are also new in finite dimensions.
The paper deals with co-derivative formulae for normal cone mappings to smooth
inequality systems. Both the regular (Linear Independence Constraint Qualification satisfied)
and nonregular (Mangasarian-Fromovitz Constraint Qualification satisfied) cases are considered.
A major part of the results relies on general transformation formulae previously obtained by
Mordukhovich and Outrata. This allows one to derive exact formulae for general smooth, regular and polyhedral, possibly
nonregular systems. In the nonregular, nonpolyhedral case a generalized transformation formula by
Mordukhovich and Outrata applies, however, a major difficulty consists in
checking a calmness condition of a certain multivalued mapping. The paper provides a translation
of this condition in terms of much easier to verify constraint qualifications. The final section is
devoted to the situation where the calmness condition is violated. A series of examples
illustrates the use and comparison of the presented formulae.
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.
In this paper, we consider the characterization of strong stationary solutions to
equilibrium problems with equilibrium constraints (EPECs). Assuming that the underlying
generalized equation satisfies strong regularity in the sense of Robinson, an explicit
multiplier-based stationarity condition can be derived. This is applied then
to an equilibrium model arising from ISO-regulated electricity spot markets.
On probabilistic constraints induced by rectangular sets and multivariate normal distributions
(2009)
In this paper, we consider optimization problems under probabilistic constraints which are defined by two-sided
inequalities for the underlying normally distributed random vector. As a main step
for an algorithmic solution of such problems, we derive a derivative formula for (normal) probabilities
of rectangles as functions of their lower or upper bounds. This formula allows to reduce the calculus
of such derivatives to the calculus of (normal) probabilities of rectangles themselves thus generalizing a
similar well-known statement for multivariate normal distribution functions. As an application, we consider
a problem from water reservoir management. One of the outcomes of the problem solution is that the
(still frequently encountered) use of simple individual probabilistic can completely fail. In contrast, the
(more difficult) use of joint probabilistic constraints which heavily depends on the derivative formula mentioned
before yields very reasonable and robust solutions over the whole time horizon considered.
In this article we compare two different calmness conditions which are
widely used in the literature on bilevel programming and on mathematical
programs with equilibrium constraints. In order to do so, we consider convex
bilevel programming as a kind of intersection between both research areas.
The so-called partial calmness concept is based on the function value
approach for describing the lower level solution set. Alternatively,
calmness in the sense of multifunctions may be considered for perturbations
of the generalized equation representing the same lower level solution set.
Both concepts allow to derive first order necessary optimality conditions
via tools of generalized differentiation introduced by Mordukhovich. They
are very different, however, concerning their range of applicability and the
form of optimality conditions obtained. The results of this paper seem to
suggest that partial calmness is considerably more restrictive than calmness
of the perturbed generalized equation. This fact is also illustrated by
means of a dicretized obstacle control problem.
An optimal control problem to find the fastest collision-free trajectory of a robot surrounded by obstacles is presented.
The collision avoidance is based on linear programming arguments and expressed as state constraints. The optimal control problem is
solved with a sequential programming method. In order to decrease the number of unknowns and constraints a backface culling active set
strategy is added to the resolution technique.
The paper provides a condition for differentiability as well as an equivalent criterion
for Lipschitz continuity of singular normal distributions. Such distributions are of interest,
for instance, in stochastic optimization problems with probabilistic constraints, where
a comparatively small (nondegenerate-) normally distributed random vector induces a large
number of linear inequality constraints (e.g. networks with stochastic demands). The criterion
for Lipschitz continuity is established for the class of quasi-concave distributions which
the singular normal distribution belongs to.
Polyhedral discrepancies are relevant for the quantitative stability
of mixed-integer two-stage and chance constrained stochastic programs. We
study the problem of optimal scenario reduction for a discrete probability
distribution with respect to certain polyhedral discrepancies and develop
algorithms for determining the optimally reduced distribution approximately.
Encouraging numerical experience for optimal scenario reduction is provided.
Modeling several competitive leaders and followers acting in an electricity market
leads to coupled systems of mathematical programs with equilibrium constraints,
called equilibrium problems with equilibrium constraints (EPECs). We consider
a simplified model for competition in electricity markets under uncertainty of demand
in an electricity network
as a (stochastic) multi-leader-follower game. First order necessary conditions are
developed for the corresponding stochastic EPEC based on a result of Outrata.
For applying the general result an explicit representation of the co-derivative of
the normal cone mapping to a polyhedron is derived. Later the
co-derivative formula is used for verifying constraint qualifications and for identifying
$M$-stationary solutions of the stochastic EPEC if the demand is represented by a
finite number of scenarios.
Stability and Sensitivity of Optimization Problems with First Order Stochastic Dominance Constraints
(2007)
We analyze the stability and sensitivity of stochastic optimization problems with stochastic dominance constraints of first order. We consider general perturbations of the underlying probability measures in the space of regular measures equipped with a suitable discrepancy distance. We show that the graph of the feasible set mapping is closed under rather general assumptions. We obtain conditions for the continuity of the optimal value and upper-semicontinuity of the optimal solutions, as well as quantitative stability estimates of Lipschitz type.
Furthermore, we analyze the sensitivity of the optimal value and obtain upper and lower bounds for the directional
derivatives of the optimal value. The estimates are formulated in terms of the dual utility functions associated with the
dominance constraints.
We investigate the convexity of chance constraints with independent random variables. It will be shown, how concavity properties of the mapping related to the decision vector have to be combined with a suitable property of decrease for the marginal densities in order to arrive at convexity of the feasible set for large enough probability levels. It turns out that the required decrease can be verified for most prominent density functions. The results are applied then, to derive convexity of linear chance constraints with normally distributed stochastic coefficients when assuming independence of the rows of the coefficient matrix.
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.
This paper deals with the computation of regular coderivatives of
solution maps associated with a frequently arising class of generalized equations.
The constraint sets are given by (not necessarily convex) inequalities,
and we do not assume linear independence of gradients to active constraints.
The achieved results enable us to state several versions of sharp necessary optimality
conditions in optimization problems with equilibria governed by such
generalized equations. The advantages are illustrated by means of examples.
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.
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.
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.