A semi-infinite programming approach to two-stage stochastic linear programs with high-order moment constraints

We consider distributionally robust two-stage stochastic linear optimization problems with higher-order (say \(p\ge 3\) and even possibly irrational) moment constraints in their ambiguity sets. We suggest to solve the dual form of the problem by a semi-infinite programming approach, which deals with a much simpler reformulation than the conic optimization approach. Some preliminary numerical results are reported.     

A new distributionally robust p-hub median problem with uncertain carbon emissions and its tractable approximation method

The p-hub median problem is to determine the optimal location for p hubs and assign the remaining nodes to hubs so as to minimize the total transportation costs. Under the carbon cap-and-trade policy, we study this problem by addressing the uncertain carbon emissions from the transportation, where the probability distributions of the uncertain carbon emissions are only partially available. A novel distributionally robust optimization model with the ambiguous chance constraint is developed for the uncapacitated single allocation p-hub median problem. The proposed distributionally robust optimization problem is a semi-infinite chance-constrained optimization model, which is computationally intractable for general ambiguity sets. To solve this hard optimization model, we discuss the safe approximation to the ambiguous chance constraint in the following two types of ambiguity sets. The first ambiguity set includes the probability distributions with the bounded perturbations with zero means. In this case, we can turn the ambiguous chance constraint into its computable form based on tractable approximation method. The second ambiguity set is the family of Gaussian perturbations with partial knowledge of expectations and variances. Under this situation, we obtain the deterministic equivalent form of the ambiguous chance constraint. Finally, we validate the proposed optimization model via a case study from Southeast Asia and CAB data set. The numerical experiments indicate that the optimal solutions depend heavily on the distribution information of carbon emissions. In addition, the comparison with the classical robust optimization method shows that the proposed distributionally robust optimization method can avoid over-conservative solutions by incorporating partial probability distribution information. Compared with the stochastic optimization method, the proposed method pays a small price to depict the uncertainty of probability distribution. Compared with the deterministic model, the proposed method generates the new robust optimal solution under uncertain carbon emissions.     

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.     

Discrete Approximation Scheme in Distributionally Robust Optimization

Discrete approximation, which has been the prevailing scheme in stochastic programming in the past decade, has been extended to distributionally robust optimization (DRO) recently. In this paper, we conduct rigorous quantitative stability analysis of discrete approximation schemes for DRO, which measures the approximation error in terms of discretization sample size. For the ambiguity set defined through equality and inequality moment conditions, we quantify the discrepancy between the discretized ambiguity sets and the original set with respect to the Wasserstein metric. To establish the quantitative convergence, we develop a Hoffman error bound theory with Hoffman constant calculation criteria in a infinite dimensional space, which can be regarded as a byproduct of independent interest. For the ambiguity set defined by Wasserstein ball and moment conditions combined with Wasserstein ball, we present similar quantitative stability analysis by taking full advantage of the convex property inherently admitted by Wasserstein metric. Efficient numerical methods for specifically solving discrete approximation DRO problems with thousands of samples are also designed. In particular, we reformulate different types of discrete approximation problems into a class of saddle point problems with completely separable structures. The stochastic primal-dual hybrid gradient (PDHG) algorithm where in each iteration we update a random subset of the sampled variables is then amenable as a solution method for the reformulated saddle point problems. Some preliminary numerical tests are reported.     

Distributionally robust chance constrained problem under interval distribution information

This paper is concerned with distributionally robust chance constrained problem under interval distribution information. Using worst-case CVaR approximation, we present a tractable convex programming approximation for distributionally robust individual chance constrained problem under interval sets of mean and covariance information. We prove the worst-case CVaR approximation problem is an exact form of the distributionally robust individual chance constrained problem. Then, our result is applied to worst-case Value-at-Risk optimization problem. Moreover, we discuss the problem under several ambiguous distribution information and investigate tractable approximations for distributionally robust joint chance constrained problem. Finally, we provide an illustrative example to show our results.     

