On safe tractable approximations of chance constraints

A natural way to handle optimization problem with data affected by stochastic uncertainty is to pass to a chance constrained version of the problem, where candidate solutions should satisfy the randomly perturbed constraints with probability at least 1 − ?. While being attractive from modeling viewpoint, chance constrained problems “as they are” are, in general, computationally intractable. In this survey paper, we overview several simulation-based and simulation-free computationally tractable approximations of chance constrained convex programs, primarily, those of chance constrained linear, conic quadratic and semidefinite programming.     

Chapter 13 Satisficing DEA models under chance constraints

DEA (Data Envelopment Analysis) models and concepts are formulated here in terms of the P-Models of Chance Constrained Programming, which are then modified to contact the satisficing concepts of H.A. Simon. Satisficing is thereby added as a third category to the efficiency/inefficiency dichotomies that have heretofore prevailed in DEA. Formulations include cases in which inputs and outputs are stochastic, as well as cases in which only the outputs are stochastic. Attention is also devoted to situations in which variations in inputs and outputs are related through a common random variable. Extensions include new developments in goal programming with deterministic equivalents for the corresponding satisficing models under chance constraints.     

On relations between chance constrained and penalty function problems under discrete distributions

We extend the theory of penalty functions to stochastic programming problems with nonlinear inequality constraints dependent on a random vector with known distribution. We show that the problems with penalty objective, penalty constraints and chance constraints are asymptotically equivalent under discretely distributed random parts. This is a complementary result to Branda (Kybernetika 48(1):105–122, 2012a), Branda and Dupa?ová (Ann Oper Res 193(1):3–19, 2012), and Ermoliev et al. (Ann Oper Res 99:207–225, 2000) where the theorems were restricted to continuous distributions only. We propose bounds on optimal values and convergence of optimal solutions. Moreover, we apply exact penalization under modified calmness property to improve the results.     

Estimated stochastic programs with chance constraints

We will consider a non-parametric estimation procedure for chance-constrained stochastic programs where the random parameters appear on the right-hand side of linear constraints for the decision variable. The assumed independence of the components of the random right-hand side data results in stochastic programs with a separability structure in the constraints. We estimate the unknown probability distribution of the random right-hand side data via isotonic regression estimates of increasing hazard rates. Our choice of the estimates was motivated by the relationship between logarithmic concave measures and increasing hazard rate distributions. We establish large deviation results for optimal values and optimal solution sets of the estimated programs. Finally, we discuss the numerical treatment of the estimated chance-constrained programs and report on a test run.     

Controlled Ornstein-Uhlenbeck process with chance constraints

In Ref. 1, existence and optimality conditions were given for control systems whose dynamics are determined by a linear stochastic differential equation with linear feedback controls; moreover, the state variables satisfy probability constraints. Here, for the simplest case of such a model, the Ornstein-Uhlenbeck velocity process, we evaluate the necessary conditions derived in Ref. 1 and compute a time-optimal control such that a given threshold value > 0 is crossed with probability of at least 1 – .This work was supported by the Sonderforschungsbereiche 21 and 72, University of Bonn, Bonn, West Germany.     

Analytic approximation and differentiability of joint chance constraints

ABSTRACT

An inner–outer approximation approach was recently developed to solve single chance constrained optimization (SCCOPT) problems. In this paper, we extend this approach to address joint chance constrained optimization (JCCOPT) problems. Using an inner–outer approximation, two smooth parametric optimization problems are defined whose feasible sets converge to the feasible set of JCCOPT from inside and outside, respectively. Any optimal solution of the inner approximation problem is a priori feasible to the JCCOPT. As the approximation parameter tends to zero, a subsequence of the solutions of the inner and outer problems, respectively, converge asymptotically to an optimal solution of the JCCOPT. As a main result, the continuous differentiability of the probability function of a joint chance constraint is obtained by examining the uniform convergence of the gradients of the parametric approximations.     

Improvement of approximations for the distributions of multinomial goodness-of-fit statistics under nonlocal alternatives

Cressie and Read (J. Roy. Statist. Soc. B 46 (1984) 440–464) introduced the power divergence statistics, R^a, as multinomial goodness-of-fit statistics. Each R^a has a limiting noncentral chi-square distribution under a local alternative and has a limiting normal distribution under a nonlocal alternative. Taneichi et al. (J. Multivariate Anal. 81 (2002) 335–359) derived an asymptotic approximation for the distribution of R^a under local alternatives. In this paper, using multivariate Edgeworth expansion for a continuous distribution, we show how the approximation based on the limiting normal distribution of R^a under nonlocal alternatives can be improved. We apply the expansion to the power approximation for R^a. The results of numerical investigation show that the proposed power approximation is very effective for the likelihood ratio test.     

General sum games with joint chance constraints

We consider an $n$-player non-cooperative game with continuous strategy sets. The strategy set of each player contains a set of stochastic linear constraints. We model the stochastic linear constraints of each player as a joint chance constraint. We assume that the row vectors of a matrix defining the stochastic constraints of each player are independent and each row vector follows a multivariate normal distribution. Under certain conditions, we show the existence of a Nash equilibrium for this game.     

Relaxations of linear programming problems with first order stochastic dominance constraints

Linear stochastic programming problems with first order stochastic dominance (FSD) constraints are non-convex. For their mixed 0-1 linear programming formulation we present two convex relaxations based on second order stochastic dominance (SSD). We develop necessary and sufficient conditions for FSD, used to obtain a disjunctive programming formulation and to strengthen one of the SSD-based relaxations.     

