Volume 2001
http://edoc.hu-berlin.de/18452/358
2024-10-03T10:09:48ZMartingale pricing measures in incomplete markets via stochastic programming duality in the dual of L ∞
http://edoc.hu-berlin.de/18452/8916
Martingale pricing measures in incomplete markets via stochastic programming duality in the dual of L ∞
King, Alan J.; Korf, Lisa A.
Buch
http://dx.doi.org/10.18452/8264
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We propose a new framework for analyzing pricing theory for incomplete markets and contingent claims, using conjugate duality and optimization theory. Various statements in the literature of the fundamental theorem of asset pricing give conditions under which an essentially arbitrage-free market is equivalent to the existence of an equivalent martingale measure, and a formula for the fair price of a contingent claim as an expectation with respect to such a measure. In the setting of incomplete markets, the fair price is not attainable as such a particular expectation, but rather as a supremum over an infinite set of equivalent martingale measures. Here, we consider the problem as a stochastic program and derive pricing results for quite general discrete time processes. It is shown that in its most general form, the martingale pricing measure is attainable if it is permitted to be finitely additive. This setup also gives rise to a natural way of analyzing models with risk preferences, spreads and margin constraints, and other problem variants. We consider a discrete time, multi-stage, infinite probability space setting and derive the basic results of arbitrage pricing in this framework.
2001-11-13T00:00:00ZKing, Alan J.Korf, Lisa A.We propose a new framework for analyzing pricing theory for incomplete markets and contingent claims, using conjugate duality and optimization theory. Various statements in the literature of the fundamental theorem of asset pricing give conditions under which an essentially arbitrage-free market is equivalent to the existence of an equivalent martingale measure, and a formula for the fair price of a contingent claim as an expectation with respect to such a measure. In the setting of incomplete markets, the fair price is not attainable as such a particular expectation, but rather as a supremum over an infinite set of equivalent martingale measures. Here, we consider the problem as a stochastic program and derive pricing results for quite general discrete time processes. It is shown that in its most general form, the martingale pricing measure is attainable if it is permitted to be finitely additive. This setup also gives rise to a natural way of analyzing models with risk preferences, spreads and margin constraints, and other problem variants. We consider a discrete time, multi-stage, infinite probability space setting and derive the basic results of arbitrage pricing in this framework.Adapting an approximate level method to the two-stage stochastic programming problem
http://edoc.hu-berlin.de/18452/8915
Adapting an approximate level method to the two-stage stochastic programming problem
Fábián, Csaba I.
Buch
http://dx.doi.org/10.18452/8263
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We present a decomposition method for the solution of stwo-stage stochastic programming problems. This is an approximate method that can handle problems with large number scenarios. At the beginning, only rough approximation of the objective function is required. As the optimum is gradually approached, more and more accurate data are computed. The required accuracy is known at each step, hence efforts can be coordinated. The present framwork enables the application of interior-point methods because the convergence proof does not rely on basic solutions. Moreover, the classic discretization methods and stochastic approximation schemes naturally fit into the present framework.
2001-11-05T00:00:00ZFábián, Csaba I.We present a decomposition method for the solution of stwo-stage stochastic programming problems. This is an approximate method that can handle problems with large number scenarios. At the beginning, only rough approximation of the objective function is required. As the optimum is gradually approached, more and more accurate data are computed. The required accuracy is known at each step, hence efforts can be coordinated. The present framwork enables the application of interior-point methods because the convergence proof does not rely on basic solutions. Moreover, the classic discretization methods and stochastic approximation schemes naturally fit into the present framework.Risk measures for income streams
http://edoc.hu-berlin.de/18452/8914
Risk measures for income streams
Pflug, Georg Ch.; Ruszczynski, Andrzej
Buch
http://dx.doi.org/10.18452/8262
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
A new measure of risk is introduced for a sequence of random incomes adapted to some filtration. This measure is formulated as the optimal net present value of a stream of adaptively planned commitments for consumption. The calculation of the new measure is done by solving a stochastic dynamic linear optimization problem, which, in case of a finite filtration, reduces to a simple deterministic linear program. We show properties of the new measure by exploiting the convexity and duality structure of the stochastic dynamic linear problem. The measure depends on the full distribution of the income process (not only on its marginal distribution) as well as on the filtration, which is interpreted as the available information about the future.
2001-10-04T00:00:00ZPflug, Georg Ch.Ruszczynski, AndrzejA new measure of risk is introduced for a sequence of random incomes adapted to some filtration. This measure is formulated as the optimal net present value of a stream of adaptively planned commitments for consumption. The calculation of the new measure is done by solving a stochastic dynamic linear optimization problem, which, in case of a finite filtration, reduces to a simple deterministic linear program. We show properties of the new measure by exploiting the convexity and duality structure of the stochastic dynamic linear problem. The measure depends on the full distribution of the income process (not only on its marginal distribution) as well as on the filtration, which is interpreted as the available information about the future.Tree-sparse convex programs
http://edoc.hu-berlin.de/18452/8913
Tree-sparse convex programs
Steinbach, Marc
Buch
http://dx.doi.org/10.18452/8261
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Dynamic stochastic programs are prototypical for optimization problems with an inherent tree structure including characteristic sparsity patterns in the KKT systems of interior methods. We propose an integrated modeling and solution approach for such tree-sparse programs. Three closely related natural formulations are theoretically analyzed from a control-theoretic perspective and compared to each other. Associated KKT system solution algorithms with linear complexity are developed and comparisons to other interior approaches and related problem formulations are discussed.
2001-09-23T00:00:00ZSteinbach, MarcDynamic stochastic programs are prototypical for optimization problems with an inherent tree structure including characteristic sparsity patterns in the KKT systems of interior methods. We propose an integrated modeling and solution approach for such tree-sparse programs. Three closely related natural formulations are theoretically analyzed from a control-theoretic perspective and compared to each other. Associated KKT system solution algorithms with linear complexity are developed and comparisons to other interior approaches and related problem formulations are discussed.Stochastic programming duality
http://edoc.hu-berlin.de/18452/8912
Stochastic programming duality
Korf, Lisa A.
Buch
http://dx.doi.org/10.18452/8260
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
A new duality theory is developed for a class of stochastic programs in which the probability distribution is not necessarily discrete. This provides a new framework for problems which are not necessarily bounded, are not required to have relatively complete recourse, and do not satisfy the typical Slater condition of strict feasibility. These problems instead satisfy a different constraint qualification called "direction-free feasibility" to deal with possibly unbounded constaint sets, and "calmness" of a certain finite-dimensional value function to serve as a weaker condition than strict feasibility to obtain the existence of dual mulitpliers. In this way, strong duality results are established in which the dual variables are finite-dimensional, despite the possible intinite-dimensional character of the second-stage constraints. From this, infinite-dimensional dual problems are obtained in the space of essentially bounded functions. It is then shown how this framework could be used to ontain duality result in the setting of mathematical finance.
2001-07-26T00:00:00ZKorf, Lisa A.A new duality theory is developed for a class of stochastic programs in which the probability distribution is not necessarily discrete. This provides a new framework for problems which are not necessarily bounded, are not required to have relatively complete recourse, and do not satisfy the typical Slater condition of strict feasibility. These problems instead satisfy a different constraint qualification called "direction-free feasibility" to deal with possibly unbounded constaint sets, and "calmness" of a certain finite-dimensional value function to serve as a weaker condition than strict feasibility to obtain the existence of dual mulitpliers. In this way, strong duality results are established in which the dual variables are finite-dimensional, despite the possible intinite-dimensional character of the second-stage constraints. From this, infinite-dimensional dual problems are obtained in the space of essentially bounded functions. It is then shown how this framework could be used to ontain duality result in the setting of mathematical finance.Applying the minimum risk criterion in stochastic recourse programs
http://edoc.hu-berlin.de/18452/8911
Applying the minimum risk criterion in stochastic recourse programs
Riis, Morten; Schultz, Rüdiger
Buch
http://dx.doi.org/10.18452/8259
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In the setting of stochastic recourse programs, we consider the problem of minimizing the probability of total costs exceeding a certain threshold value. The problem is referred to as the minimum risk problem and is posed in order to obtain a more adequate description of risk aversion than that of the accustomed expected value problem. We establish continuity properties of the recourse function as a function of the first-stage decision, as well as of the underlying probability distribution or random parameters. This leads to stability results for the optimal solution of the minimum risk problem when the underlying probability distribution is subjected to perturbations. Furthermore, an algorithm for the minimum risk problem is elaborated and we present results of some preliminary computational experiments.
2001-06-26T00:00:00ZRiis, MortenSchultz, RüdigerIn the setting of stochastic recourse programs, we consider the problem of minimizing the probability of total costs exceeding a certain threshold value. The problem is referred to as the minimum risk problem and is posed in order to obtain a more adequate description of risk aversion than that of the accustomed expected value problem. We establish continuity properties of the recourse function as a function of the first-stage decision, as well as of the underlying probability distribution or random parameters. This leads to stability results for the optimal solution of the minimum risk problem when the underlying probability distribution is subjected to perturbations. Furthermore, an algorithm for the minimum risk problem is elaborated and we present results of some preliminary computational experiments.Modeling farmers' response to uncertain rainfall in Burkina Faso
http://edoc.hu-berlin.de/18452/8910
Modeling farmers' response to uncertain rainfall in Burkina Faso
Maatman, Arno; Schweigman, Caspar; Ruijs, Arjan; Vlerk, Maarten H. van der
Buch
http://dx.doi.org/10.18452/8258
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Farmers on the Central Plateau of Burkina Faso in West Africa cultivate under precarious con-ditions. Rainfall variability is extremely high in this area, and accounts for much of the uncertainty surrounding the farmers? decision-making process. Strategies to cope with these risk are typically dynamic. Sequential decision making is one of the most important ways to cope with risk due to uncertain rainfall. In this paper, a stochastic programming model is presented to describe farmers? sequential decisions in reaction to rainfall. The model describes farmers? strategies of production, consumption, selling, purchasing and storage from the start of the growing season until one year after the harvest period. This dynamic model better describes farmers? strategies than static mod-els that are usually applied. This study draws important policy conclusions regarding reorientation of research programs and illustrates how operations research techniques can be usefully applied to study grass root problems in developing countries.
2001-06-06T00:00:00ZMaatman, ArnoSchweigman, CasparRuijs, ArjanVlerk, Maarten H. van derFarmers on the Central Plateau of Burkina Faso in West Africa cultivate under precarious con-ditions. Rainfall variability is extremely high in this area, and accounts for much of the uncertainty surrounding the farmers? decision-making process. Strategies to cope with these risk are typically dynamic. Sequential decision making is one of the most important ways to cope with risk due to uncertain rainfall. In this paper, a stochastic programming model is presented to describe farmers? sequential decisions in reaction to rainfall. The model describes farmers? strategies of production, consumption, selling, purchasing and storage from the start of the growing season until one year after the harvest period. This dynamic model better describes farmers? strategies than static mod-els that are usually applied. This study draws important policy conclusions regarding reorientation of research programs and illustrates how operations research techniques can be usefully applied to study grass root problems in developing countries.Decomposition algorithms for stochastic programming on a computational grid
http://edoc.hu-berlin.de/18452/8909
Decomposition algorithms for stochastic programming on a computational grid
Linderoth, Jeff; Wright, Stephen
Buch
http://dx.doi.org/10.18452/8257
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We describe algorithms for two-stage stochastic linear programming with recourse and their implementation on a grid computing platform. In particular, we examine serial and asynchronous versions of the L-shaped method and a trust-region method. The parallel platform of choice is the dynamic, heterogeneous, opportunistic platform provided by the Condor system. The algorithms are of master-worker type (with the workers being used to solve second-stage problems), and the MW runtime support library (which supports master- worker computations) is key to the implementation. Computational results are presented on large sample average approximations of problems from the literature.
2001-05-26T00:00:00ZLinderoth, JeffWright, StephenWe describe algorithms for two-stage stochastic linear programming with recourse and their implementation on a grid computing platform. In particular, we examine serial and asynchronous versions of the L-shaped method and a trust-region method. The parallel platform of choice is the dynamic, heterogeneous, opportunistic platform provided by the Condor system. The algorithms are of master-worker type (with the workers being used to solve second-stage problems), and the MW runtime support library (which supports master- worker computations) is key to the implementation. Computational results are presented on large sample average approximations of problems from the literature.A multi-stage stochastic integer programming approach for capacity expansion under uncertainty
http://edoc.hu-berlin.de/18452/8908
A multi-stage stochastic integer programming approach for capacity expansion under uncertainty
Ahmed, Shabbir; King, Alan J.; Parija, Gyana
Buch
http://dx.doi.org/10.18452/8256
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This paper addresses a multi-period investment model for capacity expansion in an uncertain environment. Using a scenario tree approach to model the evolution of uncertain demand and cost parameters, and fixed-charge cost functions to model the economies of scale in expansion costs, we develop a multi-stage stochastic integer programming formulation for the problem. A reformulation of the problem is proposed using variable disaggregation to exploit the lot-sizing substructure of the problem. The reformulation significantly reduces the LP relaxation gap of this large scale integer program. A heuristic scheme is presented to perturb the LP relaxation solutions to produce good quality integer solutions. Finally, we outline a branch and bound algorithm that makes use of the reformulation strategy as a lower bounding scheme, and the heuristic as an upper bounding scheme, to solve the problem to global optimality. Our preliminary computational results indicate that the proposed strategy has significant advantages over straightforward use of commercial solvers.
2001-04-20T00:00:00ZAhmed, ShabbirKing, Alan J.Parija, GyanaThis paper addresses a multi-period investment model for capacity expansion in an uncertain environment. Using a scenario tree approach to model the evolution of uncertain demand and cost parameters, and fixed-charge cost functions to model the economies of scale in expansion costs, we develop a multi-stage stochastic integer programming formulation for the problem. A reformulation of the problem is proposed using variable disaggregation to exploit the lot-sizing substructure of the problem. The reformulation significantly reduces the LP relaxation gap of this large scale integer program. A heuristic scheme is presented to perturb the LP relaxation solutions to produce good quality integer solutions. Finally, we outline a branch and bound algorithm that makes use of the reformulation strategy as a lower bounding scheme, and the heuristic as an upper bounding scheme, to solve the problem to global optimality. Our preliminary computational results indicate that the proposed strategy has significant advantages over straightforward use of commercial solvers.Second-order lower bounds on the expectation of a convex function
http://edoc.hu-berlin.de/18452/8907
Second-order lower bounds on the expectation of a convex function
Dokov, Steftcho P.; Morton, David P.
Buch
http://dx.doi.org/10.18452/8255
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We develop a class of lower bounds on the expectation of a convex function. The bounds utilize the first two moments of the underlying random variable, whose support is contained in a bounded interval or hyper-rectangle. Our bounds have applications to stochastic programs whose random parameters are known only through limited moment information. Computational results are presented for two-stage stochastic linear programs.
2001-04-16T00:00:00ZDokov, Steftcho P.Morton, David P.We develop a class of lower bounds on the expectation of a convex function. The bounds utilize the first two moments of the underlying random variable, whose support is contained in a bounded interval or hyper-rectangle. Our bounds have applications to stochastic programs whose random parameters are known only through limited moment information. Computational results are presented for two-stage stochastic linear programs.Multistage stochastic integer programs
http://edoc.hu-berlin.de/18452/8906
Multistage stochastic integer programs
Römisch, Werner; Schultz, Rüdiger
Buch
http://dx.doi.org/10.18452/8254
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We consider linear mulitstage stochastic integer programs and study their functional and dynamic programming formulations as well as conditions for optimality and stability of solutions. Furthermore, we study the application of the Rockafellar-Wets dualization approach as well as the structure and algorithmic potential of corresponding dual problems. For discrete underlying probability distributions we discuss possible large scale mixed-integer linear programming formulations and three dual decomposition approaches, namely, scenario, component and nodal decomposition.
2001-04-04T00:00:00ZRömisch, WernerSchultz, RüdigerWe consider linear mulitstage stochastic integer programs and study their functional and dynamic programming formulations as well as conditions for optimality and stability of solutions. Furthermore, we study the application of the Rockafellar-Wets dualization approach as well as the structure and algorithmic potential of corresponding dual problems. For discrete underlying probability distributions we discuss possible large scale mixed-integer linear programming formulations and three dual decomposition approaches, namely, scenario, component and nodal decomposition.Dual stochastic dominance and related mean-risk models
http://edoc.hu-berlin.de/18452/8905
Dual stochastic dominance and related mean-risk models
Ogryczak, Wlodzimierz; Ruszczynski, Andrzej
Buch
http://dx.doi.org/10.18452/8253
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We consider the problem of constructing mean-risk models which are consistent with the second degree stochastic dominance relation. By exploiting duality relations of convex analysis we develop the quantile model of stochastic dominance for general distributions. This allows us to show that several models using quantiles and tail characteristics of the distribution are in harmony with the stochastic dominance relation. We also provide stochastic linear programming formulations of these models.
2001-03-24T00:00:00ZOgryczak, WlodzimierzRuszczynski, AndrzejWe consider the problem of constructing mean-risk models which are consistent with the second degree stochastic dominance relation. By exploiting duality relations of convex analysis we develop the quantile model of stochastic dominance for general distributions. This allows us to show that several models using quantiles and tail characteristics of the distribution are in harmony with the stochastic dominance relation. We also provide stochastic linear programming formulations of these models.Decomposition of test sets in stochastic integer programming
http://edoc.hu-berlin.de/18452/8904
Decomposition of test sets in stochastic integer programming
Hemmecke, Raymond; Schultz, Rüdiger
Buch
http://dx.doi.org/10.18452/8252
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Graver test sets for linear two-stage stochastic integer programs are studied. It is shown that test sets can be decomposed into finitely many building blocks whose number is independent of the number of scenarios of the sochastic program. A finite algorithm to compute the building blocks directly, without prior knowledge of test set vectors, is presented. Once computed, building blocks can be employed to solve the stochastic program by a simple augmentation scheme, again without explicit knowledge of test set vectors. Preliminary computational experience is reported.
2001-01-30T00:00:00ZHemmecke, RaymondSchultz, RüdigerGraver test sets for linear two-stage stochastic integer programs are studied. It is shown that test sets can be decomposed into finitely many building blocks whose number is independent of the number of scenarios of the sochastic program. A finite algorithm to compute the building blocks directly, without prior knowledge of test set vectors, is presented. Once computed, building blocks can be employed to solve the stochastic program by a simple augmentation scheme, again without explicit knowledge of test set vectors. Preliminary computational experience is reported.