Test problems in stochastic multistage programming

This paper provides a set of stochastic multistage programs where the evolvement of uncertain factors is given by stochastic processes. We treat a practical problem statement within the field of managing fixed-income securities. Detailed information on the used parameter values in various interest rate models is given. Barycentric approximation is applied to obtain computational results; different measures of the achieved goodness of approximation are indicated     

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.     

Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming

Decomposition has proved to be one of the more effective tools for the solution of large-scale problems, especially those arising in stochastic programming. A decomposition method with wide applicability is Benders' decomposition, which has been applied to both stochastic programming as well as integer programming problems. However, this method of decomposition relies on convexity of the value function of linear programming subproblems. This paper is devoted to a class of problems in which the second-stage subproblem(s) may impose integer restrictions on some variables. The value function of such integer subproblem(s) is not convex, and new approaches must be designed. In this paper, we discuss alternative decomposition methods in which the second-stage integer subproblems are solved using branch-and-cut methods. One of the main advantages of our decomposition scheme is that Stochastic Mixed-Integer Programming (SMIP) problems can be solved by dividing a large problem into smaller MIP subproblems that can be solved in parallel. This paper lays the foundation for such decomposition methods for two-stage stochastic mixed-integer programs.     

SEQUENTIAL QUADRATIC PROGRAMMING METHODS FOR OPTIMAL CONTROL PROBLEMS WITH STATE CONSTRAINTS

A Kind of direct methods is presented for the solution of optimal control problems with state constraints.These methods are sequential quadratic programming methods.At every iteration a quadratic programming which is obtained by quadratic approximation to Lagrangian function and Linear approximations to constraints is solved to get a search direction for a merit function.The merit function is formulated by augmenting the Lagrangian funetion with a penalty term.A line search is carried out along the search direction to determine a step length such that the merit function is decreased.The methods presented in this paper include continuous sequential quadratic programming methods and discreate sequential quadrade programming methods.     

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.     

An unconstrained convex programming approach to solving convex quadratic programming problems

In this paper, we derive an unconstrained convex programming approach to solving convex quadratic programming problems in standard form. Related duality theory is established by using two simple inequalities. An ?-optimal solution is obtained by solving an unconstrained dual convex program. A dual-to-primal conversion formula is also provided. Some preliminary computational results of using a curved search method is included     

On the role of bounds in stochastic linear programming

Stochastic linear programming (SLP) models involve multivariate integrals. Although in the discretely distributed case these integrals become sums they typically contain a large amount of terms. The purpose of this paper is twofold:On the one hand we discuss the usage of bounds concerning integrals for constructing SLP algorithms and secondly we point out the role of bounds-based algorithms for solving SLP problems. The conceptual considerations are demonstrated in the last section by computational results. The tests have been carried out by utilizing SLP-IOR, our model management system for SLP     

Dynamic programming in stochastic control of systems with delay

We consider optimal control problems for systems described by stochastic differential equations with delay (SDDE). We prove a version of Bellman's principle of optimality (the dynamic programming principle) for a general class of such problems. That the class in general means that both the dynamics and the cost depends on the past in a general way. As an application, we study systems where the value function depends on the past only through some weighted average. For such systems we obtain a Hamilton-Jacobi-Bellman partial differential equation that the value function must solve if it is smooth enough. The weak uniqueness of the SDDEs we consider is our main tool in proving the result. Notions of strong and weak uniqueness for SDDEs are introduced, and we prove that strong uniqueness implies weak uniqueness, just as for ordinary stochastic differential equations.     

ISTMO: An interval reference point-based method for stochastic multiobjective programming problems

In this paper, we present an interactive algorithm (ISTMO) for stochastic multiobjective problems with continuous random variables. This method combines the concept of probability efficiency for stochastic problems with the reference point philosophy for deterministic multiobjective problems. The decision maker expresses her/his references by dividing the variation range of each objective into intervals, and by setting the desired probability for each objective to achieve values belonging to each interval. These intervals may also be redefined during the process. This interactive procedure helps the decision maker to understand the stochastic nature of the problem, to discover the risk level (s)he is willing to assume for each objective, and to learn about the trade-offs among the objectives.     

A class of methods for linear programming

A class of methods is presented for solving standard linear programming problems. Like the simplex method, these methods move from one feasible solution to another at each iteration, improving the objective function as they go. Each such feasible solution is also associated with a basis. However, this feasible solution need not be an extreme point and the basic solution corresponding to the associated basis need not be feasible. Nevertheless, an optimal solution, if one exists, is found in a finite number of iterations (under nondegeneracy). An important example of a method in the class is the reduced gradient method with a slight modification regarding selection of the entering variable.     