Fuzzy turnover rate chance constraints portfolio model

One concern of many investors is to own the assets which can be liquidated easily. Thus, in this paper, we incorporate portfolio liquidity in our proposed model. Liquidity is measured by an index called turnover rate. Since the return of an asset is uncertain, we present it as a trapezoidal fuzzy number and its turnover rate is measured by fuzzy credibility theory. The desired portfolio turnover rate is controlled through a fuzzy chance constraint. Furthermore, to manage the portfolios with asymmetric investment return, other than mean and variance, we also utilize the third central moment, the skewness of portfolio return. In fact, we propose a fuzzy portfolio mean–variance–skewness model with cardinality constraint which combines assets limitations with liquidity requirement. To solve the model, we also develop a hybrid algorithm which is the combination of cardinality constraint, genetic algorithm, and fuzzy simulation, called FCTPM.     

Discrete approximations to spherically symmetric distributions

Summary We consider the approximation of spherically symmetric distributions in ^d by linear combinations of Heaviside step functions or Dirac delta functions. The approximations are required to faithfully reproduce as many moments as possible. We discuss stable methods of computing such approximations, taking advantage of the close connection with Gauss-Christoffel quadrature. Numerical results are presented for the distributions of Maxwell, Bose-Einstein, and Fermi-Dirac.Dedicated to Fritz Bauer on the occasion of his 60th birthdayWork supported in part by the National Science Foundation under Grant MCS-7927158A1     

Spline approximations to spherically symmetric distributions

Summary We discuss the problem of approximating a functionf of the radial distancer in ^d on 0r< by a spline function of degreem withn (variable) knots. The spline is to be constructed so as to match the first 2n moments off. We show that if a solution exists, it can be obtained from ann-point Gauss-Christoffel quadrature formula relative to an appropriate moment functional or, iff is suitably restricted, relative to a measure, both depending onf. The moment functional and the measure may or may not be positive definite. Pointwise convergence is discussed asn. Examples are given including distributions from statistical mechanics.The work of the first author was supported in part by the National Science Foundation under grant DCR-8320561.     

Analytical approximations for the solution of chance constrained optimization problems

Uncertain influences are inherent in many practical processes, stemming for instance from measurement errors in process optimization or missing knowledge about the future behavior of a given system, e.g., the financial markets. Therefore, it is desirable to explicitly consider uncertainties when optimizing such processes. One possible approach for this task is the usage of chance constrained optimization (CCOPT), which allows that the constraints are only held with a certain probability level. This enables the user to make a compromised decision between reliability and profitability. Solving CCOPT problems usually consists of two steps. First, transforming the chance constraints into deterministic ones and then solving the transformed problem with a standard NLP solver. Depending on the underlying process, several approaches exist for the transformation. Here, we investigate the usage of so called analytical approximations (AAs). In general, AA approaches do not lead to an exact deterministic representation of CCOPT problems. Nonetheless, it can be shown that a solution obtained by AA is always feasible for the original problem. Furthermore, the corresponding optimization problem generated by AA is computationally more tractable than the original formulation, making these approaches interesting for larger scale processes. We propose a new AA method and present a comparison with existing AA approaches, considering efficiency and suitability. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On approximations to generalized Poisson distributions

In this paper three methods of the construction of approximations to generalized Poisson distributions are considered: approximation by a normal law, approximation by asymptotic distributions, the so-called Robbins mixtures, and approximation with the help of asymptotic expansions. Uniform and (for the first two methods) nonuniform estimates of the accuracy of the corresponding approximations are given. Some estimates for the concentration functions of generalized Poisson distributions are also presented. Supported by the Russian Foundation for Fundamental Research (grant No. 93-01-01446). Proceedings of the XVII Seminar on Stability Problems for Stochastic Models, Kazan, Russia, 1995, Part II.     

Second-order optimality conditions using approximations for nonsmooth vector optimization problems under inclusion constraints

Second-order necessary conditions and sufficient conditions for optimality in nonsmooth vector optimization problems with inclusion constraints are established. We use approximations as generalized derivatives and avoid even continuity assumptions. Convexity conditions are not imposed explicitly. Not all approximations in use are required to be bounded. The results improve or include several recent existing ones. Examples are provided to show that our theorems are easily applied in situations where several known results do not work.     

Convexity of chance constraints with independent random variables

We investigate the convexity of chance constraints with independent random variables. It will be shown, how concavity properties of the mapping related to the decision vector have to be combined with a suitable property of decrease for the marginal densities in order to arrive at convexity of the feasible set for large enough probability levels. It turns out that the required decrease can be verified for most prominent density functions. The results are applied then, to derive convexity of linear chance constraints with normally distributed stochastic coefficients when assuming independence of the rows of the coefficient matrix.     

Two-scale sparse finite element approximations

To reduce computational cost,we study some two-scale finite element approximations on sparse grids for elliptic partial differential equations of second order in a general setting.Over any tensor product domain ?R~d with d = 2,3,we construct the two-scale finite element approximations for both boundary value and eigenvalue problems by using a Boolean sum of some existing finite element approximations on a coarse grid and some univariate fine grids and hence they are cheaper approximations.As applications,we obtain some new efficient finite element discretizations for the two classes of problem:The new two-scale finite element approximation on a sparse grid not only has the less degrees of freedom but also achieves a good accuracy of approximation.