Search

Probability functions appear in constraints of many optimization problems in practice and have become quite popular. Understanding their first-order properties has proven useful, not only theoretically but also in implementable algorithms, giving rise to competitive algorithms in several situations. Probability functions are built up from a random vector belonging to some parameter-dependent subset of the range of a given random vector. In this paper, we investigate first order information of probability functions specified through a convex-valued set-valued application. We provide conditions under which the resulting probability function is indeed locally Lipschitzian as well as subgradient formulae. The resulting formulae are made concrete in a classic optimization setting and put to work in an illustrative example coming from an energy application.

We consider a revenue maximization model, in which a company aims at designing a menu of contracts, given a population of customers. A standard approach consists in constructing an incentive-compatible continuum of contracts, i.e., a menu composed of an infinite number of contracts, where each contract is especially adapted to an infinitesimal customer, taking his type into account. Nonetheless, in many applications, the company is constrained to offering a limited number of contracts. We show that this question reduces to an optimal quantization problem, similar to the pruning problem that appeared in the max-plus based numerical methods in optimal control. We develop a new quantization algorithm, which, given an initial menu of contracts, iteratively prunes the less important contracts, to construct an implementable menu of the desired cardinality, while minimizing the revenue loss. We apply this algorithm to solve a pricing problem with price-elastic demand, originating from the electricity retail market. Numerical results show an improved performance by comparison with earlier pruning algorithms.

Optimization problems with uncertainty in the constraints occur in many applications. Particularly, probability functions present a natural form to deal with this situation. Nevertheless, in some cases, the resulting probability functions are nonsmooth. This motivates us to propose a regularization employing the Moreau envelope of a scalar representation of the vector inequality. More precisely, we consider a probability function which covers most of the general classes of probabilistic constraints: $$\varphi(x)=\mathbb{P}(\Phi(x,\xi)\in -\mathcal{K}),$$ where $\mathcal{K}$ is a convex cone of a Banach space. The conic inclusion $\Phi (x,\xi) \in - \mathcal{K}$ represents an abstract system of inequalities, and $\xi$ is a random vector. We propose a regularization by applying the Moreau envelope to the scalarization of the function $\Phi$. In this paper, we demonstrate, under mild assumptions, the smoothness of such a regularization and that it satisfies a type of variational convergence to the original probability function. Consequently, when considering an appropriately structured problem involving probabilistic constraints, we can thus entail the convergence of the minimizers of the regularized approximate problems to the minimizers of the original problem. Finally, we illustrate our results with examples and applications in the field of (nonsmooth) joint, semidefinite and probust chance constrained optimization problems.

We consider a control problem for a heterogeneous population composed of agents able to switch at any time between different options. The controller aims to maximize an average gain per time unit, supposing that the population is of infinite size. This leads to an ergodic control problem for a "mean-field" Markov Decision Process in which the state space is a product of simplices, and the population evolves according to controlled linear dynamics. By exploiting contraction properties of the dynamics in Hilbert's projective metric, we prove that the infinite-dimensional ergodic eigenproblem admits a solution and show that the latter is in general non unique. This allows us to obtain optimal strategies, and to quantify the gap between steady-state strategies and optimal ones. In particular, we prove in the one-dimensional case that there exist cyclic policies -- alternating between discount and profit taking stages -- which secure a greater gain than constant-price policies. On numerical aspects, we develop a policy iteration algorithm with "on-the-fly" generated transitions, specifically adapted to decomposable models, leading to substantial memory savings. We finally apply our results on realistic instances coming from an electricity pricing problem encountered in the retail markets, and numerically observe the emergence of cyclic promotions for sufficient inertia in the customer behavior., Comment: The present version (v3) is an extended version of an article originally published in the Proceedings of CDC 2022

We consider the profit-maximization problem solved by an electricity retailer who aims at designing a menu of contracts. This is an extension of the unit-demand envy-free pricing problem: customers aim to choose a contract maximizing their utility based on a reservation bill and multiple price coefficients (attributes). A basic approach supposes that the customers have deterministic utilities; then, the response of each customer is highly sensitive to price since it concentrates on the best offer. A second classical approach is to consider logit model to add a probabilistic behavior in the customers' choices. To circumvent the intrinsic instability of the former and the resolution difficulties of the latter, we introduce a quadratically regularized model of customer's response, which leads to a quadratic program under complementarity constraints (QPCC). This allows to robustify the deterministic model, while keeping a strong geometrical structure. In particular, we show that the customer's response is governed by a polyhedral complex, in which every polyhedral cell determines a set of contracts which is effectively chosen. Moreover, the deterministic model is recovered as a limit case of the regularized one. We exploit these geometrical properties to develop a pivoting heuristic, which we compare with implicit or non-linear methods from bilevel programming, showing the effectiveness of the approach. Throughout the paper, the electricity retailer problem is our guideline, and we present a numerical study on this application case., Comment: 37 pages, 9 figures

We propose a generic multistage stochastic model for the Alternating Current Optimal Power Flow (AC OPF) problem for radial distribution networks, to account for the random electricity production of renewable energy sources and dynamic constraints of storage systems. We consider single-phase radial networks. Radial three-phase balanced networks (medium-voltage distribution networks typically have this structure) reduce to the former case. This induces a large scale optimization problem, which, given the non-convex nature of the AC OPF, is generally challenging to solve to global optimality. We derive a priori conditions guaranteeing a vanishing relaxation gap for the multi-stage AC OPF problem, which can thus be solved using convex optimization algorithms. We also give an a posteriori upper bound on the relaxation gap. In particular, we show that a null or low relaxation gap may be expected for applications with light reverse power flows or if sufficient storage capacities with low cost are available. Then, we discuss the validity of our results when incorporating voltage regulation devices. Finally, we illustrate our results on problems of planning of a realistic distribution feeder with distributed solar production and storage systems. Scenario trees for solar production are constructed from a stochastic model, by a quantile-based algorithm.

In decision-making problems under uncertainty, probabilistic constraints are a valuable tool to express safety of decisions. They result from taking the probability measure of a given set of random inequalities depending on the decision vector. Even if the original set of inequalities is convex, this favourable property is not immediately transferred to the probabilistically constrained feasible set and may in particular depend on the chosen safety level. In this paper, we provide results guaranteeing the convexity of feasible sets to probabilistic constraints when the safety level is greater than a computable threshold. Our results extend all the existing ones and also cover the case where decision vectors belong to Banach spaces. The key idea in our approach is to reveal the level of underlying convexity in the nominal problem data (e.g., concavity of the probability function) by auxiliary transforming functions. We provide several examples illustrating our theoretical developments.

Multi stage stochastic programs arise in many applications from engineering whenever a set of inventories or stocks has to be valued. Such is the case in seasonal storage valuation of a set of cascaded reservoir chains in hydro management. A popular method is Stochastic Dual Dynamic Programming (SDDP), especially when the dimensionality of the problem is large and Dynamic programming no longer an option. The usual assumption of SDDP is that uncertainty is stage-wise independent, which is highly restrictive from a practical viewpoint. When possible, the usual remedy is to increase the state-space to account for some degree of dependency. In applications this may not be possible or it may increase the state space by too much. In this paper we present an alternative based on keeping a functional dependency in the SDDP - cuts related to the conditional expectations in the dynamic programming equations. Our method is based on popular methodology in mathematical finance, where it has progressively replaced scenario trees due to superior numerical performance. On a set of numerical examples, we too show the interest of this way of handling dependency in uncertainty, when combined with SDDP. Our method is readily available in the open source software package StOpt., Comment: 26 pages, 10 figures