1,721,024 research outputs found
An Asynchronous Ensemble Bundle Method
No full textEfficiently optimizing complex nondifferentiable functions, composed by a sum of a large number of terms the computation of each of which may be costly, is a crucial task in many applications such as energy optimization. The use of HPC architectures may be required to obtain appropriate performances, but the existing parallelisation approaches, mostly based on the standard master-slave paradigm, do not scale well to a large number of cores. This has justified the recent surge of interest in asynchronous approaches that may allow a higher scalability. We propose a very general asynchronous approach that exploits the availability of multiple resources not only for the "oracles" (black-box) that compute the function components, but also for the solution of multiple master problems, ran in parallel, to provide a stream of potential iterates for the oracles. Each of the master problems is in principle a separate algorithm, typically one of the many variants of bundle methods with some specific setting for its (numerous) algorithmic parameters, which would converge towards an (approximate) optimal solution if ran in isolation. We add to the mix a principal entity managing their interaction, thereby obtaining an "ensemble (asynchronous) bundle" approach, and we examine how different underlying algorithms can withstand interventions of the principal entity (such as information sharing, stability centre updates, and "near points" substitutions) aimed at fostering harmonious collaboration between them towards the goal of more efficiently solving the problem while retaining the good convergence properties that they originally had. We show how our approach can work with a very wide selection of the practical nondifferentiable optimization algorithms proposed in the literature. We test the performance of our ensemble bundle approach on a significant industrial application, i.e., Lagrangian relaxations of the Unit Commitment problem
Incremental bundle methods using upper models
Full text linkWe propose a family of proximal bundle methods for minimizing sum-structured convex nondifferentiable functions which require two slightly uncommon assumptions, that are satisfied in many relevant applications: Lipschitz continuity of the functions and oracles which also produce upper estimates on the function values. In exchange, the methods: i) use upper models of the functions that allow to estimate function values at points where the oracle has not been called; ii) provide the oracles with more information about when the function computation can be interrupted, possibly diminishing their cost; iii) allow to skip oracle calls entirely for some of the component functions, not only at "null steps" but also at "serious steps"; iv) provide explicit and reliable a-posteriori estimates of the quality of the obtained solutions; v) work with all possible combinations of different assumptions on how the oracles deal with not being able to compute the function with arbitrary accuracy. We also discuss the introduction of constraints (or, more generally, of easy components) and use of (partly) aggregated models
Optimisation sous contrainte probabilistes : et applications en Management d’Energie
No full textIn optimization problems involving uncertainty, probabilistic constraints are an important tool for defining safety of decisions. In Energy management, many optimization problems have some underlying uncertainty. In particular this is the case of unit commitment problems. In this Thesis, we will investigate probabilistic constraints from a theoretical, algorithmic and applicative point of view. We provide new insights on differentiability of probabilistic constraints and on convexity results of feasible sets. New variants of bundle methods, both of proximal and level type, specially tailored for convex optimization under probabilistic constraints, are given and convergence shown. Both methods explicitly deal with evaluation errors in both the gradient and value of the probabilistic constraint. We also look at two applications from energy management: cascaded reservoir management with uncertainty on inflows and unit commitment with uncertainty on customer load. In both applications uncertainty is dealt with through the use of probabilistic constraints. The presented numerical results seem to indicate the feasibility of solving an optimization problem with a joint probabilistic constraint on a system having up to 200 constraints. This is roughly the order of magnitude needed in the applications. The differentiability results involve probabilistic constraints on uncertain linear and nonlinear inequality systems. In the latter case a convexity structure in the underlying uncertainty vector is required. The uncertainty vector is assumed to have a multivariate Gaussian or Student law. The provided gradient formulae allow for efficient numerical sampling schemes. For probabilistic constraints that can be rewritten through the use of Copulae, we provide new insights on convexity of the feasible set. These results require a generalized concavity structure of the Copulae, the marginal distribution functions of the underlying random vector and of the underlying inequality system. These generalized concavity properties may hold only on specific sets.Les contraintes en probabilité constituent un modèle pertinent pour gérer les incertitudes dans les problèmes de décision. En management d’énergie de nombreux problèmes d’optimisation ont des incertitudes sous-jacentes. En particulier c’est le cas des problèmes de gestion de la production au court-terme. Dans cette Thèse, nous investiguons les contraintes probabilistes sous l’angle théorique, algorithmique et applicative. Nous donnons quelques nouveaux résultats de différentiabilité des contraintes en probabilité et de convexité des ensembles admissibles. Des nouvelles variantes des méthodes de faisceaux « proximales » et « de niveaux » sont spécialement mises au point pour traiter des problèmes d’optimisation convexe sous contrainte en probabilité. Ces algorithmes gèrent en particulier, les erreurs d’évaluation de la contrainte en probabilité, ainsi que son gradient. La convergence vers une solution du problème est montrée. Enfin, nous examinons deux applications : l’optimisation d’une vallée hydraulique sous incertitude sur les apports et l’optimisation d’un planning de production sous incertitude sur la demande. Dans les deux cas nous utilisons une contrainte en probabilité pour gérer les incertitudes. Les résultats numériques présentés semblent montrer la faisabilité de résoudre des problèmes d’optimisation avec une contrainte en probabilité jointe portant sur un système de environ 200 contraintes. Il s’agit de l’ordre de grandeur nécessaire pour les applications. Les nouveaux résultats de différentiabilité concernent à la fois des contraintes en probabilité portant sur des systèmes linéaires et non-linéaires. Dans le deuxième cas, la convexité dans l’argument représentant le vecteur incertain est requise. Ce vecteur est supposé suivre une loi Gaussienne ou Student multi-variée. Les formules de gradient permettent l’application directe d’un schéma d’évaluation numérique efficient. Pour les contraintes en probabilité qui peuvent se réécrire à l’aide d’une Copule, nous donnons de nouveau résultats de convexité pour l’ensemble admissibles. Ces résultats requirent la concavité généralisée de la Copule, les distributions marginales sous-jacents et du système d’incertitude. Il est suffisant que ces propriétés de concavité généralisée tiennent sur un ensemble spécifique
Optimisation sous contrainte probabilistes : et applications en Management d’Energie
No full textIn optimization problems involving uncertainty, probabilistic constraints are an important tool for defining safety of decisions. In Energy management, many optimization problems have some underlying uncertainty. In particular this is the case of unit commitment problems. In this Thesis, we will investigate probabilistic constraints from a theoretical, algorithmic and applicative point of view. We provide new insights on differentiability of probabilistic constraints and on convexity results of feasible sets. New variants of bundle methods, both of proximal and level type, specially tailored for convex optimization under probabilistic constraints, are given and convergence shown. Both methods explicitly deal with evaluation errors in both the gradient and value of the probabilistic constraint. We also look at two applications from energy management: cascaded reservoir management with uncertainty on inflows and unit commitment with uncertainty on customer load. In both applications uncertainty is dealt with through the use of probabilistic constraints. The presented numerical results seem to indicate the feasibility of solving an optimization problem with a joint probabilistic constraint on a system having up to 200 constraints. This is roughly the order of magnitude needed in the applications. The differentiability results involve probabilistic constraints on uncertain linear and nonlinear inequality systems. In the latter case a convexity structure in the underlying uncertainty vector is required. The uncertainty vector is assumed to have a multivariate Gaussian or Student law. The provided gradient formulae allow for efficient numerical sampling schemes. For probabilistic constraints that can be rewritten through the use of Copulae, we provide new insights on convexity of the feasible set. These results require a generalized concavity structure of the Copulae, the marginal distribution functions of the underlying random vector and of the underlying inequality system. These generalized concavity properties may hold only on specific sets.Les contraintes en probabilité constituent un modèle pertinent pour gérer les incertitudes dans les problèmes de décision. En management d’énergie de nombreux problèmes d’optimisation ont des incertitudes sous-jacentes. En particulier c’est le cas des problèmes de gestion de la production au court-terme. Dans cette Thèse, nous investiguons les contraintes probabilistes sous l’angle théorique, algorithmique et applicative. Nous donnons quelques nouveaux résultats de différentiabilité des contraintes en probabilité et de convexité des ensembles admissibles. Des nouvelles variantes des méthodes de faisceaux « proximales » et « de niveaux » sont spécialement mises au point pour traiter des problèmes d’optimisation convexe sous contrainte en probabilité. Ces algorithmes gèrent en particulier, les erreurs d’évaluation de la contrainte en probabilité, ainsi que son gradient. La convergence vers une solution du problème est montrée. Enfin, nous examinons deux applications : l’optimisation d’une vallée hydraulique sous incertitude sur les apports et l’optimisation d’un planning de production sous incertitude sur la demande. Dans les deux cas nous utilisons une contrainte en probabilité pour gérer les incertitudes. Les résultats numériques présentés semblent montrer la faisabilité de résoudre des problèmes d’optimisation avec une contrainte en probabilité jointe portant sur un système de environ 200 contraintes. Il s’agit de l’ordre de grandeur nécessaire pour les applications. Les nouveaux résultats de différentiabilité concernent à la fois des contraintes en probabilité portant sur des systèmes linéaires et non-linéaires. Dans le deuxième cas, la convexité dans l’argument représentant le vecteur incertain est requise. Ce vecteur est supposé suivre une loi Gaussienne ou Student multi-variée. Les formules de gradient permettent l’application directe d’un schéma d’évaluation numérique efficient. Pour les contraintes en probabilité qui peuvent se réécrire à l’aide d’une Copule, nous donnons de nouveau résultats de convexité pour l’ensemble admissibles. Ces résultats requirent la concavité généralisée de la Copule, les distributions marginales sous-jacents et du système d’incertitude. Il est suffisant que ces propriétés de concavité généralisée tiennent sur un ensemble spécifique
Eventual convexity of chance constrained feasible sets
No full textInternational audienceIn decision-making problems where uncertainty plays a key role and decisions have to be taken prior to observing uncertainty, chance constraints are a strong modelling tool for defining safety of decisions. These constraints request that a random inequality system depending on a decision vector has to be satisfied with a high probability. The characteristics of the feasible set of such chance constraints depend on the constraint mapping of the random inequality system, the underlying law of uncertainty and the probability level. One characteristic of particular interest is convexity. Convexity can be shown under fairly general conditions on the underlying law of uncertainty and on the constraint mapping, regardless of the probability-level. In some situations, convexity can only be shown when the probability-level is high enough. This is defined as eventual convexity. In this paper, we will investigate further how eventual convexity can be assured for specially structured chance constraints involving Copulae. The Copulae have to exhibit generalized concavity properties. In particular, we will extend recent results and exhibit a clear link between the generalized concavity properties of the various mappings involved in the chance constraint for the result to hold. Various examples show the strength of the provided generalization
Second-order differentiability of probability functions
No full textInternational audienceIn this paper, we study second-order differentiability properties of probability functions. We present conditions under which probability functions involving nonlinear systems and Gaussian (or Student) multi-variate random vectors are twice continuously differentiable. We provide an expression for their Hessian that can be useful in numerical methods for solving probabilistic constrained optimization problems
Optimisation sous contrainte probabilistes (et applications en Management d Energie)
No full textLes contraintes en probabilité constituent un modèle pertinent pour gérer les incertitudes dans les problèmes de décision. En management d énergie de nombreux problèmes d optimisation ont des incertitudes sous-jacentes. En particulier c est le cas des problèmes de gestion de la production au court-terme. Dans cette Thèse, nous investiguons les contraintes probabilistes sous l angle théorique, algorithmique et applicative. Nous donnons quelques nouveaux résultats de différentiabilité des contraintes en probabilité et de convexité des ensembles admissibles. Des nouvelles variantes des méthodes de faisceaux proximales et de niveaux sont spécialement mises au point pour traiter des problèmes d optimisation convexe sous contrainte en probabilité. Ces algorithmes gèrent en particulier, les erreurs d évaluation de la contrainte en probabilité, ainsi que son gradient. La convergence vers une solution du problème est montrée. Enfin, nous examinons deux applications : l optimisation d une vallée hydraulique sous incertitude sur les apports et l optimisation d un planning de production sous incertitude sur la demande. Dans les deux cas nous utilisons une contrainte en probabilité pour gérer les incertitudes. Les résultats numériques présentés semblent montrer la faisabilité de résoudre des problèmes d optimisation avec une contrainte en probabilité jointe portant sur un système de environ 200 contraintes. Il s agit de l ordre de grandeur nécessaire pour les applications. Les nouveaux résultats de différentiabilité concernent à la fois des contraintes en probabilité portant sur des systèmes linéaires et non-linéaires. Dans le deuxième cas, la convexité dans l argument représentant le vecteur incertain est requise. Ce vecteur est supposé suivre une loi Gaussienne ou Student multi-variée. Les formules de gradient permettent l application directe d un schéma d évaluation numérique efficient. Pour les contraintes en probabilité qui peuvent se réécrire à l aide d une Copule, nous donnons de nouveau résultats de convexité pour l ensemble admissibles. Ces résultats requirent la concavité généralisée de la Copule, les distributions marginales sous-jacents et du système d incertitude. Il est suffisant que ces propriétés de concavité généralisée tiennent sur un ensemble spécifique.In optimization problems involving uncertainty, probabilistic constraints are an important tool for defining safety of decisions. In Energy management, many optimization problems have some underlying uncertainty. In particular this is the case of unit commitment problems. In this Thesis, we will investigate probabilistic constraints from a theoretical, algorithmic and applicative point of view. We provide new insights on differentiability of probabilistic constraints and on convexity results of feasible sets. New variants of bundle methods, both of proximal and level type, specially tailored for convex optimization under probabilistic constraints, are given and convergence shown. Both methods explicitly deal with evaluation errors in both the gradient and value of the probabilistic constraint. We also look at two applications from energy management: cascaded reservoir management with uncertainty on inflows and unit commitment with uncertainty on customer load. In both applications uncertainty is dealt with through the use of probabilistic constraints. The presented numerical results seem to indicate the feasibility of solving an optimization problem with a joint probabilistic constraint on a system having up to 200 constraints. This is roughly the order of magnitude needed in the applications. The differentiability results involve probabilistic constraints on uncertain linear and nonlinear inequality systems. In the latter case a convexity structure in the underlying uncertainty vector is required. The uncertainty vector is assumed to have a multivariate Gaussian or Student law. The provided gradient formulae allow for efficient numerical sampling schemes. For probabilistic constraints that can be rewritten through the use of Copulae, we provide new insights on convexity of the feasible set. These results require a generalized concavity structure of the Copulae, the marginal distribution functions of the underlying random vector and of the underlying inequality system. These generalized concavity properties may hold only on specific sets.CHATENAY MALABRY-Ecole centrale (920192301) / SudocSudocFranceF
Gradient formulae for nonlinear probabilistic constraints with Gaussian and Gaussian-like distributions
Full text linkProbabilistic 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
A characterization of the subdifferential of singular gaussian distribution functions
No full textInternational audienc
- …
