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.     

Inverse stochastic dominance constraints and rank dependent expected utility theory

We consider optimization problems with second order stochastic dominance constraints formulated as a relation of Lorenz curves. We characterize the relation in terms of rank dependent utility functions, which generalize Yaari's utility functions. We develop optimality conditions and duality theory for problems with Lorenz dominance constraints. We prove that Lagrange multipliers associated with these constraints can be identified with rank dependent utility functions. The problem is numerically tractable in the case of discrete distributions with equally probable realizations. Research supported by the NSF awards DMS-0303545, DMS-0303728, DMI-0354500 and DMI-0354678.     

On portfolio optimization using fuzzy decisions

We consider stochastic optimization problems involving stochastic dominance constraints. We develop portfolio optimization model involving stochastic dominance constrains using fuzzy decisions and we concentrate on fuzzy linear programming problems with only fuzzy technological coefficients and aplication/implementation of modified subgradient method to fuzy linear programming problems. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Robustness of optimal portfolios under risk and stochastic dominance constraints

Solutions of portfolio optimization problems are often influenced by a model misspecification or by errors due to approximation, estimation and incomplete information. The obtained results, recommendations for the risk and portfolio manager, should be then carefully analyzed. We shall deal with output analysis and stress testing with respect to uncertainty or perturbations of input data for static risk constrained portfolio optimization problems by means of the contamination technique. Dependence of the set of feasible solutions on the probability distribution rules out the straightforward construction of convexity-based global contamination bounds. Results obtained in our paper [Dupa?ová, J., & Kopa, M. (2012). Robustness in stochastic programs with risk constraints. Annals of Operations Research, 200, 55–74.] were derived for the risk and second order stochastic dominance constraints under suitable smoothness and/or convexity assumptions that are fulfilled, e.g. for the Markowitz mean–variance model. In this paper we relax these assumptions having in mind the first order stochastic dominance and probabilistic risk constraints. Local bounds for problems of a special structure are obtained. Under suitable conditions on the structure of the problem and for discrete distributions we shall exploit the contamination technique to derive a new robust first order stochastic dominance portfolio efficiency test.     

Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra

 We consider stochastic programming problems with probabilistic constraints involving random variables with discrete distributions. They can be reformulated as large scale mixed integer programming problems with knapsack constraints. Using specific properties of stochastic programming problems and bounds on the probability of the union of events we develop new valid inequalities for these mixed integer programming problems. We also develop methods for lifting these inequalities. These procedures are used in a general iterative algorithm for solving probabilistically constrained problems. The results are illustrated with a numerical example. Received: October 8, 2000 / Accepted: August 13, 2002 Published online: September 27, 2002 Key words. stochastic programming – integer programming – valid inequalities     

Inference of statistical bounds for multistage stochastic programming problems

We discuss in this paper statistical inference of sample average approximations of multistage stochastic programming problems. We show that any random sampling scheme provides a valid statistical lower bound for the optimal (minimum) value of the true problem. However, in order for such lower bound to be consistent one needs to employ the conditional sampling procedure. We also indicate that fixing a feasible first-stage solution and then solving the sampling approximation of the corresponding (T–1)-stage problem, does not give a valid statistical upper bound for the optimal value of the true problem.Supported, in part, by the National Science Foundation under grant DMS-0073770.     

Optimization with multivariate stochastic dominance constraints

We consider stochastic optimization problems where risk-aversion is expressed by a stochastic ordering constraint. The constraint requires that a random vector depending on our decisions stochastically dominates a given benchmark random vector. We identify a suitable multivariate stochastic order and describe its generator in terms of von Neumann–Morgenstern utility functions. We develop necessary and sufficient conditions of optimality and duality relations for optimization problems with this constraint. Assuming convexity we show that the Lagrange multipliers corresponding to dominance constraints are elements of the generator of this order, thus refining and generalizing earlier results for optimization under univariate stochastic dominance constraints. Furthermore, we obtain necessary conditions of optimality for non-convex problems under additional smoothness assumptions.     

A note on second-order stochastic dominance constraints induced by mixed-integer linear recourse

