Volume 2010
Permanent URI for this collectionhttp://edoc.hu-berlin.de/18452/367
Browse
Recent Submissions
Publication 2010-11-29BuchA computational study of a solver system forprocessing two-stage stochastic linearprogramming problemsZverovich, Victor; Fábián, C.; Ellison, Francis; Mitra, Gautam; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetPublication 2010-11-19BuchConstruction of Risk-Averse Enhanced Index FundsLejeune, Miguel; Samatli-Pac, Gülay; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetWe 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.Publication 2010-10-20BuchSampling-based decomposition methods for risk-averse multistage programsGuigues, Vincent; Römisch, Werner; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetWe 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.Publication 2010-10-19BuchOn joint probabilistic constraints with Gaussian coefficient matrixAckooij, W. Van; Henrion, R.; Möller, A.; Zorgati, R.; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetThe 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.Publication 2010-08-25BuchPattern-Based Modeling and Solution of Probabilistically Constrained Optimization ProblemsLejeune, Miguel A.; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetWe 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.Publication 2010-08-25BuchConvex duality in stochastic programming and mathematical financePennanen, Teemu; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetThis 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 filtration. The framework unifies many well-known duality frameworks from operations research and mathematical finance. The unification allows the extension of some useful techniquesfrom these two fields to a much wider class of problems. In particular, combining certain finite-dimensional techniques from convex analysis with measure theoretic techniques from mathematical finance, we are able to close the duality gap in some situations where traditional topological arguments fail.Publication 2010-05-25BuchStability and sensitivity analysis of stochastic programs with second order dominance constraintsLiu, Yongchao; Xu, Huifu; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetIn 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-infinite programmingdue to Gugat [13], we show under the Slater constraint qualification 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.Publication 2010-06-04BuchReformulation of general chance constrained problems using the penalty functionsBranda, Martin; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetWe 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 fixed 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 finite or infinite bounded. The approach is applied to the financial 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.Publication 2010-06-04BuchA comparison of sample-based stochastic optimal control methodsGirardeau, Pierre; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetIn 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 finding strategies to control a dynamicalsystem perturbed by exogenous noises so as to minimize some expected cost along a discrete and finite 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 first 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.