Scenario reduction in stochastic programming

 Given a convex stochastic programming problem with a discrete initial probability distribution, the problem of optimal scenario reduction is stated as follows: Determine a scenario subset of prescribed cardinality and a probability measure based on this set that is the closest to the initial distribution in terms of a natural (or canonical) probability metric. Arguments from stability analysis indicate that Fortet-Mourier type probability metrics may serve as such canonical metrics. Efficient algorithms are developed that determine optimal reduced measures approximately. Numerical experience is reported for reductions of electrical load scenario trees for power management under uncertainty. For instance, it turns out that after 50% reduction of the scenario tree the optimal reduced tree still has about 90% relative accuracy. Received: July 2000 / Accepted: May 2002 Published online: February 14, 2003 Key words. stochastic programming – quantitative stability – Fortet-Mourier metrics – scenario reduction – transportation problem – electrical load scenario tree Mathematics Subject Classification (1991): 90C15, 90C31     

Scenario tree reduction for multistage stochastic programs

A framework for the reduction of scenario trees as inputs of (linear) multistage stochastic programs is provided such that optimal values and approximate solution sets remain close to each other. The argument is based on upper bounds of the L _r -distance and the filtration distance, and on quantitative stability results for multistage stochastic programs. The important difference from scenario reduction in two-stage models consists in incorporating the filtration distance. An algorithm is presented for selecting and removing nodes of a scenario tree such that a prescribed error tolerance is met. Some numerical experience is reported.     

Problem-based optimal scenario generation and reduction in stochastic programming

Scenarios are indispensable ingredients for the numerical solution of stochastic programs. Earlier approaches to optimal scenario generation and reduction are based on stability arguments involving distances of probability measures. In this paper we review those ideas and suggest to make use of stability estimates based only on problem specific data. For linear two-stage stochastic programs we show that the problem-based approach to optimal scenario generation can be reformulated as best approximation problem for the expected recourse function which in turn can be rewritten as a generalized semi-infinite program. We show that the latter is convex if either right-hand sides or costs are random and can be transformed into a semi-infinite program in a number of cases. We also consider problem-based optimal scenario reduction for two-stage models and optimal scenario generation for chance constrained programs. Finally, we discuss problem-based scenario generation for the classical newsvendor problem.

     

Scenario Reduction Algorithms in Stochastic Programming

We consider convex stochastic programs with an (approximate) initial probability distribution P having finite support supp P, i.e., finitely many scenarios. The behaviour of such stochastic programs is stable with respect to perturbations of P measured in terms of a Fortet-Mourier probability metric. The problem of optimal scenario reduction consists in determining a probability measure that is supported by a subset of supp P of prescribed cardinality and is closest to P in terms of such a probability metric. Two new versions of forward and backward type algorithms are presented for computing such optimally reduced probability measures approximately. Compared to earlier versions, the computational performance (accuracy, running time) of the new algorithms has been improved considerably. Numerical experience is reported for different instances of scenario trees with computable optimal lower bounds. The test examples also include a ternary scenario tree representing the weekly electrical load process in a power management model.     

Scenario tree modeling for multistage stochastic programs

An important issue for solving multistage stochastic programs consists in the approximate representation of the (multivariate) stochastic input process in the form of a scenario tree. In this paper, we develop (stability) theory-based heuristics for generating scenario trees out of an initial set of scenarios. They are based on forward or backward algorithms for tree generation consisting of recursive scenario reduction and bundling steps. Conditions are established implying closeness of optimal values of the original process and its tree approximation, respectively, by relying on a recent stability result in Heitsch, Römisch and Strugarek (SIAM J Optim 17:511–525, 2006) for multistage stochastic programs. Numerical experience is reported for constructing multivariate scenario trees in electricity portfolio management.     

Stochastic differential portfolio games for an insurer in a jump-diffusion risk process

We discuss an optimal portfolio selection problem of an insurer who faces model uncertainty in a jump-diffusion risk model using a game theoretic approach. In particular, the optimal portfolio selection problem is formulated as a two-person, zero-sum, stochastic differential game between the insurer and the market. There are two leader-follower games embedded in the game problem: (i) The insurer is the leader of the game and aims to select an optimal portfolio strategy by maximizing the expected utility of the terminal surplus in the “worst-case” scenario; (ii) The market acts as the leader of the game and aims to choose an optimal probability scenario to minimize the maximal expected utility of the terminal surplus. Using techniques of stochastic linear-quadratic control, we obtain closed-form solutions to the game problems in both the jump-diffusion risk process and its diffusion approximation for the case of an exponential utility.     

Testing the structure of multistage stochastic programs

A fixed topology of stages and/or a fixed branching scheme are common assumptions for applications and numerical solution of scenario based multistage stochastic programs. Using contamination technique to test this structure, we extend the results of Dupačová (Contamination for multistage stochastic programs. In: Hušková M, Janžura M (eds) Prague stochastics. Matfyzpress, Praha, pp 91–101, 2006a) to stochastic programs with multistage polyhedral risk objectives. The ideas are exemplified by bond portfolio management problems and complemented by illustrative numerical results.     

