双随机矩阵收敛指数的最好上界

Ｍ．Ｌｅｗｉｎ（１９７４）已得到了ｎ阶本原双随机矩阵收敛（本原）指数的最好上界。本文对不可约非本原和可约双随机矩阵的收敛指数作出估值，从而证明了Ｌｅｗｉｎ的上界是适用于一切双随机矩阵的最好上界。     

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.     

Stochastic second-order cone programming: Applications models

Second-order cone programs are a class of convex optimization problems. We refer to them as deterministic second-order cone programs (DSCOPs) since data defining them are deterministic. In DSOCPs we minimize a linear objective function over the intersection of an affine set and a product of second-order (Lorentz) cones. Stochastic programs have been studied since 1950s as a tool for handling uncertainty in data defining classes of optimization problems such as linear and quadratic programs. Stochastic second-order cone programs (SSOCPs) with recourse is a class of optimization problems that defined to handle uncertainty in data defining DSOCPs. In this paper we describe four application models leading to SSOCPs.     

An arc-exchange decomposition method for multistage dynamic networks with random arc capacities

Multistage dynamic networks with random arc capacities (MDNRAC) have been successfully used for modeling various resource allocation problems in the transportation area. However, solving these problems is generally computationally intensive, and there is still a need to develop more efficient solution approaches. In this paper, we propose a new heuristic approach that solves the MDNRAC problem by decomposing the network at each stage into a series of subproblems with tree structures. Each subproblem can be solved efficiently. The main advantage is that this approach provides an efficient computational device to handle the large-scale problem instances with fairly good solution quality. We show that the objective value obtained from this decomposition approach is an upper bound for that of the MDNRAC problem. Numerical results demonstrate that our proposed approach works very well.     

The value of rolling-horizon policies for risk-averse hydro-thermal planning

We consider the optimal management of a hydro-thermal power system in the mid and long terms. From the optimization point of view, this amounts to a large-scale multistage stochastic linear program, often solved by combining sampling with decomposition algorithms, like stochastic dual dynamic programming. Such methodologies, however, may entail prohibitive computational time, especially when applied to a risk-averse formulation of the problem. We propose instead a risk-averse rolling-horizon policy that is nonanticipative, feasible, and time consistent. The policy is obtained by solving a sequence of risk-averse problems with deterministic constraints for the current time step and future chance and CVaR constraints.The considered hydro-thermal model takes into account losses resulting from run-of-river plants efficiencies as well as uncertain demand and streamflows. Constraints aim at satisfying demand while keeping reservoir levels above minzones almost surely. We show that if the problem uncertainty is represented by a periodic autoregressive stochastic process with lag one, then the probabilistic constraints can be computed explicitly. As a result, each one of the aforementioned risk-averse problems is a medium-size linear program, easy to solve.For a real-life power system we compare our approach with three alternative policies. Namely, a robust nonrolling-horizon policy and two risk-neutral policies obtained by stochastic dual dynamic programming, implemented in nonrolling- and rolling-horizon modes, respectively. Our numerical assessment confirms the superiority of the risk-averse rolling-horizon policy that yields comparable average indicators, but with reduced volatility and with substantially less computational effort.     

Efficient sampling in approximate dynamic programming algorithms

Dynamic Programming (DP) is known to be a standard optimization tool for solving Stochastic Optimal Control (SOC) problems, either over a finite or an infinite horizon of stages. Under very general assumptions, commonly employed numerical algorithms are based on approximations of the cost-to-go functions, by means of suitable parametric models built from a set of sampling points in the d-dimensional state space. Here the problem of sample complexity, i.e., how “fast” the number of points must grow with the input dimension in order to have an accurate estimate of the cost-to-go functions in typical DP approaches such as value iteration and policy iteration, is discussed. It is shown that a choice of the sampling based on low-discrepancy sequences, commonly used for efficient numerical integration, permits to achieve, under suitable hypotheses, an almost linear sample complexity, thus contributing to mitigate the curse of dimensionality of the approximate DP procedure.     

A risk-averse newsvendor with law invariant coherent measures of risk

For general law invariant coherent measures of risk, we derive an equivalent representation of a risk-averse newsvendor problem as a mean-risk model. We prove that the higher the weight of the risk functional, the smaller the order quantity. Our theoretical results are confirmed by sample-based optimization.     

Analysis of stochastic dual dynamic programming method

In this paper we discuss statistical properties and convergence of the Stochastic Dual Dynamic Programming (SDDP) method applied to multistage linear stochastic programming problems. We assume that the underline data process is stagewise independent and consider the framework where at first a random sample from the original (true) distribution is generated and consequently the SDDP algorithm is applied to the constructed Sample Average Approximation (SAA) problem. Then we proceed to analysis of the SDDP solutions of the SAA problem and their relations to solutions of the “true” problem. Finally we discuss an extension of the SDDP method to a risk averse formulation of multistage stochastic programs. We argue that the computational complexity of the corresponding SDDP algorithm is almost the same as in the risk neutral case.     

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 stochastic programming approach for planning horizons of infinite horizon capacity planning problems