We introduce stochastic integer programs with second-order dominance constraints induced by mixed-integer linear recourse. Closedness of the constraint set mapping with respect to perturbations of the underlying probability measure is derived. For discrete probability measures, large-scale, block-structured, mixed- integer linear programming equivalents to the dominance constrained stochastic programs are identified. For these models, a decomposition algorithm is proposed and tested with instances from power optimization.     

Multivariate robust second-order stochastic dominance and resulting risk-averse optimization

ABSTRACT

By utilizing a min-biaffine scalarization function, we define the multivariate robust second-order stochastic dominance relationship to flexibly compare two random vectors. We discuss the basic properties of the multivariate robust second-order stochastic dominance and relate it to the nonpositiveness of a functional which is continuous and subdifferentiable everywhere. We study a stochastic optimization problem with multivariate robust second-order stochastic dominance constraints and develop the necessary and sufficient conditions of optimality in the convex case. After specifying an ambiguity set based on moments information, we approximate the ambiguity set by a series of sets consisting of discrete distributions. Furthermore, we design a convex approximation to the proposed stochastic optimization problem with multivariate robust second-order stochastic dominance constraints and establish its qualitative stability under Kantorovich metric and pseudo metric, respectively. All these results lay a theoretical foundation for the modelling and solution of complex stochastic decision-making problems with multivariate robust second-order stochastic dominance constraints.     

Optimality and duality theory for stochastic optimization problems with nonlinear dominance constraints

We consider a new class of optimization problems involving stochastic dominance constraints of second order. We develop a new splitting approach to these models, optimality conditions and duality theory. These results are used to construct special decomposition methods.This research was supported by the NSF awards DMS-0303545 and DMS-0303728.Key words.Stochastic programming – stochastic ordering – semi-infinite optimized – decomposition     

Two-stage stochastic optimization problems with stochastic ordering constraints on the recourse

We consider two-stage risk-averse stochastic optimization problems with a stochastic ordering constraint on the recourse function. Two new characterizations of the increasing convex order relation are provided. They are based on conditional expectations and on integrated quantile functions: a counterpart of the Lorenz function. We propose two decomposition methods to solve the problems and prove their convergence. Our methods exploit the decomposition structure of the risk-neutral two-stage problems and construct successive approximations of the stochastic ordering constraints. Numerical results confirm the efficiency of the methods.     

Numerical methods for stochastic programs with second order dominance constraints with applications to portfolio optimization

Inspired by the successful applications of the stochastic optimization with second order stochastic dominance (SSD) model in portfolio optimization, we study new numerical methods for a general SSD model where the underlying functions are not necessarily linear. Specifically, we penalize the SSD constraints to the objective under Slater’s constraint qualification and then apply the well known stochastic approximation (SA) method and the level function method to solve the penalized problem. Both methods are iterative: the former requires to calculate an approximate subgradient of the objective function of the penalized problem at each iterate while the latter requires to calculate a subgradient. Under some moderate conditions, we show that w.p.1 the sequence of approximated solutions generated by the SA method converges to an optimal solution of the true problem. As for the level function method, the convergence is deterministic and in some cases we are able to estimate the number of iterations for a given precision. Both methods are applied to portfolio optimization problem where the return functions are not necessarily linear and some numerical test results are reported.     

General linear formulations of stochastic dominance criteria

We develop and implement linear formulations of general Nth order stochastic dominance criteria for discrete probability distributions. Our approach is based on a piece-wise polynomial representation of utility and its derivatives and can be implemented by solving a relatively small system of linear inequalities. This approach allows for comparing a given prospect with a discrete set of alternative prospects as well as for comparison with a polyhedral set of linear combinations of prospects. We also derive a linear dual formulation in terms of lower partial moments and co-lower partial moments. An empirical application to historical stock market data suggests that the passive stock market portfolio is highly inefficient relative to actively managed portfolios for all investment horizons and for nearly all investors. The results also illustrate that the mean–variance rule and second-order stochastic dominance rule may not detect market portfolio inefficiency because of non-trivial violations of non-satiation and prudence.     

Stochastic Programming with Multivariate Second Order Stochastic Dominance Constraints with Applications in Portfolio Optimization