Recourse-based stochastic nonlinear programming: properties and Benders-SQP algorithms

In this paper, we study recourse-based stochastic nonlinear programs and make two sets of contributions. The first set assumes general probability spaces and provides a deeper understanding of feasibility and recourse in stochastic nonlinear programs. A sufficient condition, for equality between the sets of feasible first-stage decisions arising from two different interpretations of almost sure feasibility, is provided. This condition is an extension to nonlinear settings of the “W-condition,” first suggested by Walkup and Wets (SIAM J. Appl. Math. 15:1299–1314, 1967). Notions of complete and relatively-complete recourse for nonlinear stochastic programs are defined and simple sufficient conditions for these to hold are given. Implications of these results on the L-shaped method are discussed. Our second set of contributions lies in the construction of a scalable, superlinearly convergent method for solving this class of problems, under the setting of a finite sample-space. We present a novel hybrid algorithm that combines sequential quadratic programming (SQP) and Benders decomposition. In this framework, the resulting quadratic programming approximations while arbitrarily large, are observed to be two-period stochastic quadratic programs (QPs) and are solved through two variants of Benders decomposition. The first is based on an inexact-cut L-shaped method for stochastic quadratic programming while the second is a quadratic extension to a trust-region method suggested by Linderoth and Wright (Comput. Optim. Appl. 24:207–250, 2003). Obtaining Lagrange multiplier estimates in this framework poses a unique challenge and are shown to be cheaply obtainable through the solution of a single low-dimensional QP. Globalization of the method is achieved through a parallelizable linesearch procedure. Finally, the efficiency and scalability of the algorithm are demonstrated on a set of stochastic nonlinear programming test problems.     

The Existence and Uniqueness of the Solution for Neutral Stochastic Functional Differential Equations with Infinite Delay in Abstract Space

The main aim of this paper is to prove the existence and uniqueness of the solution for neutral stochastic functional differential equations with infinite delay, which the initial data belong to the phase space ℬ((−∞,0];ℝ ^d ). The vital work of this paper is to extend the initial function space of the paper (Wei and Wang, J. Math. Anal. Appl. 331:516–531, 2007) and give some examples to show that the phase space ℬ((−∞,0];ℝ ^d ) exists. In addition, this paper builds a Banach space ℳ²((−∞,T],ℝ ^d ) with a new norm in order to discuss the existence and uniqueness of the solution for such equations with infinite delay.     

Distribution sensitivity in stochastic programming

In this paper, stochastic programming problems are viewed as parametric programs with respect to the probability distributions of the random coefficients. General results on quantitative stability in parametric optimization are used to study distribution sensitivity of stochastic programs. For recourse and chance constrained models quantitative continuity results for optimal values and optimal solution sets are proved (with respect to suitable metrics on the space of probability distributions). The results are useful to study the effect of approximations and of incomplete information in stochastic programming.This research was presented in parts at the 4th International Conference on Stochastic Programming held in Prague in September 1986.     

Stability analysis for stochastic programs

For stochastic programs with recourse and with (several joint) probabilistic constraints, respectively, we derive quantitative continuity properties of the relevant expectation functionals and constraint set mappings. This leads to qualitative and quantitative stability results for optimal values and optimal solutions with respect to perturbations of the underlying probability distributions. Earlier stability results for stochastic programs with recourse and for those with probabilistic constraints are refined and extended, respectively. Emphasis is placed on equipping sets of probability measures with metrics that one can handle in specific situations. To illustrate the general stability results we present possible consequences when estimating the original probability measure via empirical ones.     

Approximating the Pathway Axis and the Persistence Diagrams for a Collection of Balls in 3-Space

Given a collection ℬ of balls in a three-dimensional space, we wish to explore the cavities, voids, and tunnels in the complement space of ∪ℬ. We introduce the pathway axis of ℬ as a useful subset of the medial axis of the complement of ∪ℬ and prove that it satisfies several desirable geometric properties. We present an algorithm that constructs the pathway graph of ∪ℬ, a piecewise-linear approximation of the pathway axis. At the heart of our approach is an approximation scheme that constructs a collection K{\mathcal{K}} of same-size balls that approximate ℬ so that the Hausdorff distance between ∪ℬ and èK\bigcup{\mathcal{K}} is bounded by a prescribed parameter. We prove a bound on the ratio between the number of balls in K{\mathcal{K}} and the number of balls in ℬ. We employ this bound and the approximation scheme to show how to approximate the persistence diagrams for ∪ℬ, which can be used to extract major topological features such as the large voids and tunnels in the complement of ∪ℬ. We show that our approach is superior in terms of complexity to the standard point-sample approaches for the two problems that we address in this paper: approximating the pathway axis of ℬ and approximating the persistence diagrams for ∪ℬ. In a companion paper we introduce MolAxis, a tool for the identification of channels in macromolecules that demonstrates how the pathway graph and the persistence diagrams are used to identify plausible pathways in the complement of molecules.     

