Quantitative stability of full random two-stage stochastic programs with recourse

In this paper, we consider quantitative stability analysis for two-stage stochastic linear programs when recourse costs, the technology matrix, the recourse matrix and the right-hand side vector are all random. For this purpose, we first investigate continuity properties of parametric linear programs. After deriving an explicit expression for the upper bound of its feasible solutions, we establish locally Lipschitz continuity of the feasible solution sets of parametric linear programs. These results are then applied to prove continuity of the generalized objective function derived from the full random second-stage recourse problem, from which we derive new forms of quantitative stability results of the optimal value function and the optimal solution set with respect to the Fortet–Mourier probability metric. The obtained results are finally applied to establish asymptotic behavior of an empirical approximation algorithm for full random two-stage stochastic programs.     

On distributionally robust optimization problems with k-th order stochastic dominance constraints induced by full random quadratic recourse

In this paper, we consider the optimization problems with k-th order stochastic dominance constraint on the objective function of the two-stage stochastic programs with full random quadratic recourse. By establishing the Lipschitz continuity of the feasible set mapping under some pseudo-metric, we show the Lipschitz continuity of the optimal value function and the upper semicontinuity of the optimal solution mapping of the problem. Furthermore, by the Hölder continuity of parameterized ambiguity set under the pseudo-metric, we demonstrate the quantitative stability results of the feasible set mapping, the optimal value function and the optimal solution mapping of the corresponding distributionally robust problem.     

Quantitative stability of mixed-integer two-stage quadratic stochastic programs

For our introduced mixed-integer quadratic stochastic program with fixed recourse matrices, random recourse costs, technology matrix and right-hand sides, we study quantitative stability properties of its optimal value function and optimal solution set when the underlying probability distribution is perturbed with respect to an appropriate probability metric. To this end, we first establish various Lipschitz continuity results about the value function and optimal solutions of mixed-integer parametric quadratic programs with parameters in the linear part of the objective function and in the right-hand sides of linear constraints. The obtained results extend earlier results about quantitative stability properties of stochastic integer programming and stability results for mixed-integer parametric quadratic programs.     

Quantitative stability of full random two-stage problems with quadratic recourse

ABSTRACT

In this paper, we discuss quantitative stability of two-stage stochastic programs with quadratic recourse where all parameters in the second-stage problem are random. By establishing the Lipschitz continuity of the feasible set mapping of the restricted Wolfe dual of the second-stage quadratic programming in terms of the Hausdorff distance, we prove the local Lipschitz continuity of the integrand of the objective function of the two-stage stochastic programming problem and then establish quantitative stability results of the optimal values and the optimal solution sets when the underlying probability distribution varies under the Fortet–Mourier metric. Finally, the obtained results are applied to study the asymptotic behaviour of the empirical approximation of the model.     

Continuity of parametric mixed-integer quadratic programs and its application to stability analysis of two-stage quadratic stochastic programs with mixed-integer recourse

For mixed-integer quadratic program where all coefficients in the objective function and the right-hand sides of constraints vary simultaneously, we show locally Lipschitz continuity of its optimal value function, and derive the corresponding global estimation; furthermore, we also obtain quantitative estimation about the change of its optimal solutions. Applying these results to two-stage quadratic stochastic program with mixed-integer recourse, we establish quantitative stability of the optimal value function and the optimal solution set with respect to the Fortet-Mourier probability metric, when the underlying probability distribution is perturbed. The obtained results generalize available results on continuity properties of mixed-integer quadratic programs and extend current results on quantitative stability of two-stage quadratic stochastic programs with mixed-integer recourse.     

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.     

Continuity and stability of fully random two-stage stochastic programs with mixed-integer recourse

In order to derive continuity and stability of two-stage stochastic programs with mixed-integer recourse when all coefficients in the second-stage problem are random, we first investigate the quantitative continuity of the objective function of the corresponding continuous recourse problem with random recourse matrices. Then by extending derived results to the mixed-integer recourse case, the perturbation estimate and the piece-wise lower semi-continuity of the objective function are proved. Under the framework of weak convergence for probability measure, the epi-continuity and joint continuity of the objective function are established. All these results help us to prove a qualitative stability result. The obtained results extend current results to the mixed-integer recourse with random recourse matrices which have finitely many atoms.     

Continuity and Stability of a Quadratic Mixed-Integer Stochastic Program

For the two-stage quadratic stochastic program where the second-stage problem is a general mixed-integer quadratic program with a random linear term in the objective function and random right-hand sides in constraints, we study continuity properties of the second-stage optimal value as a function of both the first-stage policy and the random parameter vector. We also present sufficient conditions for lower or upper semicontinuity, continuity, and Lipschitz continuity of the second-stage problem's optimal value function and the upper semicontinuity of the optimal solution set mapping with respect to the first-stage variables and/or the random parameter vector. These results then enable us to establish conclusions on the stability of optimal value and optimal solutions when the underlying probability distribution is perturbed with respect to the weak convergence of probability measures.     

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.     

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.

     

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.     