An approximation algorithm for a facility location problem with stochastic demands and inventories

We propose a 2-approximation algorithm for a facility location problem with stochastic demands. At open facilities, inventory is kept such that arriving requests find a zero inventory with (at most) some pre-specified probability. Costs incurred are expected transportation costs, facility operating costs and inventory costs.     

Stability results for stochastic programming problems

The paper deals with a statistical approach to stability analysis in nonlinear stochastic programming. Firstly the distribution function of the underlying random variable is estimated by the empirical distribution function, and secondly the problem of estimated parameters is considered. In both the cases the probability that the solution set of the approximate problem, is not contained in an l-neighbourhood of the solution set to the original problem is estimated, and under differentiability properties an asymptotic expansion for the density of the (unique) solution to the approximate problem is derived.     

Multistage stochastic programming: Error analysis for the convex case

We consider convex stochastic multistage problems and present an approximation technique which allows to analyse the error with respect to time. The technique is based on barycentric approximation of conditional and marginal probability spaces and requiresstrict nonanticipativity for the constraint multifunction and thesaddle property for the value functions.Part of this work was carried out at the Institute of Operations Research of the University of Zurich.     

Valid inequalities and restrictions for stochastic programming problems with first order stochastic dominance constraints

Stochastic dominance relations are well studied in statistics, decision theory and economics. Recently, there has been significant interest in introducing dominance relations into stochastic optimization problems as constraints. In the discrete case, stochastic optimization models involving second order stochastic dominance constraints can be solved by linear programming. However, problems involving first order stochastic dominance constraints are potentially hard due to the non-convexity of the associated feasible regions. In this paper we consider a mixed 0–1 linear programming formulation of a discrete first order constrained optimization model and present a relaxation based on second order constraints. We derive some valid inequalities and restrictions by employing the probabilistic structure of the problem. We also generate cuts that are valid inequalities for the disjunctive relaxations arising from the underlying combinatorial structure of the problem by applying the lift-and-project procedure. We describe three heuristic algorithms to construct feasible solutions, based on conditional second order constraints, variable fixing, and conditional value at risk. Finally, we present numerical results for several instances of a real world portfolio optimization problem. This research was supported by the NSF awards DMS-0603728 and DMI-0354678.     

Solving two-stage stochastic programming problems with level decomposition

We propose a new variant of the two-stage recourse model. It can be used e.g., in managing resources in whose supply random interruptions may occur. Oil and natural gas are examples for such resources. Constraints in the resulting stochastic programming problems can be regarded as generalizations of integrated chance constraints. For the solution of such problems, we propose a new decomposition method that integrates a bundle-type convex programming method with the classic distribution approximation schemes. Feasibility and optimality issues are taken into consideration simultaneously, since we use a convex programming method suited for constrained optimization. This approach can also be applied to traditional two-stage problems whose recourse functions can be extended to the whole space in a computationally efficient way. Network recourse problems are an example for such problems. We report encouraging test results with the new method.      

A new regularized stochastic approximation framework for stochastic inverse problems

We study the nonlinear inverse problem of estimating stochastic parameters in the fourth-order partial differential equation with random data. The primary focus is on developing a novel stochastic approximation framework for inverse problems consisting of three key components. As a first step, we reformulate the inverse problem into a stochastic convex optimization problem. The second step includes developing a new regularized stochastic extragradient framework for a nonlinear variational inequality, which subsumes the optimality conditions for the optimization formulation of the inverse problem. The third step involves modeling random variables by a Karhunen–Loève type finite-dimensional noise representation, allowing the direct and the inverse problems to be conveniently discretized. We show that the regularized extragradient methods are strongly convergent in a Hilbert space setting, and we also provide several auxiliary results for the inverse problem, including Lipschitz continuity and a derivative characterization of the solution map. We provide the outcome of computational experiments to estimate stochastic and deterministic parameters. The numerical results demonstrate the feasibility and effectiveness of the developed framework and validate stochastic approximation as an effective method for stochastic inverse problems.     

Dynamic programming for multidimensional stochastic control problems

In this paper we study a general multidimensional diffusion-type stochastic control problem. Our model contains the usual regular control problem, singular control problem and impulse control problem as special cases. Using a unified treatment of dynamic programming, we show that the value function of the problem is a viscosity solution of certain Hamilton-Jacobi-Bellman (HJB) quasivariational inequality. The uniqueness of such a quasi-variational inequality is proved. Supported in part by USA Office of Naval Research grant #N00014-96-1-0262. Supported in part by the NSFC Grant #79790130, the National Distinguished Youth Science Foundation of China Grant #19725106 and the Chinese Education Ministry Science Foundation.