Stochastic Programming E-print Series (SPEPS)SPEPS 1999 - 2018http://edoc.hu-berlin.de/18452/1522024-03-19T10:40:11Z2024-03-19T10:40:11ZA randomized method for handling a difficult function in a convex optimization problem, motivated by probabilistic programmingFábián, Csaba I.Szántai, Tamáshttp://edoc.hu-berlin.de/18452/190842020-03-07T04:54:55Z2017-09-26T00:00:00ZA randomized method for handling a difficult function in a convex optimization problem, motivated by probabilistic programming
Fábián, Csaba I.; Szántai, Tamás
Mathematisch-Naturwissenschaftliche Fakultät
http://dx.doi.org/10.18452/18407
We propose a randomized gradient method for the handling of a convex function whose gradient computation is demanding. The method bears a resemblance to the stochastic approximation family. But in contrast to stochastic approximation, the present method builds a model problem. The approach requires that estimates of function values and gradients be provided at the iterates. We present a variance reduction Monte Carlo simulation procedure to provide such estimates in the case of certain probabilistic functions.
2017-09-26T00:00:00ZLearning Enabled Optimization: Towards a Fusion of Statistical Learning and Stochastic OptimizationSen, SuvrajeetDeng, Yunxiaohttp://edoc.hu-berlin.de/18452/187562023-10-31T04:07:41Z2017-07-31T00:00:00ZLearning Enabled Optimization: Towards a Fusion of Statistical Learning and Stochastic Optimization
Sen, Suvrajeet; Deng, Yunxiao
Mathematisch-Naturwissenschaftliche Fakultät
http://dx.doi.org/10.18452/18087
Several emerging applications, such as “Analytics of Things" and “Integrative Analytics" call for a fusion of statistical learning (SL) and stochastic optimization (SO). The Learning Enabled Optimization paradigm fuses concepts from these disciplines in a manner which not only enriches both SL and SO, but also provides a framework which supports rapid model updates and optimization, together with a methodology for rapid model-validation, assessment, and selection. Moreover, in many big data/big decisions applications these steps are repetitive, and possible only through a continuous cycle involving data analysis, optimization, and validation. This paper sets forth the foundation for such a framework by introducing several novel concepts such as statistical optimality, hypothesis tests for modeldelity, generalization error of stochastic optimization, and finally, a non-parametric methodology for model selection. These new concepts provide a formal framework for modeling, solving, validating, and reporting solutions for Learning Enabled Optimization (LEO). We illustrate the LEO framework by applying it to an inventory control model in which we use demand data available for ARIMA modeling in the statistical package \R". In addition, we also study a production-marketing coordination model based on combining a pedagogical production planning model with an advertising data set intended for sales prediction. Because the approach requires the solution of several stochastic programming instances, some using continuous random variables, we leverage stochastic decomposition (SD) for the fusion of regression and stochastic linear programming. In this sense, the novelty of this paper is its framework, rather than a specific new algorithm. Finally, we present an architecture of a software framework to bring about the fusion we envision.
2017-07-31T00:00:00ZQuantitative Stability Analysis for Minimax Distributionally Robust RiskOptimizationPichler, AloisXu, Huifuhttp://edoc.hu-berlin.de/18452/91072020-03-07T04:14:48Z2017-04-19T00:00:00ZQuantitative Stability Analysis for Minimax Distributionally Robust RiskOptimization
Pichler, Alois; Xu, Huifu
http://dx.doi.org/10.18452/8455
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This paper considers distributionally robust formulations of a two stage stochastic programmingproblem with the objective of minimizing a distortion risk of the minimal cost incurred at the secondstage.We carry out stability analysis by looking into variations of the ambiguity set under theWassersteinmetric, decision spaces at both stages and the support set of the random variables. In the case when itis risk neutral, the stability result is presented with the variation of the ambiguity set being measuredby generic metrics of ζ-structure, which provides a unified framework for quantitative stability analysisunder various metrics including total variation metric and Kantorovich metric. When the ambiguity set isstructured by a ζ-ball, we find that the Hausdorff distance between two ζ-balls is bounded by the distanceof their centres and difference of their radius. The findings allow us to strengthen some recent convergenceresults on distributionally robust optimization where the centre of the Wasserstein ball is constructed bythe empirical probability distribution.
2017-04-19T00:00:00ZOptimal scenario generation and reduction in stochastic programmingHenrion, RenéRömisch, Wernerhttp://edoc.hu-berlin.de/18452/91062024-02-28T10:21:23Z2017-04-19T00:00:00ZOptimal scenario generation and reduction in stochastic programming
Henrion, René; Römisch, Werner
http://dx.doi.org/10.18452/8454
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Scenarios are indispensable ingredients for the numerical solution of stochastic optimization problems. Earlier approaches for optimal scenario generation and reduction are based on stability arguments involving distances of probabilitymeasures. In this paper we review those ideas and suggest to make use of stability estimates based on distances containing minimal information, i.e., on data appearing in the optimization model only. For linear two-stage stochasticprograms we show that the optimal scenario generation problem can be reformulatedas best approximation problem for the expected recourse function and asgeneralized semi-infinite program, respectively. The latter model turns out to beconvex if either right-hand sides or costs are random. We also review the problemsof optimal scenario reduction for two-stage models and of optimal scenario generationfor chance constrained programs. Finally, we consider scenario generationand reduction for the classical newsvendor problem.
2017-04-19T00:00:00ZScenariao Reduction Revisited: Fundamental Limits and GuraranteesRujeerapaiboon, NapatSchindler, KilianKuhn, DanielWiesemann, Wolframhttp://edoc.hu-berlin.de/18452/91052020-03-07T04:14:48Z2017-02-21T00:00:00ZScenariao Reduction Revisited: Fundamental Limits and Gurarantees
Rujeerapaiboon, Napat; Schindler, Kilian; Kuhn, Daniel; Wiesemann, Wolfram
http://dx.doi.org/10.18452/8453
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
The goal of scenario reduction is to approximate a given discrete distributionwith another discrete distribution that has fewer atoms. We distinguishcontinuous scenario reduction, where the new atoms may be chosen freely, anddiscrete scenario reduction, where the new atoms must be chosen from among theexisting ones. Using the Wasserstein distance as measure of proximity between distributions,we identify those n-point distributions on the unit ball that are leastsusceptible to scenario reduction, i.e., that have maximum Wasserstein distanceto their closest m-point distributions for some prescribed m < n. We also providesharp bounds on the added benefit of continuous over discrete scenario reduction.Finally, to our best knowledge, we propose the first polynomial-time constant-factorapproximations for both discrete and continuous scenario reduction as wellas the first exact exponential-time algorithms for continuous scenario reduction.
2017-02-21T00:00:00ZUniformly monotone functions - defiitions, properties, characterizationsLachout, Petrhttp://edoc.hu-berlin.de/18452/91042020-03-07T04:14:48Z2016-09-05T00:00:00ZUniformly monotone functions - defiitions, properties, characterizations
Lachout, Petr
http://dx.doi.org/10.18452/8452
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Quasi-concave functions play an important role in economics and finance as utility functions, measures of risk or other objects used, mainly,in portfolio selection analysis. A special attention is paid to these functions in the minimax theory. Unfortunately, their limited application is due to the fact that supremum, sum, product of quasi-concave functions are typically not quasi-concave. This difficulty is overcome by establishing of uniformly quasi-concave functions, due to Prékopa, Yoda andSubasi (2011). We contribute with a new characterization of uniformlyquasi-concave functions that allows easier verfication and provide morestraightforward insight.
2016-09-05T00:00:00ZClustering 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:00ZQuasi-Monte Carlo methods for linear two-stage stochastic programming problemsLeövey, HernanRömisch, Wernerhttp://edoc.hu-berlin.de/18452/90962024-02-28T09:23:53Z2014-12-30T00:00:00ZQuasi-Monte Carlo methods for linear two-stage stochastic programming problems
Leövey, Hernan; Römisch, Werner
http://dx.doi.org/10.18452/8444
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Quasi-Monte Carlo algorithms are studied for generating scenarios to solve two-stage linear stochastic programming problems. Their integrands are piecewise linear-quadratic, but do not belong to the function spaces consideredfor QMC error analysis. We show that under some weak geometric condition on the two-stage model all terms of their ANOVA decomposition, except the one of highest order, are continuously differentiable and second order mixed derivativesexist almost everywhere and belong to $L_2$. This implies that randomly shifted latticerules may achieve the optimal rate of convergence $O(n^{-1+\delta})$ with $\delta \in (0,\frac{1}{2}]$ and a constant not depending on the dimension if the effective superposition dimension is less than or equal to two. The geometric condition is shown to be satisfied for almost all covariance matrices if the underlying probability distribution isnormal. We discuss effective dimensions and techniques for dimension reduction.Numerical experiments for a production planning model with normal inputs showthat indeed convergence rates close to the optimal rate are achieved when usingrandomly shifted lattice rules or scrambled Sobol' point sets accompanied withprincipal component analysis for dimension reduction.
2014-12-30T00:00:00ZDistribution shaping and scenario bundling for stochastic programs with endogenous uncertaintyLaumanns, MarcoPrestwich, StevenKawas, Banhttp://edoc.hu-berlin.de/18452/90952020-03-07T04:14:46Z2014-12-30T00:00:00ZDistribution shaping and scenario bundling for stochastic programs with endogenous uncertainty
Laumanns, Marco; Prestwich, Steven; Kawas, Ban
http://dx.doi.org/10.18452/8443
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Stochastic programs are usually formulated with probability distributions that are exogenously given. Modeling and solving problems withendogenous uncertainty, where decisions can influence the probabilities, has remained a largely unresolved challenge. In this paper we develop a new approach to handle decision-dependent probabilities based on the ideaof distribution shaping. It uses a sequence of distributions, successively conditioned on the influencing decision variables, and characterizes these by linear inequalities. We demonstrate the approach on a pre-disaster planning problem of finding optimal investments to strengthen links ina transportation network, given that the links are subject to stochastic failure. Our new approach solves a recently considered instance of the Istanbul highway network to optimality within seconds, for which only approximate solutions had been known so far.
2014-12-30T00:00:00ZDynamic Generation of Scenario TreesPflug, Georg Ch.Pichler, Aloishttp://edoc.hu-berlin.de/18452/90942020-03-07T04:14:46Z2014-10-16T00:00:00ZDynamic Generation of Scenario Trees
Pflug, Georg Ch.; Pichler, Alois
http://dx.doi.org/10.18452/8442
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We present new algorithms for the dynamic generation of scenario trees for multistagestochastic optimization. The different methods described are based on random vectors, whichare drawn from conditional distributions given the past and on sample trajectories.The structure of the tree is not determined beforehand, but dynamically adapted to meeta distance criterion, which insures the quality of the approximation. The criterion is built ontransportation theory, which is extended to stochastic processes.
2014-10-16T00:00:00ZOn Distributionally Robust Multiperiod Stochastic OptimizationAnalui, BitaPflug, Georg Ch.http://edoc.hu-berlin.de/18452/90932020-03-07T04:14:46Z2014-05-07T00:00:00ZOn Distributionally Robust Multiperiod Stochastic Optimization
Analui, Bita; Pflug, Georg Ch.
http://dx.doi.org/10.18452/8441
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This paper considers model uncertainty for multistage stochastic programs. The data and information structure of the baseline model is a tree, on which the decision problem is defined. We consider ambiguity neighborhoods around this tree as alternative models which are close to the baseline model. Closeness is defined in terms of a distance for probability trees, called the nested distance. This distance is appropriate for scenario models of multistage stochastic optimization problems as was demonstrated in (Pflug and Pichler, 2012). The ambiguity model is formulated as a minimax problem, where the optimal decision is to be found, which minimizes the maximal objective function, within the ambiguity set. We give a setup for studying saddle point properties of the minimax problem. Moreover, we present solution algorithms for finding the minimax decisions at least asymptotically. As an example, we consider a multiperiod stochastic production/inventory control problem with weekly ordering. The stochastic scenario process is given by the random demands for two products. We find the worst trees within the ambiguity set and determine a solution which is robust w.r.t. model uncertainty. It turns out that the probability weights of the worst case trees are concentrated on few very bad scenarios.
2014-05-07T00:00:00ZMitigating Uncertainty via Compromise Decisions in Two-stage Stochastic Linear ProgrammingSen, SuvrajeetLiu, Yifanhttp://edoc.hu-berlin.de/18452/90922020-03-07T04:14:45Z2014-04-16T00:00:00ZMitigating Uncertainty via Compromise Decisions in Two-stage Stochastic Linear Programming
Sen, Suvrajeet; Liu, Yifan
http://dx.doi.org/10.18452/8440
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Stochastic Programming (SP) has long been considered as a well-justified yet computationally challenging paradigm for practical applications. Computational studies in the literature often involve approximating a large number of scenarios by using a small number of scenarios to be processed via deterministic solvers, or running Sample Average Approximation on some genre of high performance machines so that statistically acceptable bounds can be obtained. In this paper we show that for a class of stochastic linear programming problems, an alternative approach known as Stochastic Decomposition (SD) can provide solutions of similar quality, in far less computational time using ordinary desktop or laptop machines of today. In addition to these compelling computational results, we also provide a stronger convergence result for SD, and introduce a new solution concept which we refer to as the compromise decision. This new concept is attractive for algorithms which call for multiple replications in sampling-based convex optimization algorithms. For such replicated optimization, we show that the difference between an average solution and a compromise decision provides a natural stopping rule. Finally our computational results cover a variety of instances from the literature, including a detailed study of SSN, a network planning instance which is known to be more challenging than other test instances in the literature.
2014-04-16T00:00:00ZMulti-Objective Probabilistically Constrained Programming with Variable Risk: New Models and ApplicationsLejeune, Miguel A.Shen, Siqianhttp://edoc.hu-berlin.de/18452/90912020-03-07T04:14:45Z2014-04-04T00:00:00ZMulti-Objective Probabilistically Constrained Programming with Variable Risk: New Models and Applications
Lejeune, Miguel A.; Shen, Siqian
http://dx.doi.org/10.18452/8439
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We consider a class of multi-objective probabilistically constrained problems MOPCP with a joint chance constraint, a multi-row random technology matrix, and a risk parameter (i.e., the reliability level) defined as a decision variable. We propose a Boolean modeling framework and derive a series of new equivalent mixed-integer programming formulations. We demonstrate the computational efficiency of the formulations that contain a small number of binary variables. We provide modeling insights pertaining to the most suitable reformulation, to the trade-off between the conflicting cost/revenue and reliability objectives, and to the scalarization parameter determining the relative importance of the objectives. Finally, we propose several MOPCP variants of multi-portfolio financial optimization models that implement a downside risk measure and can be used in a centralized or decentralized investment context. We study the impact of the model parameters on the portfolios, show, via a cross-validation study, the robustness of the proposed models, and perform a comparative analysis of the optimal investment decisions.
2014-04-04T00:00:00ZAncestral Benders' Cuts and Multi-term Disjunctions for Mixed-Integer Recourse Decisions in Stochastic ProgrammingQi, YunweiSen, Suvrajeethttp://edoc.hu-berlin.de/18452/90902020-03-07T04:14:45Z2013-09-17T00:00:00ZAncestral Benders' Cuts and Multi-term Disjunctions for Mixed-Integer Recourse Decisions in Stochastic Programming
Qi, Yunwei; Sen, Suvrajeet
http://dx.doi.org/10.18452/8438
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This paper focuses on solving two-stage stochastic mixed integer programs (SMIPs) with general mixed integer decision variables in both stages. We develop a decomposition algorithm in which the first stage approximation is solved using a branch-and-bound tree with nodes inheriting Benders' cuts that are valid for their ancestor nodes. In addition, we develop two closely related convexification schemes which use multi-term disjunctive cuts to obtain approximations of the second stagemixed-integer programs. We prove that the proposed methods are finitely convergent. One of the main advantages of our decomposition scheme is that we use a Benders-based branch-and-cut approach in which linear programming approximations are strengthened sequentially. Moreover as inmany decomposition schemes, these subproblems can be solved in parallel. We also illustrate thesealgorithms using several variants of an SMIP example from the literature, and present preliminary evidence of the scalability of these algorithms as the number of scenarios increases.
2013-09-17T00:00:00ZConditioning of linear-quadratic two-stage stochastic optimization problemsEmich, KonstantinHenrion, RenéRömisch, Wernerhttp://edoc.hu-berlin.de/18452/90892024-02-28T10:20:59Z2013-07-25T00:00:00ZConditioning of linear-quadratic two-stage stochastic optimization problems
Emich, Konstantin; Henrion, René; Römisch, Werner
http://dx.doi.org/10.18452/8437
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In this paper a condition number for linear-quadratic two-stage stochastic optimization problemsis introduced as the Lipschitz modulus of the multifunction assigning to a (discrete) probabilitydistribution the solution set of the problem. Being the outer norm of the Mordukhovich coderivativeof this multifunction, the condition number can be estimated from above explicitly in terms of theproblem data by applying appropriate calculus rules. Here, a chain rule for the extended partialsecond-order subdifferential recently proved by Mordukhovich and Rockafellar plays a crucial role.The obtained results are illustrated for the example of two-stage stochastic optimization problemswith simple recourse.
2013-07-25T00:00:00ZBidding in sequential electricity markets: The Nordic caseBoomsma, Trine KroghJuul, NinaFleten, Stein-Erikhttp://edoc.hu-berlin.de/18452/90882020-03-07T04:14:45Z2013-07-24T00:00:00ZBidding in sequential electricity markets: The Nordic case
Boomsma, Trine Krogh; Juul, Nina; Fleten, Stein-Erik
http://dx.doi.org/10.18452/8436
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
For electricity market participants trading in sequential markets with differences in price levels and riskexposure, coordinated bidding is highly relevant. We consider a Nordic power producer who engages inthe day-ahead spot market and the near real-time balancing market. In both markets, clearing prices anddispatched volumes are unknown at the time of bidding. However, in the balancing market, the agent facesan additional risk of not being dispatched. Taking into account the sequential clearing of these marketsand the gradual realization of market prices, we formulate the bidding problem as a multi-stage stochasticprogram. We investigate whether higher risk exposure can explain the hesitation, often observed in practice,to bid into the balancing market, even in cases of higher expected price levels. Furthermore, we quantify thegain from coordinated bidding, and by deriving bounds on this gain, assess the performance of alternativebidding strategies used in practice.
2013-07-24T00:00:00ZA mixed-integer stochastic nonlinear optimization problem with joint probabilistic constraintsArnold, T.Henrion, R.Möller, A.Vigerske, S.http://edoc.hu-berlin.de/18452/90872024-02-28T09:25:54Z2013-05-14T00:00:00ZA mixed-integer stochastic nonlinear optimization problem with joint probabilistic constraints
Arnold, T.; Henrion, R.; Möller, A.; Vigerske, S.
http://dx.doi.org/10.18452/8435
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We illustrate the solution of a mixed-integer stochastic nonlinear optimization problem in an application of power management. In this application, a coupled system consisting of a hydro power station and a wind farm is considered. The objective is to satisfy the local energy demand and sell any surplus energy on a spot market for a short time horizon. Generation of wind energy is assumed to be random, so that demand satisfaction is modeled by a joint probabilistic constraint taking into accountthe multivariate distribution. The turbine is forced to either operate between given positive limits or to be shut down. This introduces additional binary decisions. The numerical solution procedure is presented and results are illustrated.
2013-05-14T00:00:00ZElectricity Swing Option Pricing by Stochastic Bilevel Optimization: a Survey and New ApproachesKovacevic, Raimund M.Pflug, Georg Ch.http://edoc.hu-berlin.de/18452/90862020-03-07T04:14:44Z2013-05-13T00:00:00ZElectricity Swing Option Pricing by Stochastic Bilevel Optimization: a Survey and New Approaches
Kovacevic, Raimund M.; Pflug, Georg Ch.
http://dx.doi.org/10.18452/8434
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We demonstrate how the problem of determining the ask price for electricityswing options can be considered as a stochastic bilevel program with asymmetricinformation. Unlike as for financial options, there is no way for basingthe pricing method on no-arbitrage arguments. Two main situations are analyzed:if the seller has strong market power he/she might be able to maximizehis/her utility, while in fully competitive situations he/she will just look for aprice which makes profit and has acceptable risk. In both cases the seller hasto consider the decision problem of a potential buyer - the valuation problemof determining a fair value for a specific option contract - and anticipate thebuyer's optimal reaction to any proposed strike price. We also discuss somemethods for finding numerical solutions of stochastic bilevel problems witha special emphasis on using duality gap penalizations.
2013-05-13T00:00:00ZComputational aspects of risk-averse optimizationin two-stage stochastic modelsFábián, Csaba I.http://edoc.hu-berlin.de/18452/90852020-03-07T04:14:44Z2013-04-09T00:00:00ZComputational aspects of risk-averse optimizationin two-stage stochastic models
Fábián, Csaba I.
http://dx.doi.org/10.18452/8433
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Computational studies on two-stage stochastic programming problems indicate that aggregate models have better scale-up properties than disaggregate ones, though the threshold of breaking even may be high. In this paper we attempt to explain this phenomenon, and to lower this threshold.We present the on-demand accuracy approach of Oliveira and Sagastizábal in a form which shows that this approach, when applied to two-stage stochastic programming problems, combines the advantages of the disaggregate and the aggregate models.Moreover, we generalize the on-demand accuracy approach to constrained convex problems, and showhow to apply it to risk-averse two-stage stochastic programming problems.
2013-04-09T00:00:00Z