Volume 2010http://edoc.hu-berlin.de/18452/3672024-04-23T15:15:05Z2024-04-23T15:15:05ZA computational study of a solver system forprocessing two-stage stochastic linearprogramming problemsZverovich, VictorFábián, C.Ellison, FrancisMitra, Gautamhttp://edoc.hu-berlin.de/18452/90682024-02-28T11:42:37Z2010-11-29T00:00:00ZA computational study of a solver system forprocessing two-stage stochastic linearprogramming problems
Zverovich, Victor; Fábián, C.; Ellison, Francis; Mitra, Gautam
http://dx.doi.org/10.18452/8416
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
2010-11-29T00:00:00ZConstruction of Risk-Averse Enhanced Index FundsLejeune, MiguelSamatli-Pac, Gülayhttp://edoc.hu-berlin.de/18452/90672024-02-28T09:20:11Z2010-11-19T00:00:00ZConstruction of Risk-Averse Enhanced Index Funds
Lejeune, Miguel; Samatli-Pac, Gülay
http://dx.doi.org/10.18452/8415
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We propose a partial replication strategy to construct risk-averse enhanced index funds. Our model takes into account the parameter estimation risk by defining the asset returns and the return covariance terms as random variables. The variance of the index fund return is forced to be below a low-risk threshold with a largeprobability, thereby limiting the market risk exposure of the investors and the moral hazard associated with thewage structure of fund managers. The resulting stochastic integer problem is reformulated through the derivationof a deterministic equivalent for the risk constraint and the use of a block decomposition technique. We developan exact outer approximation method based on the relaxation of some binary restrictions and the reformulation ofthe cardinality constraint. The method provides a hierarchical organization of the computations with expandingsets of integer-restricted variables and outperforms the Bonmin and the Cplex 12.1 solvers. The methodcan solve very large (up to 1000 securities) instances, converges fast, scales well, and is general enough to beapplicable to problems with buy-in threshold constraints. Cross-validation tests show that the constructed fundstrack closely and are consistently less risky than the benchmark on the out-of-sample period.
2010-11-19T00:00:00ZSampling-based decomposition methods for risk-averse multistage programsGuigues, VincentRömisch, Wernerhttp://edoc.hu-berlin.de/18452/90662024-02-28T09:24:10Z2010-10-20T00:00:00ZSampling-based decomposition methods for risk-averse multistage programs
Guigues, Vincent; Römisch, Werner
http://dx.doi.org/10.18452/8414
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We define a risk averse nonanticipative feasible policy for multistage stochastic programsand propose a methodology to implement it. The approach is based on dynamic programmingequations written for a risk averse formulation of the problem.This formulation relies on a new class of multiperiod risk functionals called extended polyhedralrisk measures. Dual representations of such risk functionals are given and used to derive conditionsof coherence. In the one-period case, conditions for convexity and consistency with second orderstochastic dominance are also provided. The risk averse dynamic programming equations arespecialized considering convex combinations of one-period extended polyhedral risk measures suchas spectral risk measures.To implement the proposed policy, the approximation of the risk averse recourse functionsfor stochastic linear programs is discussed. In this context, we detail a stochastic dual dynamicprogramming algorithm which converges to the optimal value of the risk averse problem.
2010-10-20T00:00:00ZOn joint probabilistic constraints with Gaussian coefficient matrixAckooij, W. VanHenrion, R.Möller, A.Zorgati, R.http://edoc.hu-berlin.de/18452/90652024-02-28T09:26:40Z2010-10-19T00:00:00ZOn joint probabilistic constraints with Gaussian coefficient matrix
Ackooij, W. Van; Henrion, R.; Möller, A.; Zorgati, R.
http://dx.doi.org/10.18452/8413
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
The paper deals with joint probabilistic constraints defined by a Gaussiancoefficient matrix. It is shown how to explicitly reduce the computation ofvalues and gradients of the underlying probability function to that of Gaussiandistribution functions. This allows to employ existing efficient algorithms forcalculating this latter class of function in order to solve probabilistically constrainedoptimization problems of the indicated type. Results are illustratedby an example from energy production.
2010-10-19T00:00:00ZPattern-Based Modeling and Solution of Probabilistically Constrained Optimization ProblemsLejeune, Miguel A.http://edoc.hu-berlin.de/18452/90642020-03-07T04:14:40Z2010-08-25T00:00:00ZPattern-Based Modeling and Solution of Probabilistically Constrained Optimization Problems
Lejeune, Miguel A.
http://dx.doi.org/10.18452/8412
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We propose a new modeling and solution method for probabilistically constrained optimization problems.The methodology is based on the integration of the stochastic programming and combinatorialpattern recognition fields. It permits the very fast solution of stochastic optimization problems in which the random variables are represented by an extremely large number of scenarios. The methodinvolves the binarization of the probability distribution, and the generation of a consistent partially defined Boolean function (pdBf) representing the combination (F,p) of the binarized probability distributionF and the enforced probability level p. We show that the pdBf representing (F,p) can becompactly extended as a disjunctive normal form (DNF). The DNF is a collection of combinatorialp-patterns, each of which defining sufficient conditions for a probabilistic constraint to hold. We propose two linear programming formulations for the generation of p-patterns which can be subsequently used to derive a linear programming inner approximation of the original stochastic problem.A formulation allowing for the concurrent generation of a p-pattern and the solution of the deterministic equivalent of the stochastic problem is also proposed. Results show that large-scale stochastic problems, in which up to 50,000 scenarios are used to describe the stochastic variables, can be consistentlysolved to optimality within a few seconds.
2010-08-25T00:00:00ZConvex duality in stochastic programming and mathematical financePennanen, Teemuhttp://edoc.hu-berlin.de/18452/90632020-03-07T04:14:39Z2010-08-25T00:00:00ZConvex duality in stochastic programming and mathematical finance
Pennanen, Teemu
http://dx.doi.org/10.18452/8411
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This paper proposes a general duality framework for the problem of minimizing a convex integral functional over a space of stochastic processes adapted to a given ﬁltration. The framework uniﬁes many well-known duality frameworks from operations research and mathematical ﬁnance. The uniﬁcation allows the extension of some useful techniquesfrom these two ﬁelds to a much wider class of problems. In particular, combining certain ﬁnite-dimensional techniques from convex analysis with measure theoretic techniques from mathematical ﬁnance, we are able to close the duality gap in some situations where traditional topological arguments fail.
2010-08-25T00:00:00ZStability and sensitivity analysis of stochastic programs with second order dominance constraintsLiu, YongchaoXu, Huifuhttp://edoc.hu-berlin.de/18452/90622020-03-07T04:14:39Z2010-05-25T00:00:00ZStability and sensitivity analysis of stochastic programs with second order dominance constraints
Liu, Yongchao; Xu, Huifu
http://dx.doi.org/10.18452/8410
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In this paper we present stability and sensitivity analysis of a stochastic optimizationproblem with stochastic second order dominance constraints. We consider perturbation of theunderlying probability measure in the space of regular measures equipped with pseudometricdiscrepancy distance ( [30]). By exploiting a result on error bound in semi-inﬁnite programmingdue to Gugat [13], we show under the Slater constraint qualiﬁcation that the optimal valuefunction is Lipschitz continuous and the optimal solution set mapping is upper semicontinuouswith respect to the perturbation of the probability measure. In particular, we consider the case when the probability measure is approximated by empirical probability measure and show the exponential rate of convergence of optimal solution obtained from solving the approximation problem. The analysis is extended to the stationary points when the objective function is nonconvex.
2010-05-25T00:00:00ZReformulation of general chance constrained problems using the penalty functionsBranda, Martinhttp://edoc.hu-berlin.de/18452/90612020-03-07T04:14:39Z2010-06-04T00:00:00ZReformulation of general chance constrained problems using the penalty functions
Branda, Martin
http://dx.doi.org/10.18452/8409
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We explore reformulation of nonlinear stochastic programs with several joint chance constraints by stochastic programs with suitably chosenpenalty-type objectives. We show that the two problems are asymptotically equivalent. Simpler cases with one chance constraint and particular penalty functions were studied in [5, 9]. The obtained problems with penalties and with a ﬁxed set of feasible solutions are simpler to solve and analyze then the chance constrained programs. We discuss solving both problems using Monte-Carlo simulation techniques for the cases when the set of feasible solution is ﬁnite or inﬁnite bounded. The approach is applied to the ﬁnancial optimization problem with Value at Risk constraint, transaction costs and integer allocations. We compare the ability to generate a feasible solution of the original chance constrained problem using the sample approximations of the chance constraints directly or via sample approximation of the penaltyfunction objective.
2010-06-04T00:00:00ZA comparison of sample-based stochastic optimal control methodsGirardeau, Pierrehttp://edoc.hu-berlin.de/18452/90602020-03-07T04:14:39Z2010-06-04T00:00:00ZA comparison of sample-based stochastic optimal control methods
Girardeau, Pierre
http://dx.doi.org/10.18452/8408
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In this paper, we compare the performance of two scenario-based numerical methods to solve stochastic optimal control problems: scenario trees and particles. The problem consists in ﬁnding strategies to control a dynamicalsystem perturbed by exogenous noises so as to minimize some expected cost along a discrete and ﬁnite time horizon. We introduce the Mean SquaredError (MSE) which is the expected $L^2$-distance between the strategy given by the algorithm and the optimal strategy, as a performance indicator for the two models. We study the behaviour of the MSE with respect to the number of scenarios used for discretization. The ﬁrst model, widely studied in the Stochastic Programming community, consists in approximating the noise diffusion using a scenario tree representation. On a numerical example, we observe that the number of scenarios needed to obtain a given precision growsexponentially with the time horizon. In that sense, our conclusion on scenario trees is equivalent to the one in the work by Shapiro (2006) and has been widely noticed by practitioners. However, in the second part, we show using the same example that, by mixing Stochastic Programming and Dynamic Programmingideas, the particle method described by Carpentier et al. (2009) copes with this numerical difficulty: the number of scenarios needed to obtain a given precision now does not depend on the time horizon. Unfortunately, we alsoobserve that serious obstacles still arise from the system state space dimension.
2010-06-04T00:00:00Z