Search Results
Joint dynamic probabilistic constraints with projected linear decision rules
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
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.
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.
Optimal control of the sweeping process
We formulate and study an optimal control problem for the sweeping (Moreau) process, where control functions enter the moving sweeping set. To the best of our knowledge, this is the first study in the literature devoted to optimal control of the sweeping process. We first establish an existence theorem of optimal solutions and then derive necessary optimality conditions for this optimal control problem of a new type, where the dynamics is governed by discontinuous differential inclusions with variable right-hand sides. Our approach to necessary optimality conditions is based on the method of discrete approximations and advanced tools of variational analysis and generalized differentiation. The final results obtained are given in terms of the initial data of the controlled sweeping process and are illustrated by nontrivial examples.
Task assignment, sequencing and path-planning in robotic welding cells
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
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.
(Sub-) Gradient formulae for probability functions of random inequality systems under Gaussian distribution
We consider probability functions of parameter-dependent random inequality systems under Gaussian distribution. As a main result, we provide an upper estimate for the Clarke subdifferential of such probability functions without imposing compactness conditions. A constraint qualification ensuring continuous differentiability is formulated. Explicit formulae are derived from the general result in case of linear random inequality systems. In the case of a constant coefficient matrix an upper estimate for even the smaller Mordukhovich subdifferential is proven.
Subdifferential characterization of probability functions under Gaussian distribution
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.
Critical objective size and calmness modulus in linear programming
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.
Conditioning of linear-quadratic two-stage stochastic optimization problems
In this paper a condition number for linear-quadratic two-stage stochastic optimization problems is introduced as the Lipschitz modulus of the multifunction assigning to a (discrete) probability distribution the solution set of the problem. Being the outer norm of the Mordukhovich coderivative of this multifunction, the condition number can be estimated from above explicitly in terms of the problem data by applying appropriate calculus rules. Here, a chain rule for the extended partial second-order subdifferential recently proved by Mordukhovich and Rockafellar plays a crucial role. The obtained results are illustrated for the example of two-stage stochastic optimization problems with simple recourse.