We present an adaptive grid refinement algorithm to solve probabilistic optimization problems with infinitely many random constraints. Using a bilevel approach, we iteratively aggregate inequalities that provide most information not in a geometric but in a probabilistic sense. This conceptual idea, for which a convergence proof is provided, is then adapted to an implementable algorithm. The efficiency of our approach when compared to naive methods based on uniform grid refinement is illustrated for a numerical test example as well as for a water reservoir problem with joint probabilistic filling level constraints.
Value at risk approach to producer's best response in electricity market with uncertain demand
(2021)
We deal with several sources of uncertainty in electricity markets. The independent system operator (ISO) maximizes the social welfare using chance constraints to hedge against discrepancies between the estimated and real electricity demand. We find an explicit solution of the ISO problem, and use it to tackle the problem of a producer. In our model, production as well as income of a producer are determined based on the estimated electricity demand predicted by the ISO, that is unknown to producers. Thus, each producer is hedging against the uncertainty of prediction of the demand using the value-at-risk approach. To illustrate our results, a numerical study of a producer's best response given a historical distribution of both estimated and real electricity demand is provided.
In this paper we investigate stochastic programs with joint chance constraints. We consider discrete scenario set and reformulate the problem by adding auxiliary variables. Since the resulting problem has a difficult feasible set, we regularize it. To decrease the dependence on the scenario number, we propose a numerical method by iteratively solving a master problem while adding Benders cuts. We find the solution of the slave problem (generating the Benders cuts) in a closed form and propose a heuristic method to decrease the number of cuts. We perform a numerical study by increasing the number of scenarios and compare our solution with a solution obtained by solving the same problem with continuous distribution.
We deal with several sources of uncertainty in electricity markets. The independent system operator (ISO) maximizes the social welfare using chance constraints to hedge against discrepancies between the estimated and real electricity
demand. We find an explicit solution of the ISO problem, and use it to tackle the
problem of a producer. In our model, production as well as income of a producer
are determined based on the estimated electricity demand predicted by the ISO, that
is unknown to producers. Thus, each producer is hedging against the uncertainty of
prediction of the demand using the value-at-risk approach. To illustrate our results, a
numerical study of a producer’s best response given a historical distribution of both
estimated and real electricity demand is provided.
Bilevel optimization is an increasingly important tool to model hierarchical decision making. However, the ability of modeling such settings makes bilevel problems hard to solve in theory and practice. In this paper, we add on the general difficulty of this class of problems by further incorporating convex black-box constraints in the lower level. For this setup, we develop a cutting-plane algorithm that computes approximate bilevel-feasible points. We apply this method to a bilevel model of the European gas market in which we use a joint chance constraint to model uncertain loads. Since the chance constraint is not available in closed form, this fits into the black-box setting studied before. For the applied model, we use further problem-specific insights to derive bounds on the objective value of the bilevel problem. By doing so, we are able to show that we solve the application problem to approximate global optimality. In our numerical case study we are thus able to evaluate the welfare sensitivity in dependence of the achieved safety level of uncertain load coverage.
We present a novel mathematical algorithm to assist gas network operators in managing uncertainty,
while increasing reliability of transmission and supply. As a result, we solve an optimization problem
with a joint probabilistic constraint over an infinite system of random inequalities. Such models arise
in the presence of uncertain parameters having partially stochastic and partially non-stochastic character.
The application that drives this new approach is a stationary network with uncertain demand
(which are stochastic due to the possibility of fitting statistical distributions based on historical measurements)
and with uncertain roughness coefficients in the pipes (which are uncertain but non-stochastic due to a lack of
attainable measurements).
We study the sensitivity of local uncertainties in the roughness coefficients and their impact on a highly reliable
network operation. In particular, we are going to answer the question, what is the maximum uncertainty that is
allowed (shaping a 'maximal' uncertainty set) around nominal roughness coefficients, such that random demands in
a stationary gas network can be satisfied at given high probability level for no matter which realization of
true roughness coefficients within the uncertainty set.
One ends up with a constraint, which is probabilistic with respect to the load of gas
and robust with respect to the roughness coefficients. We demonstrate how such constraints can be dealt with in
the framework of the so-called spheric-radial decomposition of multivariate Gaussian distributions.
The numerical solution of a corresponding optimization problem is illustrated.
The results might assist the network operator with the implementation
of cost-intensive roughness measurements.
Depending on whether a mathematical program with equilibrium constraints
(MPEC) is considered in its original or its enhanced (via KKT conditions) form, the assumed qualification
conditions as well as the derived necessary optimality conditions may differ significantly. In this paper, we
study this issue when imposing one of the weakest possible qualification conditions, namely the calmness of
the perturbation mapping associated with the respective generalized equations in both forms of the MPEC.
It is well known that the calmness property allows one to derive the so-called M-stationarity conditions. The
restrictiveness of assumptions and the strength of conclusions in the two forms of the MPEC is also strongly
related to the qualification conditions on the “lower level”. For instance, even under the Linear Independence
Constraint Qualification (LICQ) for a lower level feasible set described by C 1 functions, the calmness properties
of the original and the enhanced perturbation mapping are drastically different. When passing to C 1,1 data, this
difference still remains true under the weaker Mangasarian-Fromovitz Constraint Qualification, whereas under
LICQ both the calmness assumption and the derived optimality conditions are fully equivalent for the original
and the enhanced form of the MPEC. After clarifying these relations, we provide a compilation of practically
relevant consequences of our analysis in the derivation of necessary optimality conditions. The obtained results
are finally applied to MPECs with structured equilibria.
The paper considers the computation of the probability of feasible load constellations in a stationary gas
network with uncertain demand. More precisely, a network with a single entry and several
exits with uncertain loads is studied. Feasibility of a load constellation is understood in the sense of
an existing flow meeting these loads along with given pressure bounds in the pipes.
In a first step, feasibility of deterministic exit loads is characterized algebraically and these general
conditions are specified to networks involving at most one cycle.
This prerequisite is essential for determining probabilities in a stochastic setting when exit loads
are assumed to follow some (joint) Gaussian distribution when modeling uncertain customer demand.
The key of our approach is the application of the spheric-radial decomposition of Gaussian random
vectors coupled with Quasi Monte-Carlo sampling. This approach requires an efficient algorithmic
treatment of the mentioned algebraic relations moreover depending on a scalar parameter. Numerical
results are illustrated for different network examples and demonstrate a clear superiority in terms of
precision over simple generic Monte-Carlo sampling. They lead to fairly accurate probability values
even for moderate sample size.
We consider probability functions of parameter-dependent random inequality systems under
Gaussian distribution. As a main result, we provide an upper estimate for the Clarke subdifferential
of such probability functions without imposing compactness conditions. A constraint qualification
ensuring continuous differentiability is formulated. Explicit formulae are derived from the general
result in case of linear random inequality systems. In the case of a constant coefficient matrix an
upper estimate for even the smaller Mordukhovich subdifferential is proven.
We consider multistage stochastic linear optimization problems combining joint dynamic probabilistic constraints with hard constraints. We develop a method for projecting decision rules onto
hard constraints of wait-and-see type. We establish the relation between the original (infinite
dimensional) problem and approximating problems working with projections from different subclasses of decision policies. Considering the subclass of linear decision rules and a generalized
linear model for the underlying stochastic process with noises that are Gaussian or truncated
Gaussian, we show that the value and gradient of the objective and constraint functions of the
approximating problems can be computed analytically.