In this paper we study optimization problems with multivariate stochastic dominance constraints where the underlying functions are not necessarily linear. These problems are important in multicriterion decision making, since each component of vectors can be interpreted as the uncertain outcome of a given criterion. We propose a penalization scheme for the multivariate second order stochastic dominance constraints. We solve the penalized problem by the level function methods, and a modified cutting plane method and compare them to the cutting surface method proposed in the literature. The proposed numerical schemes are applied to a generic budget allocation problem and a real world portfolio optimization problem.     

An algorithm for stochastic programs with first-order dominance constraints induced by linear recourse

We derive a cutting plane decomposition method for stochastic programs with first-order dominance constraints induced by linear recourse models with continuous variables in the second stage.     

An exact method for constrained maximization of the conditional value-at-risk of a class of stochastic submodular functions

We consider a class of risk-averse submodular maximization problems (RASM) where the objective is the conditional value-at-risk (CVaR) of a random nondecreasing submodular function at a given risk level. We propose valid inequalities and an exact general method for solving RASM under the assumption that we have an efficient oracle that computes the CVaR of the random function. We demonstrate the proposed method on a stochastic set covering problem that admits an efficient CVaR oracle for the random coverage function.     

Numerical solution of quasi-variational inequalities arising in stochastic game theory

We study the finite-difference approximation for the quasi-variational inequalities for a stochastic game involving discrete actions of the players and continuous and discrete payoff. We prove convergence of iterative schemes for the solution of the discretized quasi-variational inequalities, with estimates of the rate of convergence (via contraction mappings) in two particular cases. Further, we prove stability of the finite-difference schemes, and convergence of the solution of the discrete problems to the solution of the continuous problem as the discretization mesh goes to zero. We provide a direct interpretation of the discrete problems in terms of finite-state, continuous-time Markov processes.     

Chance-constrained programming with fuzzy stochastic coefficients

We consider fuzzy stochastic programming problems with a crisp objective function and linear constraints whose coefficients are fuzzy random variables, in particular of type L-R. To solve this type of problems, we formulate deterministic counterparts of chance-constrained programming with fuzzy stochastic coefficients, by combining constraints on probability of satisfying constraints, as well as their possibility and necessity. We discuss the possible indices for comparing fuzzy quantities by putting together interval orders and statistical preference. We study the convexity of the set of feasible solutions under various assumptions. We also consider the case where fuzzy intervals are viewed as consonant random intervals. The particular cases of type L-R fuzzy Gaussian and discrete random variables are detailed.     

A generalized stochastic goal programming model

In this paper we show how one can get stochastic solutions of Stochastic Multi-objective Problem (SMOP) using goal programming models. In literature it is well known that one can reduce a SMOP to deterministic equivalent problems and reduce the analysis of a stochastic problem to a collection of deterministic problems. The first sections of this paper will be devoted to the introduction of deterministic equivalent problems when the feasible set is a random set and we show how to solve them using goal programming technique. In the second part we try to go more in depth on notion of SMOP solution and we suppose that it has to be a random variable. We will present stochastic goal programming model for finding stochastic solutions of SMOP. Our approach requires more computational time than the one based on deterministic equivalent problems due to the fact that several optimization programs (which depend on the number of experiments to be run) needed to be solved. On the other hand, since in our approach we suppose that a SMOP solution is a random variable, according to the Central Limit Theorem the larger will be the sample size and the more precise will be the estimation of the statistical moments of a SMOP solution. The developed model will be illustrated through numerical examples.     

A gaussian upper bound for gaussian multi-stage stochastic linear programs

This paper deals with two-stage and multi-stage stochastic programs in which the right-hand sides of the constraints are Gaussian random variables. Such problems are of interest since the use of Gaussian estimators of random variables is widespread. We introduce algorithms to find upper bounds on the optimal value of two-stage and multi-stage stochastic (minimization) programs with Gaussian right-hand sides. The upper bounds are obtained by solving deterministic mathematical programming problems with dimensions that do not depend on the sample space size. The algorithm for the two-stage problem involves the solution of a deterministic linear program and a simple semidefinite program. The algorithm for the multi-stage problem invovles the solution of a quadratically constrained convex programming problem.