On structure and stability in stochastic programs with random technology matrix and complete integer recourse

For two-stage stochastic programs with integrality constraints in the second stage, we study continuity properties of the expected recourse as a function both of the first-stage policy and the integrating probability measure.Sufficient conditions for lower semicontinuity, continuity and Lipschitz continuity with respect to the first-stage policy are presented. Furthermore, joint continuity in the policy and the probability measure is established. This leads to conclusions on the stability of optimal values and optimal solutions to the two-stage stochastic program when subjecting the underlying probability measure to perturbations.This research is supported by the Schwerpunktprogramm Anwendungsbezogene Optimierung und Steuerung of the Deutsche Forschungsgemeinschaft.The main part of the paper was written while the author was an assistant at the Department of Mathematics at Humboldt University Berlin.     

A probability metrics approach for reducing the bias of optimality gap estimators in two-stage stochastic linear programming

Monte Carlo sampling-based estimators of optimality gaps for stochastic programs are known to be biased. When bias is a prominent factor, estimates of optimality gaps tend to be large on average even for high-quality solutions. This diminishes our ability to recognize high-quality solutions. In this paper, we present a method for reducing the bias of the optimality gap estimators for two-stage stochastic linear programs with recourse via a probability metrics approach, motivated by stability results in stochastic programming. We apply this method to the Averaged Two-Replication Procedure (A2RP) by partitioning the observations in an effort to reduce bias, which can be done in polynomial time in sample size. We call the resulting procedure the Averaged Two-Replication Procedure with Bias Reduction (A2RP-B). We provide conditions under which A2RP-B produces strongly consistent point estimators and an asymptotically valid confidence interval. We illustrate the effectiveness of our approach analytically on a newsvendor problem and test the small-sample behavior of A2RP-B on a number of two-stage stochastic linear programs from the literature. Our computational results indicate that the procedure effectively reduces bias. We also observe variance reduction in certain circumstances.     

Quantitative stability of fully random mixed-integer two-stage stochastic programs

Mixed-integer two-stage stochastic programs with fixed recourse matrix, random recourse costs, technology matrix, and right-hand sides are considered. Quantitative continuity properties of its optimal value and solution set are derived when the underlying probability distribution is perturbed with respect to an appropriate probability metric.     

On the information-based complexity of stochastic programming

Existing complexity results in stochastic linear programming using the Turing model depend only on problem dimensionality. We apply techniques from the information-based complexity literature to show that the smoothness of the recourse function is just as important. We derive approximation error bounds for the recourse function of two-stage stochastic linear programs and show that their worst case is exponential and depends on the solution tolerance, the dimensionality of the uncertain parameters and the smoothness of the recourse function.     

Stability of multistage stochastic programming

In this paper, we study the stability of multistage stochastic programming with recourse in a way that is different from that used in studying stability of two-stage stochastic programs. Here, we transform the multistage programs into mathematical programs in the space ⁿ ×L _p with a simple objective function and multistage stochastic constraints. By investigating the continuity of the multistage multifunction defined by the multistage stochastic constraints and applying epi-convergence theory we obtain stability results for linear and linear-quadratic multistage stochastic programs.Project supported by the National Natural Science Foundation of China.     

Distribution sensitivity analysis for stochastic programs with complete recourse

In this paper we study the stability of solutions to stochastic programming problems with complete recourse and show the Lipschitz continuity of optimal solutions as well as the associated Lagrange multipliers with respect to the parameters of the distribution function.     

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.     

Distribution sensitivity for certain classes of chance-constrained models with application to power dispatch

Using results from parametric optimization, we derive for chance-constrained stochastic programs quantitative stability properties for locally optimal values and sets of local minimizers when the underlying probability distribution is subjected to perturbations in a metric space of probability measures. Emphasis is placed on verifiable sufficient conditions for the constraint-set mapping to fulfill a Lipschitz property which is essential for the stability results. Both convex and nonconvex problems are investigated. For a chance-constrained model of power dispatch, where the power demand enters as a random vector with incompletely known probability distribution, we discuss consequences of our general results for the stability of optimal generation costs and optimal generation policies.The authors thank P. Kleinmann (formerly with the Humboldt-Universität, Berlin, Germany) for his active cooperation in designing the power dispatch model and J. Mayer (MTA SZTAKI, Budapest, Hungary) for his insight into energy optimization. Further thanks are due to the referees for their constructive criticism.This research was developed in the course of a contract study between the International Institute for Applied Systems Analysis, Laxenburg, Austria and the Humboldt-Universität, Berlin, Germany.