Approximation of Stochastic Programming Problems

In stochastic programming, statistics, or econometrics, the aim is in general the optimization of a criterion function that depends on a decision variable theta and reads as an expectation with respect to a probability $\mathbb{P}$. When this function cannot be computed in closed form, it is customary to approximate it through an empirical mean function based on a random sample. On the other hand, several other methods have been proposed, such as quasi-Monte Carlo integration and numerical integration rules. In this paper, we propose a general approach for approximating such a function, in the sense of epigraphical convergence, using a sequence of functions of simpler type which can be expressed as expectations with respect to probability measures ${\mathbb{P}}_n$ that, in some sense, approximate $\mathbb{P}$. The main difference with the existing results lies in the fact that our main theorem does not impose conditions directly on the approximating probabilities but only on some integrals with respect to them. In addition, the ${\mathbb{P}}_n$’s can be transition probabilities, i.e., are allowed to depend on a further parameter, $\xi$, whose value results from deterministic or stochastic operations, depending on the underlying model. This framework allows us to deal with a large variety of approximation procedures such as Monte Carlo, quasi-Monte Carlo, numerical integration, quantization, several variations on Monte Carlo sampling, and some density approximation algorithms. As by-products, we discuss convergence results for stochastic programming and statistical inference based on dependent data, for programming with estimated parameters, and for robust optimization; we also provide a general result about the consistency of the bootstrap for $M$-estimators.

We examine the concept of essential intersection of a random set in the framework of robust optimization programs and ergodic theory. Using a recent extension of Birkhoff’s Ergodic Theorem developed by the present authors, it is shown that essential intersection can be represented as the countable intersection of random sets involving an asymptotically mean stationary transformation. This is applied to the approximation of a robust optimization program by a sequence of simpler programs with only a finite number of constraints. We also discuss some formulations of robust optimization programs that have appeared in the literature and we make them more precise, especially from the probabilistic point of view. We show that the essential intersection appears naturally in the correct formulation.

We consider scenario approximation of problems given by the optimization of a function over a constraint that is too difficult to be handled but can be efficiently approximated by a finite collection of constraints corresponding to alternative scenarios. The covered programs include min-max games, and semi-infinite, robust and chance-constrained programming problems. We prove convergence of the solutions of the approximated programs to the given ones, using mainly epigraphical convergence, a kind of variational convergence that has demonstrated to be a valuable tool in optimization problems.

In some estimation problems, especially in applications dealing with information theory, signal processing and biology, theory provides us with additional information allowing us to restrict the parameter space to a finite number of points. In this case, we speak of discrete parameter models. Even though the problem is quite old and has interesting connections with testing and model selection, asymptotic theory for these models has hardly ever been studied. Therefore, we discuss consistency, asymptotic distribution theory, information inequalities and their relations with efficiency and superefficiency for a general class of $m$-estimators.

We first establish a general version of the Birkhoff Ergodic Theorem for quasi-integrable extended real-valued random variables without assuming ergodicity. The key argument involves the Poincaré Recurrence Theorem. Our extension of the Birkhoff Ergodic Theorem is also shown to hold for asymptotic mean stationary sequences. This is formulated in terms of necessary and sufficient conditions. In particular, we examine the case where the probability space is endowed with a metric and we discuss the validity of the Birkhoff Ergodic Theorem for continuous random variables. The interest of our results is illustrated by an application to the convergence of statistical transforms, such as the moment generating function or the characteristic function, to their theoretical counterparts.

In this paper, we prove a new version of the Birkhoff ergodic theorem (BET) for random variables depending on a parameter (alias integrands). This involves variational convergences, namely epigraphical, hypographical and uniform convergence and requires a suitable definition of the conditional expectation of integrands. We also have to establish the measurability of the epigraphical lower and upper limits with respect to the $\sigma$-field of invariant subsets. From the main result, applications to uniform versions of the BET to sequences of random sets and to the strong consistency of estimators are briefly derived.

International conference

International conference

Seminar

Seminar

International conference

International conference

National conference

National conference

National conference

Seminar

International conference

International conference

International conference

International conference

International conference

Seminar

Seminar

Seminar

International conference

International conference

National conference

National conference

Seminar

International conference

Seminar

Seminar