Volume 2015http://edoc.hu-berlin.de/18452/3722024-03-28T21:29:11Z2024-03-28T21:29:11ZClustering of sample average approximation for stochastic programChen, Lijianhttp://edoc.hu-berlin.de/18452/91032020-03-07T04:14:48Z2015-10-05T00:00:00ZClustering of sample average approximation for stochastic program
Chen, Lijian
http://dx.doi.org/10.18452/8451
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We present an improvement to the Sample Average Approximation (SAA) method for two-stage stochasticprogram. Although the SAA has nice theoretical properties, such as convergence in probability and consistency,as long as the sample is large enough, the requirement on the sample size is always a concern forboth academia and practitioners. Our clustering method employs the Maximum Volume Inscribed Ellipsoid(MVIE) to approximate the feasible set of each scenario and calculates a measure of similarity. The scenariosare clustered based on such a measure of similarity and our clustering method reduces the sample size considerably.Moreover, the clustering method will offer managerial implications by highlighting the matteringscenarios. The clustering method would be implemented in a distributed computational infrastructure withlow-cost computers.
2015-10-05T00:00:00ZRisk measures for vector-valued returnsPichler, Aloishttp://edoc.hu-berlin.de/18452/91022020-03-07T04:14:47Z2015-09-16T00:00:00ZRisk measures for vector-valued returns
Pichler, Alois
http://dx.doi.org/10.18452/8450
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Portfolios, which are exposed to different currencies, have separate and different returns ineach individual currency and are thus vector-valued in a natural way.This paper investigates the natural domain of these risk measures. A Banach space is presented,for which the risk measure is continuous, and which reflects the vector-valued outcomesof the corresponding risk measures from mathematical finance. We develop its key properties and describe the corresponding duality theory. We finally outline extensions of this space, which are along classical Lp spaces.
2015-09-16T00:00:00ZParallel stochastic optimization based on descent algorithmsBilenne, Olivierhttp://edoc.hu-berlin.de/18452/91012020-03-07T04:14:47Z2015-10-16T00:00:00ZParallel stochastic optimization based on descent algorithms
Bilenne, Olivier
http://dx.doi.org/10.18452/8449
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This study addresses the stochastic optimization of a function unknown in closed form which can only be estimated based on measurementsor simulations. We consider parallel implementations of a class of stochasticoptimization methods that consist of the iterative application of a descent algorithmto a sequence of approximation functions converging in some sense to the function of interest. After discussing classical parallel modes of implementations (Jacobi, Gauss-Seidel, random, Gauss-Southwell), we devise effort-savingimplementation modes where the pace of application of the considered descentalgorithm along individual coordinates is coordinated with the evolution of the estimated accuracy of the convergent function sequence. It is shown that this approach can be regarded as a Gauss-Southwell implementation of the initialmethod in an augmented space. As an example of application we study the distributed optimization of stochastic networks using a scaled gradient projection algorithm with approximate line search, for which asymptotic propertiesare derived.
2015-10-16T00:00:00ZConvergence of the Smoothed Empirical Process in Nested DistancePflug, Georg Ch.Pichler, Aloishttp://edoc.hu-berlin.de/18452/91002020-03-07T04:14:47Z2015-09-14T00:00:00ZConvergence of the Smoothed Empirical Process in Nested Distance
Pflug, Georg Ch.; Pichler, Alois
http://dx.doi.org/10.18452/8448
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
The nested distance, also process distance, provides a quantitative measure of distance for stochastic processes. It is the crucial and determining distance for stochastic optimization problems.In this paper we demonstrate first that the empirical measure, which is built from observed sample paths, does not converge in nested distance to its underlying distribution. We show that smoothing convolutions, which are appropriately adapted from classical density estimation using kernels, can be employed to modify the empirical measure in order to obtain stochastic processes, which converge in nested distance to the underlying process. We employ the results to estimate transition probabilities at each time moment. Finally we construct processes with discrete sample space from observed empirical paths, which approximate well the original stochastic process as they converge in nested distance.
2015-09-14T00:00:00ZStatistical Estimation of Composite Risk Functionals and Risk Optimization ProblemsDentcheva, DarinkaPenev, SpiridonRuszczynski, Andrzejhttp://edoc.hu-berlin.de/18452/90992020-03-07T04:14:47Z2015-05-12T00:00:00ZStatistical Estimation of Composite Risk Functionals and Risk Optimization Problems
Dentcheva, Darinka; Penev, Spiridon; Ruszczynski, Andrzej
http://dx.doi.org/10.18452/8447
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We address the statistical estimation of composite functionals whichmay be nonlinear in the probability measure. Our study is motivated bythe need to estimate coherent measures of risk, which become increasinglypopular in finance, insurance, and other areas associated with optimization under uncertainty and risk. We establish central limit formulae forcomposite risk functionals. Furthermore, we discuss the asymptotic behavior of optimization problems whose objectives are composite risk functionals and we establish a central limit formula of their optimal valueswhen an estimator of the risk functional is used. While the mathematicalstructures accommodate commonly used coherent measures of risk, theyhave more general character, which may be of independent interest.
2015-05-12T00:00:00ZA Comment on "Computational Complexityof Stochastic Programming Problems"Hanasusanto, Grani A.Kuhn, DanielWiesemann, Wolframhttp://edoc.hu-berlin.de/18452/90982020-03-07T04:14:47Z2015-04-22T00:00:00ZA Comment on "Computational Complexityof Stochastic Programming Problems"
Hanasusanto, Grani A.; Kuhn, Daniel; Wiesemann, Wolfram
http://dx.doi.org/10.18452/8446
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Although stochastic programming problems were always believed to be computationally chal-lenging, this perception has only recently received a theoretical justification by the seminal workof Dyer and Stougie (Mathematical Programming A, 106(3):423{432, 2006). Amongst others,that paper argues that linear two-stage stochastic programs with fixed recourse are #P-hard evenif the random problem data is governed by independent uniform distributions. We show thatDyer and Stougie's proof is not correct, and we offer a correction which establishes the strongerresult that even the approximate solution of such problems is #P-hard for a sufficiently highaccuracy. We also prove that the approximate solution of linear two-stage stochastic programswith random recourse is strongly #P-hard.
2015-04-22T00:00:00ZA Simulation Based Approach to Solve A Specific Type of Chance Constrained OptimizationChen, Lijianhttp://edoc.hu-berlin.de/18452/90972020-03-07T04:14:46Z2015-04-09T00:00:00ZA Simulation Based Approach to Solve A Specific Type of Chance Constrained Optimization
Chen, Lijian
http://dx.doi.org/10.18452/8445
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We solve the chance constrained optimization with convexfeasible set through approximating the chance constraint by another convexsmooth function. The approximation is based on the numerical properties of theBernstein polynomial that is capable of effectively controlling the approximationerror for both function value and gradient. Thus we adopt a first-order algorithmto reach a satisfactory solution which is expected to be optimal. When theexplicit expression of joint distribution is not available, we then use Monte Carloapproach to numerically evaluate the chance constraint to obtain an optimalsolution by probability. Numerical results for known problem instances arepresented.
2015-04-09T00:00:00Z