Search Results
Analysis of M-stationary points to an EPEC modeling oligopolistic competition in an electricity spot market
2009, Henrion, René, Outrata, Jií̌, Surowiec, Thomas
We consider an equilibrium problem with equilibrium constraints (EPEC) as it arises from modeling competition in an electricity spot market (under ISO regulation). For a characterization of equilibrium solutions, so-called M-stationarity conditions are derived. This requires a structural analysis of the problem first (constraint qualifications, strong regularity). Second, the calmness property of a certain multifunction has to be verified in order to justify M-stationarity. Third, for stating the stationarity conditions, the co-derivative of a normal cone mapping has to be calculated. Finally, the obtained necessary conditions are made fully explicit in terms of the problem data for one typical constellation. A simple two-settlements example serves as an illustration.
Task assignment, sequencing and path-planning in robotic welding cells
2013, Landry, Chantal, Welz, Wolfgang, Henrion, René, Hömberg, Dietmar, Skutella, Martin
A workcell composed of a workpiece and several welding robots is considered. We are interested in minimizing the makespan in the workcell. Hence, one needs i) to assign tasks between the robots, ii) to do the sequencing of the tasks for each robot and iii) to compute the fastest collisionfree paths between the tasks. Up to now, task assignment and path-planning were always handled separately, the former being a typical Vehicle Routing Problem whereas the later is modelled using an optimal control problem. In this paper, we present a complete algorithm which combines discrete optimization techniques with collision detection and optimal control problems efficiently
A gradient formula for linear chance constraints under Gaussian distribution
2012, Henrion, René, Möller, Andris
We provide an explicit gradient formula for linear chance constraints under a (possibly singular) multivariate Gaussian distribution. This formula allows one to reduce the calculus of gradients to the calculus of values of the same type of chance constraints (in smaller dimension and with different distribution parameters). This is an important aspect for the numerical solution of stochastic optimization problems because existing efficient codes for e.g., calculating singular Gaussian distributions or regular Gaussian probabilities of polyhedra can be employed to calculate gradients at the same time. Moreover, the precision of gradients can be controlled by that of function values which is a great advantage over using finite difference approximations. Finally, higher order derivatives are easily derived explicitly. The use of the obtained formula is illustrated for an example of a transportation network with stochastic demands.
Gradient formulae for nonlinear probabilistic constraints with Gaussian and aussian-like distributions
2013, van Ackooij, Wim, Henrion, René
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.
Strong stationary solutions to equilibrium problems with equilibrium constraints with applications to an electricity spot market model
2009, Henrion, René, Outrata, Jiří, Surowiec, Thomas
Literaturverz. S. 26 In this paper, we consider the characterization of strong stationary solutions to equilibrium problems with equilibrium constraints (EPECs). Assuming that the underlying generalized equation satisfies strong regularity in the sense of Robinson, an explicit multiplier-based stationarity condition can be derived. This is applied then to an equilibrium model arising from ISO-regulated electricity spot markets.
Subdifferential characterization of probability functions under Gaussian distribution
2018, Hantoute, Abderrahim, Henrion, René, Pérez-Aros, Pedro
Probability functions figure prominently in optimization problems of engineering. They may be nonsmooth even if all input data are smooth. This fact motivates the consideration of subdifferentials for such typically just continuous functions. The aim of this paper is to provide subdifferential formulae of such functions in the case of Gaussian distributions for possibly infinite-dimensional decision variables and nonsmooth (locally Lipschitzian) input data. These formulae are based on the spheric-radial decomposition of Gaussian random vectors on the one hand and on a cone of directions of moderate growth on the other. By successively adding additional hypotheses, conditions are satisfied under which the probability function is locally Lipschitzian or even differentiable.
On M-stationary points for a stochastic equilibrium problem under equilibrium constraints in electricity spot market modeling
2007, Henrion, René, Römisch, Werner
Modeling several competitive leaders and followers acting in an electricity market leads to coupled systems of mathematical programs with equilibrium constraints, called equilibrium problems with equilibrium constraints (EPECs). We consider a simplified model for competition in electricity markets under uncertainty of demand in an electricity network as a (stochastic) multi-leader-follower game. First order necessary conditions are developed for the corresponding stochastic EPEC based on a result of Outrata [17]. For applying the general result an explicit representation of the co-derivative of the normal cone mapping to a polyhedron is derived (Proposition 3.2). Later the co-derivative formula is used for verifying constraint qualifications and for identifying M-stationary solutions of the stochastic EPEC if the demand is represented by a finite number of scenarios.
Joint dynamic probabilistic constraints with projected linear decision rules
2016, Guigues, Vincent, Henrion, René
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.
Some remarks on stability of generalized equations
2012, Henrion, René, Kruger, Alexander, Outrata, Jiří
The paper concerns the computation of the graphical derivative and the regular (Fréchet) coderivative of the solution map to a class of generalized equations, where the multi-valued term amounts to the regular normal cone to a (possibly nonconvex) set given by C2 inequalities. Instead of the Linear Independence qualification condition, standardly used in this context, one assumes a combination of the Mangasarian-Fromovitz and the Constant Rank qualification conditions. On the basis of the obtained generalized derivatives, new optimality conditions for a class of mathematical programs with equilibrium constrains are derived, and a workable characterization of the isolated calmness of the considered solution map is provided.
Critical objective size and calmness modulus in linear programming
2015, Cánovas, Maria J., Henrion, René, Parra, Juan, Toledo, F. Javier
This paper introduces the concept of critical objective size associated with a linear program in order to provide operative point-based formulas (only involving the nominal data, and not data in a neighborhood) for computing or estimating the calmness modulus of the optimal set (argmin) mapping under uniqueness of nominal optimal solution and perturbations of all coefficients. Our starting point is an upper bound on this modulus given in [4]. In this paper we prove that this upper bound is attained if and only if the norm of the objective function coefficient vector is less than or equal to the critical objective size. This concept also allows us to obtain operative lower bounds on the calmness modulus. We analyze in detail an illustrative example in order to xplore some strategies that can improve the referred upper and lower bounds.