On complexity of multistage stochastic programs

In this paper we derive estimates of the sample sizes required to solve a multistage stochastic programming problem with a given accuracy by the (conditional sampling) sample average approximation method. The presented analysis is self-contained and is based on a relatively elementary, one-dimensional, Cramér's Large Deviations Theorem.     

On the complexity of robust geometric programming with polyhedral uncertainty

Geometric Programming is a useful tool with a wide range of applications in engineering. As in real-world problems input data is likely to be affected by uncertainty, robust geometric programming has been introduced. It is an open question whether there exists a tractable reformulation of the robust geometric programming model. We provide a negative answer by showing that robust geometric programming with polyhedral uncertainty is co-NP hard, and provide positive results for the case of interval uncertainty.     

On the complexity of linear programming under finite precision arithmetic

In this paper we study the complexity of solving linear programs in finite precision arithmetic. This is the normal setup in scientific computation, as digital computers work in finite precision. We analyze two aspects of the complexity: one is the number of arithmetic operations required to solve the problem approximately, and the other is the working precision required to carry out some critical computations safely. We show how the conditioning of the problem instance affects the working precision required and the computational requirements of a classical logarithmic barrier algorithm to approximate the optimal value of the problem within a given tolerance. Our results show that these complexity measures depend linearly on the logarithm of a certain condition measure. We carry out the analysis by looking at how well Newton's Method can follow the central trajectory of the feasible set, and computing error bounds in terms of the condition measure. These results can be interpreted as a theoretical indication of good numerical behavior of the logarithmic barrier method, in the sense that a problem instance twice as hard as the other from the numerical point of view, requires only at most twice as much precision to be solved. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.This research has been supported through grants from Fundación Andes, under agreement C12021/7, and FONDECYT (project number 1930948).     

Partially observable multistage stochastic programming

We propose a class of partially observable multistage stochastic programs and describe an algorithm for solving this class of problems. We provide a Bayesian update of a belief-state vector, extend the stochastic programming formulation to incorporate the belief state, and characterize saddle-function properties of the corresponding cost-to-go function. Our algorithm is a derivative of the stochastic dual dynamic programming method.     

Extremization of multi-objective stochastic fractional programming problem

This paper addresses classes of assembled printed circuit boards, which faces certain kinds of errors during its process of manufacturing. Occurrence of errors may lead the manufacturer to be in loss. The encountered problem has two objective functions, one is fractional and the other is a non-linear objective. The manufacturers are confined to maximize the fractional objective and to minimize the non-linear objective subject to stochastic and non-stochastic environment. This problem is decomposed into two problems. A solution approach to this model has been developed in this paper. Results of some test problems are provided.     

Solution approaches for the multiobjective stochastic programming

We survey in this paper various solution approaches for multiobjective stochastic problems where random variables can be in both objectives and constraints parameters. Once a problem requires a stochastic formulation, a first step consists in transforming the problem into its deterministic formulation. We propose to classify and evaluate such transformations with regards to the many proposed concepts of efficiency. The paper addresses also some applications of the multiobjective stochastic programming models.     

On stages and consistency checks in stochastic programming

This paper gives a rigorous definition of a stage, usable for dynamic stochastic programs with both recourse and probabilistic constraints. Algebraic modelling languages can make use of this definition for automatic consistency checks.     

On differential stability in stochastic programming

In this paper optimal solutions of a stochastic programming problem are considered as functions of the underlying probability distribution. Their directional derivatives, in the sense of Gâteaux, are calculated by applying some recent results from the sensitivity analysis of nonlinear programs. These derivatives are employed as a heuristic device in order to derive the asymptotic distribution of statistical estimators of the optimal solutions.     

关于一些凸规划问题的复杂性研究结果

目前,已发表了大量研究各类不同凸规划的低复杂度的障碍函数方法的文章. 利用自和谐理论,对不同的几类凸规划问题构造相应的对数障碍函数,通过两个引理证明这些凸规划问题相应的对数障碍函数都满足自和谐,根据Nesterov 和Nemirovsky的工作证明了所给问题的内点算法具有多项式复杂性.     

On complexity of unconstrained hyperbolic 0-1 programming problems

