Search Results
Dynamic probabilistic constraints under continuous random distributions
The paper investigates analytical properties of dynamic probabilistic constraints (chance constraints). The underlying random distribution is supposed to be continuous. In the first part, a general multistage model with decision rules depending on past observations of the random process is analyzed. Basic properties like (weak sequential) (semi-) continuity of the probability function or existence of solutions are studied. It turns out that the results differ significantly according to whether decision rules are embedded into Lebesgue or Sobolev spaces. In the second part, the simplest meaningful two-stage model with decision rules from L 2 is investigated. More specific properties like Lipschitz continuity and differentiability of the probability function are considered. Explicitly verifiable conditions for these properties are provided along with explicit gradient formulae in the Gaussian case. The application of such formulae in the context of necessary optimality conditions is discussed and a concrete identification of solutions presented.
Discrepancy distances and scenario reduction in two-stage stochastic integer programming
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.
On the algorithmic solution of optimization problems subject to probabilistic/robust (probust) constraints
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
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.
Generalized gradients for probabilistic/robust (probust) constraints
Probability functions are a powerful modelling tool when seeking to account for uncertainty in optimization problems. In practice, such uncertainty may result from different sources for which unequal information is available. A convenient combination with ideas from robust optimization then leads to probust functions, i.e., probability functions acting on generalized semi-infinite inequality systems. In this paper we employ the powerful variational tools developed by Boris Mordukhovich to study generalized differentiation of such probust functions. We also provide explicit outer estimates of the generalized subdifferentials in terms of nominal data.
On convex lower-level black-box constraints in bilevel optimization with an application to gas market models with chance constraints
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.
Gradient formulae for nonlinear probabilistic constraints with Gaussian and aussian-like distributions
Probabilistic constraints represent a major model of stochastic optimization. A possible approach for solving probabilistically constrained optimization problems consists in applying nonlinear programming methods. In order to do so, one has to provide sufficiently precise approximations for values and gradients of probability functions. For linear probabilistic constraints under Gaussian distribution this can be successfully done by analytically reducing these values and gradients to values of Gaussian distribution functions and computing the latter, for instance, by Genz’ code. For nonlinear models one may fall back on the spherical-radial decomposition of Gaussian random vectors and apply, for instance, Deák’s sampling scheme for the uniform distribution on the sphere in order to compute values of corresponding probability functions. The present paper demonstrates how the same sampling scheme can be used in order to simultaneously compute gradients of these probability functions. More precisely, we prove a formula representing these gradients in the Gaussian case as a certain integral over the sphere again. Later, the result is extended to alternative distributions with an emphasis on the multivariate Student (or T-) distribution.
Structural properties of linear probabilistic constraints
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 thefeasible set are precisely characterized at the same time. The relation between feasible sets with negative and nonnegative right-hand side is revealed. Finally, an existence result is formulated for the more difficult case of joint probabilistic constraints.