Sublinear upper bounds for stochastic programs with recourse

Separable sublinear functions are used to provide upper bounds on the recourse function of a stochastic program. The resulting problem's objective involves the inf-convolution of convex functions. A dual of this problem is formulated to obtain an implementable procedure to calculate the bound. Function evaluations for the resulting convex program only require a small number of single integrations in contrast with previous upper bounds that require a number of function evaluations that grows exponentially in the number of random variables. The sublinear bound can often be used when other suggested upper bounds are intractable. Computational results indicate that the sublinear approximation provides good, efficient bounds on the stochastic program objective value.This research has been partially supported by the National Science Foundation. The first author's work was also supported in part by Office of Naval Research Grant N00014-86-K-0628 and by the National Research Council under a Research Associateship at the Naval Postgraduate School, Monterey, California.     

A tighter variant of Jensen’s lower bound for stochastic programs and separable approximations to recourse functions

In this paper, we propose a new method to compute lower bounds on the optimal objective value of a stochastic program and show how this method can be used to construct separable approximations to the recourse functions. We show that our method yields tighter lower bounds than Jensen’s lower bound and it requires a reasonable amount of computational effort even for large problems. The fundamental idea behind our method is to relax certain constraints by associating dual multipliers with them. This yields a smaller stochastic program that is easier to solve. We particularly focus on the special case where we relax all but one of the constraints. In this case, the recourse functions of the smaller stochastic program are one dimensional functions. We use these one dimensional recourse functions to construct separable approximations to the original recourse functions. Computational experiments indicate that our lower bounds can significantly improve Jensen’s lower bound and our recourse function approximations can provide good solutions.     

Stochastic programs with recourse: An upper bound and the related moment problem

The probability measureP ^O on multidimensional intervals in the extension of the Edmundson-Madansky upper bound for stochastically dependent random variables, derived recently in [7], is shown to be the uniquely determined extremal solution of a particular multivariate moment problem. A necessary and sufficient condition for the feasibility of this moment problem is derived, which is shown to coincide for the univariate moment problem with the simplex containing the moment space (see [15]).A first draft of this paper was written during the authors stay at the Mathematics Research Center, University of Wisconsin-Madison, during January 1986, with support by the National Science Foundation, Grant No. DCR-8502202; the generous support by these institutions is greatly appreciated.     

An upper bound on the expectation of simplicial functions of multivariate random variables

We introduce an upper bound on the expectation of a special class of sublinear functions of multivariate random variables defined over the entire Euclidean space without an independence assumption. The bound can be evaluated easily requiring only the solution of systems of linear equations thus permitting implementations in high-dimensional space. Only knowledge on the underlying distribution means and second moments is necessary. We discuss pertinent techniques on dominating general sublinear functions by using simpler sublinear and polyhedral functions and second order quadratic functions.     

L-shaped decomposition of two-stage stochastic programs with integer recourse

We consider two-stage stochastic programming problems with integer recourse. The L-shaped method of stochastic linear programming is generalized to these problems by using generalized Benders decomposition. Nonlinear feasibility and optimality cuts are determined via general duality theory and can be generated when the second stage problem is solved by standard techniques. Finite convergence of the method is established when Gomory’s fractional cutting plane algorithm or a branch-and-bound algorithm is applied.     

Nested decomposition of multistage nonlinear programs with recourse

Nested decomposition is extended to the case of arborescent nonlinear programs. Duals of extensive forms of nonlinear multistage stochastic programs constitute a particular class of those problems; the method is tested on a set of problems of that type.     

一类带有MaxEMin评判的补偿型随机规划算法

补偿型随机规划一般假定随机变量的概率分布具有完备信息, 但实际情况往往只能获得部分信息. 针对离散概率具有一类线性部分信息条件而建立了带有MaxEMin评判的两阶段随机规划模型, 借助二次规划和对偶分解方法得到了可行性切割和最优切割, 给出了基于L-型的求解算法, 并证明了算法的收敛性. 通过数值实验表明了算法的有效性.     

Approximate nonlinear programming algorithms for solving stochastic programs with recourse

This paper summarizes the main results on approximate nonlinear programming algorithms investigated by the author. These algorithms are obtained by combining approximation and nonlinear programming algorithms. They are designed for programs in which the evaluation of the objective functions is very difficult so that only their approximate values can be obtained. Therefore, these algorithms are particularly suitable for stochastic programming problems with recourse.Project supported by the National Natural Science Foundation of China.     

带补偿的随机二次规划的近似Lagrange-Newton方法

In this paper, two-stage stochastic quadratic programming problems with equality constraints are considered. By Monte Carlo simulation-based approximations of the objective function and its first (second)derivative,an inexact Lagrange-Newton type method is proposed.It is showed that this method is globally convergent with probability one. In particular, the convergence is local superlinear under an integral approximation error bound condition.Moreover, this method can be easily extended to solve stochastic quadratic programming problems with inequality constraints.     

New strong duality results for convex programs with separable constraints

It is known that convex programming problems with separable inequality constraints do not have duality gaps. However, strong duality may fail for these programs because the dual programs may not attain their maximum. In this paper, we establish conditions characterizing strong duality for convex programs with separable constraints. We also obtain a sub-differential formula characterizing strong duality for convex programs with separable constraints whenever the primal problems attain their minimum. Examples are given to illustrate our results.     