Risk-Averse Stochastic Programming and Distributionally Robust Optimization Via Operator Splitting

This work deals with a broad class of convex optimization problems under uncertainty. The approach is to pose the original problem as one of finding a zero of the sum of two appropriate monotone operators, which is solved by the celebrated Douglas-Rachford splitting method. The resulting algorithm, suitable for risk-averse stochastic programs and distributionally robust optimization with fixed support, separates the random cost mapping from the risk function composing the problem’s objective. Such a separation is exploited to compute iterates by alternating projections onto different convex sets. Scenario subproblems, free from the risk function and thus parallelizable, are projections onto the cost mappings’ epigraphs. The risk function is handled in an independent and dedicated step consisting of evaluating its proximal mapping that, in many important cases, amounts to projecting onto a certain ambiguity set. Variables get updated by straightforward projections on subspaces through independent computations for the various scenarios. The investigated approach enjoys significant flexibility and opens the way to handle, in a single algorithm, several classes of risk measures and ambiguity sets.

     

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.     

Distributionally robust scheduling on parallel machines under moment uncertainty

This paper investigates a distributionally robust scheduling problem on identical parallel machines, where job processing times are stochastic without any exact distributional form. Based on a distributional set specified by the support and estimated moments information, we present a min-max distributionally robust model, which minimizes the worst-case expected total flow time out of all probability distributions in this set. Our model doesn’t require exact probability distributions which are the basis for many stochastic programming models, and utilizes more information compared to the interval-based robust optimization models. Although this problem originates from the manufacturing environment, it can be applied to many other fields when the machines and jobs are endowed with different meanings. By optimizing the inner maximization subproblem, the min-max formulation is reduced to an integer second-order cone program. We propose an exact algorithm to solve this problem via exploring all the solutions that satisfy the necessary optimality conditions. Computational experiments demonstrate the high efficiency of this algorithm since problem instances with 100 jobs are optimized in a few seconds. In addition, simulation results convincingly show that the proposed distributionally robust model can hedge against the bias of estimated moments and enhance the robustness of production systems.     

Distributionally robust Optimal Control and MDP modeling

In this paper we discuss Optimal Control and Markov Decision Process (MDP) formulations of multistage optimization problems when the involved probability distributions are not known exactly, but rather are assumed to belong to specified ambiguity families. The aim of this paper is to clarify a connection between such distributionally robust approaches to multistage stochastic optimization.     

Data-driven risk-averse stochastic optimization with Wasserstein metric

In this paper, we study a data-driven risk-averse stochastic optimization approach with Wasserstein Metric for the general distribution case. By using the Wasserstein Metric, we can successfully reformulate the risk-averse two-stage stochastic optimization problem with distributional ambiguity to a traditional two-stage robust optimization problem. In addition, we derive the worst-case distribution and perform convergence analysis to show that the risk aversion of the proposed formulation vanishes as the size of historical data grows to infinity.     

Robust portfolio selection based on a multi-stage scenario tree

The aim of this paper is to apply the concept of robust optimization introduced by Bel-Tal and Nemirovski to the portfolio selection problems based on multi-stage scenario trees. The objective of our portfolio selection is to maximize an expected utility function value (or equivalently, to minimize an expected disutility function value) as in a classical stochastic programming problem, except that we allow for ambiguities to exist in the probability distributions along the scenario tree. We show that such a problem can be formulated as a finite convex program in the conic form, on which general convex optimization techniques can be applied. In particular, if there is no short-selling, and the disutility function takes the form of semi-variance downside risk, and all the parameter ambiguity sets are ellipsoidal, then the problem becomes a second order cone program, thus tractable. We use SeDuMi to solve the resulting robust portfolio selection problem, and the simulation results show that the robust consideration helps to reduce the variability of the optimal values caused by the parameter ambiguity.     

一类分布鲁棒线性决策随机优化研究