Single- and multiple-ratio unconstrained hyperbolic 0-1 programming problems are considered. We prove that checking whether these problems have a unique solution is NP-hard. Furthermore, we show that finding the global maximizer of problems with unique solution remains NP-hard. We also discuss complexity of local search and approximability for multiple-ratio problems.     

Decomposition methods in stochastic programming

Stochastic programming problems have very large dimension and characteristic structures which are tractable by decomposition. We review basic ideas of cutting plane methods, augmented Lagrangian and splitting methods, and stochastic decomposition methods for convex polyhedral multi-stage stochastic programming problems.     

Parallel decomposition of multistage stochastic programming problems

A new decomposition method for multistage stochastic linear programming problems is proposed. A multistage stochastic problem is represented in a tree-like form and with each node of the decision tree a certain linear or quadratic subproblem is associated. The subproblems generate proposals for their successors and some backward information for their predecessors. The subproblems can be solved in parallel and exchange information in an asynchronous way through special buffers. After a finite time the method either finds an optimal solution to the problem or discovers its inconsistency. An analytical illustrative example shows that parallelization can speed up computation over every sequential method. Computational experiments indicate that for large problems we can obtain substantial gains in efficiency with moderate numbers of processors.This work was partly supported by the International Institute for Applied Systems Analysis, Laxenburg, Austria.     

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.     

On statistical sensitivity analysis in stochastic programming

Different approaches to statistical sensitivity analysis for optimal solutions of stochastic programs are discussed and compared. Possibilities of drawing conclusions about asymptotic behavior of estimated optimal solutions by means of stability properties of auxiliary randomly perturbed convex quadratic programs are indicated and illustrated on a numerical example.     

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.     

Bilinear programming and structured stochastic games

One-step algorithms are presented for two classes of structured stochastic games, namely, those with additive rewards and transitions and those which have switching controllers. Solutions to such classes of games under the average reward criterion can be derived from optimal solutions to appropriate bilinear programs. The validity of using bilinear programming as a solution method follows from two preliminary theorems, the first of which is a complete classification of undiscounted stochastic games with optimal stationary strategies. The second of these preliminary theorems relaxes the conditions of the classification theorem for certain classes of stochastic games and provides the basis for the bilinear programming results. Analogous results hold for the discounted stochastic games with the above special structures.This research was supported in part by the Air Force Office of Scientific Research and by the National Science Foundation under Grant No. ECS-850-3440.     

On the complexity of stochastic integration

We study the complexity of approximating stochastic integrals with error for various classes of functions. For Ito integration, we show that the complexity is of order , even for classes of very smooth functions. The lower bound is obtained by showing that Ito integration is not easier than Lebesgue integration in the average case setting with the Wiener measure. The upper bound is obtained by the Milstein algorithm, which is almost optimal in the considered classes of functions. The Milstein algorithm uses the values of the Brownian motion and the integrand. It is bilinear in these values and is very easy to implement. For Stratonovich integration, we show that the complexity depends on the smoothness of the integrand and may be much smaller than the complexity of Ito integration.

     

Stochastic semidefinite programming: a new paradigm for stochastic optimization

Semidefinite programs are a class of optimization problems that have been studied extensively during the past 15 years. Semidefinite programs are naturally related to linear programs, and both are defined using deterministic data. Stochastic programs were introduced in the 1950s as a paradigm for dealing with uncertainty in data defining linear programs. In this paper, we introduce stochastic semidefinite programs as a paradigm for dealing with uncertainty in data defining semidefinite programs.The work of this author was supported in part by the U.S. Army Research Office under Grant DAAD 19-00-1-0465. The material in this paper is part of the doctoral dissertation of this author in preparation at Washington State University.     

Linear programming,complexity theory and elementary functional analysis

We propose analyzing interior-point methods using notions of problem-instance size which are direct generalizations of the condition number of a matrix. The notions pertain to linear programming quite generally; the underlying vector spaces are not required to be finite-dimensional and, more importantly, the cones defining nonnegativity are not required to be polyhedral. Thus, for example, the notions are appropriate in the context of semi-definite programming. We prove various theorems to demonstrate how the notions can be used in analyzing interior-point methods. These theorems assume little more than that the interiors of the cones (defining nonnegativity) are the domains of self-concordant barrier functions.Research supported by NSF Grant #CCR-9103285 and IBM. This paper was conceived in part while the author was sponsored by the visiting scientist program at the IBM T.J. Watson Research Center.