Search Results
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.
A turnpike property for optimal control problems with dynamic probabilistic constraints
In this paper we consider systems that are governed by linear time-discrete dynamics with an initial condition, additive random perturbations in each step and a terminal condition for the expected values. We study optimal control problems where the objective function consists of a term of tracking type for the expected values and a control cost. In addition, the feasible states have to satisfy a conservative probabilistic constraint that requires that the probability that the trajectories remain in a given set F is greater than or equal to a given lower bound. An application are optimal control problems related to storage management systems with uncertain in- and output. We give sufficient conditions that imply that the optimal expected trajectories remain close to a certain state that can be characterized as the solution of an optimal control problem without prescribed initial- and terminal condition. In this way we contribute to the study of the turnpike phenomenon that is well-known in mathematical economics and make a step towards the extension of the turnpike theory to problems with probabilistic constraints.
An enumerative formula for the spherical cap discrepancy
The spherical cap discrepancy is a widely used measure for how uniformly a sample of points on the sphere is distributed. Being hard to compute, this discrepancy measure is typically replaced by some lower or upper estimates when designing optimal sampling schemes for the uniform distribution on the sphere. In this paper, we provide a fully explicit, easy to implement enumerative formula for the spherical cap discrepancy. Not surprisingly, this formula is of combinatorial nature and, thus, its application is limited to spheres of small dimension and moderate sample sizes. Nonetheless, it may serve as a useful calibrating tool for testing the efficiency of sampling schemes and its explicit character might be useful also to establish necessary optimality conditions when minimizing the discrepancy with respect to a sample of given size.
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.
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.
Controlled polyhedral sweeping processes: Existence, stability, and optimality conditions
This paper is mainly devoted to the study of controlled sweeping processes with polyhedral moving sets in Hilbert spaces. Based on a detailed analysis of truncated Hausdorff distances between moving polyhedra, we derive new existence and uniqueness theorems for sweeping trajectories corresponding to various classes of control functions acting in moving sets. Then we establish quantitative stability results, which provide efficient estimates on the sweeping trajectory dependence on controls and initial values. Our final topic, accomplished in finite-dimensional state spaces, is deriving new necessary optimality and suboptimality conditions for sweeping control systems with endpoint constrains by using constructive discrete approximations.