Stochastic programming with integer variables

 Including integer variables into traditional stochastic linear programs has considerable implications for structural analysis and algorithm design. Starting from mean-risk approaches with different risk measures we identify corresponding two- and multi-stage stochastic integer programs that are large-scale block-structured mixed-integer linear programs if the underlying probability distributions are discrete. We highlight the role of mixed-integer value functions for structure and stability of stochastic integer programs. When applied to the block structures in stochastic integer programming, well known algorithmic principles such as branch-and-bound, Lagrangian relaxation, or cutting plane methods open up new directions of research. We review existing results in the field and indicate departure points for their extension. Received: December 2, 2002 / Accepted: April 23, 2003 Published online: May 28, 2003 Mathematics Subject Classification (2000): 90C15, 90C11, 90C06, 90C57     

Embeddings of Bornological Universes

A bornological universe 〈X, τ, ℬ〉 is a topological space 〈X, τ〉 equipped with a bornology ℬ, that is, a cover of X that is hereditary and is closed under finite unions. In this paper, we give three different sets of necessary and sufficient conditions for the universe to be both topologically and bornologically embeddable in ℝ ^Y for some index set Y. When this is possible, Y can be chosen to be a family of continuous coercive functions on X. Dedicated to Arrigo Cellina.     

The asymptotic distribution of leaf heights in binary trees

Let ℬ _n be the family of extended binary tress withn internal nodes and assume that eacht ∈ℬ _n has equal probability. We identify the asymptotic distribution of the height of leafi (where the leaves are enumerated from left to right) asi andn tend to infinity, such thati/n tends tox λ]0, 1[, as a Maxwell distribution. A generalization of the used combinatorial resp. probabilistic considerations is indicated.     

Multiplicative maps on ℬ(X)

A structural feature of multiplicative maps on ℬ(X) which sends some rank-1 operator to an operator of rank not greater than 1 is given, and based on it, some characterizations of automorphism of ℬ(X) are obtained and some multiplicative preserver problems are answered. Project supported by the National Natural Science Foundation of China (Grant No.19671055) and Provincial Natural Science Foundation of Shanxi.     

A scenario decomposition algorithm for 0–1 stochastic programs

We propose a scenario decomposition algorithm for stochastic 0–1 programs. The algorithm recovers an optimal solution by iteratively exploring and cutting-off candidate solutions obtained from solving scenario subproblems. The scheme is applicable to quite general problem structures and can be implemented in a distributed framework. Illustrative computational results on standard two-stage stochastic integer programming and nonlinear stochastic integer programming test problems are presented.     

Postoptimality for mean-risk stochastic mixed-integer programs and its application

The mean-risk stochastic mixed-integer programs can better model complex decision problems under uncertainty than usual stochastic (integer) programming models. In order to derive theoretical results in a numerically tractable way, the contamination technique is adopted in this paper for the postoptimality analysis of the mean-risk models with respect to changes in the scenario set, here the risk is measured by the lower partial moment. We first study the continuity of the objective function and the differentiability, with respect to the parameter contained in the contaminated distribution, of the optimal value function of the mean-risk model when the recourse cost vector, the technology matrix and the right-hand side vector in the second stage problem are all random. The postoptimality conclusions of the model are then established. The obtained results are applied to two-stage stochastic mixed-integer programs with risk objectives where the objective function is nonlinear with respect to the probability distribution. The current postoptimality results for stochastic programs are improved.     

Assessing solution quality in stochastic programs

Determining whether a solution is of high quality (optimal or near optimal) is fundamental in optimization theory and algorithms. In this paper, we develop Monte Carlo sampling-based procedures for assessing solution quality in stochastic programs. Quality is defined via the optimality gap and our procedures' output is a confidence interval on this gap. We review a multiple-replications procedure that requires solution of, say, 30 optimization problems and then, we present a result that justifies a computationally simplified single-replication procedure that only requires solving one optimization problem. Even though the single replication procedure is computationally significantly less demanding, the resulting confidence interval might have low coverage probability for small sample sizes for some problems. We provide variants of this procedure that require two replications instead of one and that perform better empirically. We present computational results for a newsvendor problem and for two-stage stochastic linear programs from the literature. We also discuss when the procedures perform well and when they fail, and we propose using ɛ-optimal solutions to strengthen the performance of our procedures.     

Improving constants of strong convexity in linear stochastic programming

We derive formulas for constants of strong convexity (CSCs) of expectation functions encountered in two-stage stochastic programs with linear recourse. One of them yields a CSC as the optimal value of a certain quadratically constrained quadratic program, another one in terms of the thickness of the feasibility polytope of the dual problem associated to the recourse problem. CSCs appear in Hoelder-type estimates relating the distance of optimal solution sets of stochastic programs to a suitable distance of underlying probability distributions.