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.     

Multi-stage stochastic optimization applied to energy planning

This paper presents a methodology for the solution of multistage stochastic optimization problems, based on the approximation of the expected-cost-to-go functions of stochastic dynamic programming by piecewise linear functions. No state discretization is necessary, and the combinatorial explosion with the number of states (the well known curse of dimensionality of dynamic programming) is avoided. The piecewise functions are obtained from the dual solutions of the optimization problem at each stage and correspond to Benders cuts in a stochastic, multistage decomposition framework. A case study of optimal stochastic scheduling for a 39-reservoir system is presented and discussed.     

Multi-constrained matroidal knapsack problems

We consider multi-constrained knapsack problems where the sets of elements to be selected are subject to combinatorial constraints of matroidal nature. For this important class of NP-hard combinatorial optimization problems we prove that Lagrangean relaxation techniques not only provide good bounds to the value of the optimum, but also yield approximate solutions, which are asymptotically optimal under mild probabilistic assumptions.Partially supported by research projects Analisi e progetto di algoritmi and Modelli ed algoritmi per l'ottimizzazione of the Italian Ministry of Education (MPI 40%), and by NATO Grant RG 85/0240. Orally presented at the 12th International Symposium on Mathematical Programming, Boston, August 1985.     

Nonlinear Diffusion with Absorption

We consider the nonlinear diffusion-absorption problem in L¹() u - div a(, Du) + j (, u) f on , u = 0 on where is an arbitrary open set in ^N. Conditions for the existence of a strong solution are presented and the existence of a natural generalized solution in the general case is established. We study the dependence of the generalized solution on the absorption term j and characterize generalized solutions which are essentially bounded.     

Explicitly solvable model of Mössbauer scattering

An explicitly solvable model of Mössbauer scattering of rays by a nucleus bound in a harmonic-oscillator potential is constructed. The probability of elastic scattering, which is proportional to the Debye—Waller factor, is calculated in the framework of the explicitly solvable scattering problem. It is assumed that the rms deviation x of the nucleus and the photon wave numberk satisfykxE /E , whereE andE are typical energy levels of the photon and the oscillator states.St Petersburg State University. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 95, No. 3, pp. 439–430, June, 1993.     

Projection methods for non-linear programming

Several algorithms are presented for solving the non-linear programming problem, based on variable-metric projections of the gradient of the objective function into a local approximation to the constraints. The algorithms differ in the nature of this approximation. Inequality constraints are dealt with by selecting at each step a subset of active constraints to treat as equalities, this subset being the smallest necessary to ensure that the new point remains feasible. Some numerical results are given for the Colville problems.Paper presented at the 7^th Mathematical Programming Symposium, The Hague, September 1970.     

The Choquet-Deny convolution equation μ=μ*σ for probability measures on Abelian semigroups

In this note, we characterize the regular probability measures satisfying the Choquet-Deny convolution equation =* on Abelian topological semigroups for a given probability measure .     

Averaging in parabolic systems subject to weakly dependent random actions. The L2-approach

The first initial-boundary problem for a parabolic equation with a small parameter under external action described by some random process satisfying an arbitrary condition of weak dependence is considered. Averaging of the coefficients over a time variable is carried out. The existence of a generalized solution for the initial stochastic problem as well as for the problem with an averaged equation which turns out to be deterministic is assumed. Exponential bounds of the type of the well-known Bernstein inequalities for a sum of independent random variables are established for the probability of the deviation of the solution of the initial equation from the solution of the averaged problem.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 43, No. 3, pp. 315–322, March, 1991.     

On spaces of Baire I functions over K-analytic spaces

Suppose that is a relatively countably compact subset of B₁(X), the space of Baire I functions over a K-analytic space X equipped with the pointwise convergence topology. It is proved that (1) the closure of is a strongly countably compact Frechét-Urysohn space; (2) if is ₁ -compact, is a bicompactum; (3) if X is a paracompact space, the closure of is a bicompactum.Translated from Matematicheskie Zametki, Vol. 52, No. 3, pp. 108–116, September, 1992.     

Stochastic Lagrangian Relaxation Applied to Power Scheduling in a Hydro-Thermal System under Uncertainty

A dynamic (multi-stage) stochastic programming model for the weekly cost-optimal generation of electric power in a hydro-thermal generation system under uncertain demand (or load) is developed. The model involves a large number of mixed-integer (stochastic) decision variables and constraints linking time periods and operating power units. A stochastic Lagrangian relaxation scheme is designed by assigning (stochastic) multipliers to all constraints coupling power units. It is assumed that the stochastic load process is given (or approximated) by a finite number of realizations (scenarios) in scenario tree form. Solving the dual by a bundle subgradient method leads to a successive decomposition into stochastic single (thermal or hydro) unit subproblems. The stochastic thermal and hydro subproblems are solved by a stochastic dynamic programming technique and by a specific descent algorithm, respectively. A Lagrangian heuristics that provides approximate solutions for the first stage (primal) decisions starting from the optimal (stochastic) multipliers is developed. Numerical results are presented for realistic data from a German power utility and for numbers of scenarios ranging from 5 to 100 and a time horizon of 168 hours. The sizes of the corresponding optimization problems go up to 200000 binary and 350000 continuous variables, and more than 500000 constraints.     

Stochastic dominance with nonadditive probabilities