Planning horizon is a key issue in production planning. Different from previous approaches based on Markov Decision Processes, we study the planning horizon of capacity planning problems within the framework of stochastic programming. We first consider an infinite horizon stochastic capacity planning model involving a single resource, linear cost structure, and discrete distributions for general stochastic cost and demand data (non-Markovian and non-stationary). We give sufficient conditions for the existence of an optimal solution. Furthermore, we study the monotonicity property of the finite horizon approximation of the original problem. We show that, the optimal objective value and solution of the finite horizon approximation problem will converge to the optimal objective value and solution of the infinite horizon problem, when the time horizon goes to infinity. These convergence results, together with the integrality of decision variables, imply the existence of a planning horizon. We also develop a useful formula to calculate an upper bound on the planning horizon. Then by decomposition, we show the existence of a planning horizon for a class of very general stochastic capacity planning problems, which have complicated decision structure.     

Optimal myopic policies and index policies for stochastic scheduling problems

Stochastic scheduling problems are considered by using discounted dynamic programming. Both, maximizing pure rewards and minimizing linear holding costs are treated in one common Markov decision problem. A sufficient condition for the optimality of the myopic policy for finite and infinite horizon is given. For the infinite horizon case we show the optimality of an index policy and give a sufficient condition for the index policy to be myopic. Moreover, the relation between the two sufficient conditions is discussed.     

An upper bound for SLP using first and total second moments

In 1987, J. Dulá considered the problem of finding an upper bound for the expectation of a so-called simplicial function of a random vector and used for this purpose first and total second moments. Under the same moment conditions we consider some different cases of recourse functions and demonstrate how the related moment problems can be solved by solving nonsmooth (unconstrained) optimization problems and thereafter satisfying simple linear constraint systems.     

Making inefficient market indices efficient

This paper uses the concept of Marginal Conditional Stochastic Dominance and a generalization of the 50% Portfolio Rule to develop a tractable and parsimonious methodology for constructing a second degree Stochastic Dominance (SSD) efficient portfolio from a given, inefficient index. Because the SSD approach considers the entire probability distributions of asset returns, the resulting portfolios are efficient with respect to all risk-averse, utility-maximizing investors regardless of the form of their utility functions or the distributions of asset returns.     

Asymptotically optimal production policies in dynamic stochastic jobshops with limited buffers

We consider a production planning problem for a jobshop with unreliable machines producing a number of products. There are upper and lower bounds on intermediate parts and an upper bound on finished parts. The machine capacities are modelled as finite state Markov chains. The objective is to choose the rate of production so as to minimize the total discounted cost of inventory and production. Finding an optimal control policy for this problem is difficult. Instead, we derive an asymptotic approximation by letting the rates of change of the machine states approach infinity. The asymptotic analysis leads to a limiting problem in which the stochastic machine capacities are replaced by their equilibrium mean capacities. The value function for the original problem is shown to converge to the value function of the limiting problem. The convergence rate of the value function together with the error estimate for the constructed asymptotic optimal production policies are established.     

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.     

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.     

A branch and bound method for stochastic global optimization

A stochastic branch and bound method for solving stochastic global optimization problems is proposed. As in the deterministic case, the feasible set is partitioned into compact subsets. To guide the partitioning process the method uses stochastic upper and lower estimates of the optimal value of the objective function in each subset. Convergence of the method is proved and random accuracy estimates derived. Methods for constructing stochastic upper and lower bounds are discussed. The theoretical considerations are illustrated with an example of a facility location problem.     

Investment models based on clustered scenario trees

Stochastic programming is widely applied in financial decision problems. In particular, when we need to carry out the actual calculations for portfolio selection problems, we have to assign a value for each expected return and the associated conditional probability in advance. These estimated random parameters often rely on a scenario tree representing the distribution of the underlying asset returns. One of the drawbacks is that the estimated parameters may be deviated from the actual ones. Therefore, robustness is considered so as to cope with the issue of parameter inaccuracy. In view of this, we propose a clustered scenario-tree approach, which accommodates the parameter inaccuracy problem in the context of a scenario tree.     

A Branch-and-Price Algorithm for the Capacitated Arc Routing Problem with Stochastic Demands

We address the Capacitated Arc Routing Problem with Stochastic Demands (CARPSD), which we formulate as a Set Partitioning Problem. The CARPSD is solved by a Branch-and-Price algorithm, which we apply without graph transformation. The demand’s stochastic nature is incorporated into the pricing problem. Computational results are reported.     

An efficient computational method for a stochastic dynamic lot-sizing problem under service-level constraints

We provide an efficient computational approach to solve the mixed integer programming (MIP) model developed by Tarim and Kingsman [8] for solving a stochastic lot-sizing problem with service level constraints under the static-dynamic uncertainty strategy. The effectiveness of the proposed method hinges on three novelties: (i) the proposed relaxation is computationally efficient and provides an optimal solution most of the time, (ii) if the relaxation produces an infeasible solution, then this solution yields a tight lower bound for the optimal cost, and (iii) it can be modified easily to obtain a feasible solution, which yields an upper bound. In case of infeasibility, the relaxation approach is implemented at each node of the search tree in a branch-and-bound procedure to efficiently search for an optimal solution. Extensive numerical tests show that our method dominates the MIP solution approach and can handle real-life size problems in trivial time.