Designing a majorization scheme for the recourse function in two-stage stochastic linear programming

We discuss issues pertaining to the domination from above of the second-stage recourse function of a stochastic linear program and we present a scheme to majorize this function using a simpler sublinear function. This majorization is constructed using special geometrical attributes of the recourse function. The result is a proper, simplicial function with a simple characterization which is well-suited for calculations of its expectation as required in the computation of stochastic programs. Experiments indicate that the majorizing function is well-behaved and stable.     

Extended Farkas lemma and strong duality for composite optimization problems with DC functions

In this paper, we consider the optimization problem in locally convex Hausdorff topological vector spaces with objectives given as the difference of two composite functions and constraints described by an arbitrary (possibly infinite) number of convex inequalities. Using the epigraph technique, we introduce some new constraint qualifications, which completely characterize the Farkas lemma, the dualities between the primal problem and its dual problem. Applications to the conical programming with DC composite function are also given.     

A simple recourse model for power dispatch under uncertain demand

Optimal power dispatch under uncertainty of power demand is tackled via a stochastic programming model with simple recourse. The decision variables correspond to generation policies of a system comprising thermal units, pumped storage plants and energy contracts. The paper is a case study to test the kernel estimation method in the context of stochastic programming. Kernel estimates are used to approximate the unknown probability distribution of power demand. General stability results from stochastic programming yield the asymptotic stability of optimal solutions. Kernel estimates lead to favourable numerical properties of the recourse model (no numerical integration, the optimization problem is smooth convex and of moderate dimension). Test runs based on real-life data are reported. We compute the value of the stochastic solution for different problem instances and compare the stochastic programming solution with deterministic solutions involving adjusted demand portions.This research is supported by the Schwerpunktprogramm Anwendungsbezogene Optimierung und Steuerung of the Deutsche Forschungsgemeinschaft.     

A simulation-based approach to two-stage stochastic programming with recourse

In this paper we consider stochastic programming problems where the objective function is given as an expected value function. We discuss Monte Carlo simulation based approaches to a numerical solution of such problems. In particular, we discuss in detail and present numerical results for two-stage stochastic programming with recourse where the random data have a continuous (multivariate normal) distribution. We think that the novelty of the numerical approach developed in this paper is twofold. First, various variance reduction techniques are applied in order to enhance the rate of convergence. Successful application of those techniques is what makes the whole approach numerically feasible. Second, a statistical inference is developed and applied to estimation of the error, validation of optimality of a calculated solution and statistically based stopping criteria for an iterative alogrithm. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Supported by CNPq (Conselho Nacional de Desenvolvimento Científico e Tecnológico), Brasília, Brazil, through a Doctoral Fellowship under grant 200595/93-8.     

Portfolio theory for the recourse certainty equivalent maximizing investor

The portfolio selection problem with one safe andn risky assets is analyzed via a new decision theoretic criterion based on the Recourse Certainty Equivalent (RCE). Fundamental results in portfolio theory, previously studied under the Expected Utility criterion (EU), such as separation theorems, comparative static analysis, and threshold values for inclusion or exclusion of risky assets in the optimal portfolio, are obtained here. In contrast to the EU model, our results for the RCE maximizing investor do not impose restrictions on either the utility function or the underlying probability laws. We also derive a dual portfolio selection problem and provide it with a concrete economic interpretation.Research partly supported by ONR Contracts N0014-81-C-0236 and N00014-82-K-0295, and NSF Grant SES-8408134 with the Center for Cybernetic Studies, The University of Texas at Austin.Partly supported by NSF Grant DDM-8896112.Partly supported by AFOSR Grant 0218-88 and NSF Grant ECS-8802239 at the University of Maryland, Baltimore Campus.     

Equilibrium prices supported by dual price functions in markets with non-convexities

The issue of finding market clearing prices in markets with non-convexities has had a renewed interest due to the deregulation of the electricity sector. In the day-ahead electricity market, equilibrium prices are calculated based on bids from generators and consumers. In most of the existing markets, several generation technologies are present, some of which have considerable non-convexities, such as capacity limitations and large start-up costs. In this paper we present equilibrium prices composed of a commodity price and an uplift charge. The prices are based on the generation of a separating valid inequality that supports the optimal resource allocation. In the case when the sub-problem generated as the integer variables are held fixed to their optimal values possess the integrality property, the generated prices are also supported by non-linear price functions that are the basis for integer programming duality.     

Nonanticipativity in stochastic programming

The paper gives strong duality results in multistage stochastic programming without assuming compactness and without applying induction arguments.     

Guaranteeing approach to solving quantile optimization problems

This paper presents a numerical method for solving quantile optimization problems, i.e. stochastic programming problems in which the quantile of the distribution of an objective function is the criterion to be optimized.     

A piecewise linear upper bound on the network recourse function

We consider the optimal value of a pure minimum cost network flow problem as a function of supply, demand and arc capacities. We present a new piecewise linear upper bound on this function, which is called the network recourse function. The bound is compared to the standard Madansky bound, and is shown computationally to be a little weaker, but much faster to find. The amount of work is linear in the number of stochastic variables, not exponential as is the case for the Madansky bound. Therefore, the reduction in work increases as the number of stochastic variables increases. Computational results are presented.