随机优化广泛应用于经济、管理、工程和国防等领域,分布鲁棒优化作为解决分布信息模糊下的随机优化问题近年来成为学术界的研究热点.本文基于φ-散度不确定集和线性决策方式研究一类分布鲁棒随机优化的建模与计算,构建了易于计算实现的分布鲁棒随机优化的上界和下界问题.数值算例验证了模型分析的有效性.     

串联式多级火箭成本问题初论

本文以火箭最大速度值的一般变化规律为基础, 改进了以前考虑火箭发射的成本问题的常用数学模型：最省的最省推进剂方案, 详细研究了各种情况下串联式多级火箭的成本问题,并以算例验证了所得的新成本计算模型的有效性.     

Energy and reserve dispatch with distributionally robust joint chance constraints

We develop a two-stage stochastic program for energy and reserve dispatch of a joint power and gas system with a high penetration of renewables. Data-driven distributionally robust chance constraints ensure that there is no load shedding and renewable spillage with high probability. We solve this problem efficiently using conditional value-at-risk approximations and linear decision rules. Out-of-sample experiments show that this model dominates the corresponding stochastic program without chance constraints that models the effects of load shedding and renewable spillage explicitly.     

Robust optimal reinsurance and investment strategies for an AAI with multiple risks

This paper studies the robust optimal reinsurance and investment problem for an ambiguity averse insurer (abbr. AAI). The AAI sells insurance contracts and has access to proportional reinsurance business. The AAI can invest in a financial market consisting of four assets: one risk-free asset, one bond, one inflation protected bond and one stock, and has different levels of ambiguity aversions towards the risks. The goal of the AAI is to seek the robust optimal reinsurance and investment strategies under the worst case scenario. Here, the nominal interest rate is characterized by the Vasicek model; the inflation index is introduced according to the Fisher’s equation; and the stock price is driven by the Heston’s stochastic volatility model. The explicit forms of the robust optimal strategies and value function are derived by introducing an auxiliary robust optimal control problem and stochastic dynamic programming method. In the end of this paper, a detailed sensitivity analysis is presented to show the effects of market parameters on the robust optimal reinsurance policy, the robust optimal investment strategy and the utility loss when ignoring ambiguity.     

Two-Stage Stochastic Variational Inequality Arising from Stochastic Programming

We consider a two-stage stochastic variational inequality arising from a general convex two-stage stochastic programming problem, where the random variables have continuous distributions. The equivalence between the two problems is shown under some moderate conditions, and the monotonicity of the two-stage stochastic variational inequality is discussed under additional conditions. We provide a discretization scheme with convergence results and employ the progressive hedging method with double parameterization to solve the discretized stochastic variational inequality. As an application, we show how the water resources management problem under uncertainty can be transformed from a two-stage stochastic programming problem to a two-stage stochastic variational inequality, and how to solve it, using the discretization scheme and the progressive hedging method with double parameterization.

     

Distributionally robust optimization with matrix moment constraints: Lagrange duality and cutting plane methods

A key step in solving minimax distributionally robust optimization (DRO) problems is to reformulate the inner maximization w.r.t. probability measure as a semiinfinite programming problem through Lagrange dual. Slater type conditions have been widely used for strong duality (zero dual gap) when the ambiguity set is defined through moments. In this paper, we investigate effective ways for verifying the Slater type conditions and introduce other conditions which are based on lower semicontinuity of the optimal value function of the inner maximization problem. Moreover, we propose two discretization schemes for solving the DRO with one for the dualized DRO and the other directly through the ambiguity set of the DRO. In the absence of strong duality, the discretization scheme via Lagrange duality may provide an upper bound for the optimal value of the DRO whereas the direct discretization approach provides a lower bound. Two cutting plane schemes are consequently proposed: one for the discretized dualized DRO and the other for the minimax DRO with discretized ambiguity set. Convergence analysis is presented for the approximation schemes in terms of the optimal value, optimal solutions and stationary points. Comparative numerical results are reported for the resulting algorithms.

     

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.