Choquet expected utility which uses capacities (i.e. nonadditive probability measures) in place of-additive probability measures has been introduced to decision making under uncertainty to cope with observed effects of ambiguity aversion like the Ellsberg paradox. In this paper we present necessary and sufficient conditions for stochastic dominance between capacities (i.e. the expected utility with respect to one capacity exceeds that with respect to the other one for a given class of utility functions). One wide class of conditions refers to probability inequalities on certain families of sets. To yield another general class of conditions we present sufficient conditions for the existence of a probability measureP with f dC= f dP for all increasing functionsf whenC is a given capacity. Examples includen-th degree stochastic dominance on the reals and many cases of so-called set dominance. Finally, applications to decision making are given including anticipated utility with unknown distortion function.     

Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms

Properties of several dual characteristics of the multidimensional knapsack problem (such as the probability of existence of-optimal and optimal-feasible Lagrange function generalized saddle points, magnitude of relative duality gap, etc.) are investigated for different probabilistic models. Sufficient conditions of good asymptotic behavior of the dual characteristics are given. A fast statistically efficient approximate algorithm with linear running time complexity for problems with random coefficients is presented.This paper was written when the author was affiliated with Chelyabinsk State Technical University and the Moscow Physical and Technical Institute, Russia.     

Turnpike theorems in probabilistic models of economic dynamics

This note is connected with a series of investigations of probabilistic models of economics. Its aim is the study of the asymptotic properties of the optimal programs in such models. The results are the stochastic analogs of the Turnpike theorems stating that the optimal programs are near to a definite stationary program for most of the time.Translated from Matematicheskie Zametki, Vol. 19, No. 2, pp. 279–290, February, 1976.The author thanks E. B. Dynkin for useful discussion and help during the preparation of this note.     

Probabilistisch kompakte L-unscharfe Mengen

In the case of completely distributive lattices (L,) we establish a probabilistic version of Alexander's subbase lemma and of Tychonoff's theorem for L-fuzzy sets. As an application we obtain that probabilistic topologies induced by compact ordinary topologies are also compact; i.e. ordinary compactness is consistent with probabilistic compactness. Regarding the validity of these results a counterexample shows that the complete distributivity of (L,) cannot be replaced by a weaker distributivity condition.     

Geometry of optimality conditions and constraint qualifications: The convex case

The cones of directions of constancy are used to derive: new as well as known optimality conditions; weakest constraint qualifications; and regularization techniques, for the convex programming problem. In addition, the badly behaved set of constraints, i.e. the set of constraints which causes problems in the Kuhn—Tucker theory, is isolated and a computational procedure for checking whether a feasible point is regular or not is presented.This research was supported by the National Research Council of Canada and le Gouvernement du Quebec and is part of the author's Ph.D. Dissertation done at McGill University, Montreal, Que., under the guidance of Professor S. Zlobec.     

A simple recourse model for power dispatch under uncertain demand

Optimal power dispatch under uncertainty of power demand is tackled via a stochastic programming model with simple recourse. The decision variables correspond to generation policies of a system comprising thermal units, pumped storage plants and energy contracts. The paper is a case study to test the kernel estimation method in the context of stochastic programming. Kernel estimates are used to approximate the unknown probability distribution of power demand. General stability results from stochastic programming yield the asymptotic stability of optimal solutions. Kernel estimates lead to favourable numerical properties of the recourse model (no numerical integration, the optimization problem is smooth convex and of moderate dimension). Test runs based on real-life data are reported. We compute the value of the stochastic solution for different problem instances and compare the stochastic programming solution with deterministic solutions involving adjusted demand portions.This research is supported by the Schwerpunktprogramm Anwendungsbezogene Optimierung und Steuerung of the Deutsche Forschungsgemeinschaft.     

Compactness of probability measures and the uniform convergence of certain stochastic series

We give the conditions which ensure the compactness of the probability measures _n, n1, generated by Gaussian processes the realizations of which are continuous with unit probability in [0, 1]. We also give the conditions for the uniform convergence of stochastic series of the form _{k=1 2k}(t), where the _k(t) are independent Gaussian processes the realizations of which are continuous with unit probability in [0, 1].Translated from Matematicheskie Zametki, Vol. 12, No. 4, pp. 443–451, October, 1972.In conclusion the author wishes to express his deep gratitude to Yu. V. Kozachenko for formulating the problem and for his attention to the paper.     

Continuous Singularity of the Weak Limit of Convolution Powers of a Discrete Probability Measure on 2 × 2 Stochastic Matrices

Let be a probability measure on n 2 × 2 stochastic matrices, n an arbitrary positive integer, and = (w) lim _n ⁿ , such that the support of consists of 2 × 2 stochastic matrices of rank one, and as such, can be regarded as a probability measure on [0, 1]. We present simple sufficient conditions for to be continuous singular w.r.t. the Lebesgue measure on [0, 1]. We also determine , given .     

Symmetrization of functions in Sobolev spaces and the isoperimetric inequality

A positive measurable function f on R^d can be symmetrized to a function f^* depending only on the distance r, and with the same distribution function as f. If the distribution derivatives of f are Radon measures then we have the inequality f^*f, where f is the total mass of the gradient. This inequality is a generalisation of the classical isoperimetric inequality for sets. Furthermore, and this is important for applications, if f belongs to the Sobolev space H¹,P then f^* belongs to H¹,P and f^*_pf_p.     

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.