Scenario tree generation and multi-asset financial optimization problems

We compare two popular scenario tree generation methods in the context of financial optimization: moment matching and scenario reduction. Using a simple problem with a known analytic solution, moment matching–when ensuring absence of arbitrage–replicates this solution precisely. On the other hand, even if the scenario trees generated by scenario reduction are arbitrage-free, the solutions are biased and highly variable. These results hold for correlated and uncorrelated asset returns, as well as for normal and non-normal returns.     

Practical arbitrage‐free scenario tree reduction methods and their applications in financial optimization

We construct an arbitrage‐free scenario tree reduction model, from which some arbitrage‐free scenario tree reduction algorithms are designed. They ensure that the reduced scenario trees are arbitrage free. Numerical results show the practicality and efficiency of the proposed algorithms. Results for multistage portfolio selection problems demonstrate the necessity and importance for guaranteeing that the reduced scenario trees are arbitrage free, as well as the practicality of the proposed arbitrage‐free scenario tree reduction algorithms for financial optimization.     

Mixed-integer second-order cone programming for lower hedging of American contingent claims in incomplete markets

We describe a challenging class of large mixed-integer second-order cone programming models which arise in computing the maximum price that a buyer is willing to disburse to acquire an American contingent claim in an incomplete financial market with no arbitrage opportunity. Taking the viewpoint of an investor who is willing to allow a controlled amount of risk by replacing the classical no-arbitrage assumption with a “no good-deal assumption” defined using an arbitrage-adjusted Sharpe ratio criterion we formulate the problem of computing the pricing and hedging of an American option in a financial market described by a multi-period, discrete-time, finite-state scenario tree as a large-scale mixed-integer conic optimization problem. We report computational results with off-the-shelf mixed-integer conic optimization software.     

Adaptive discretization of convex multistage stochastic programs

We propose a new scenario tree reduction algorithm for multistage stochastic programs, which integrates the reduction of a scenario tree into the solution process of the stochastic program. This allows to construct a scenario tree that is highly adapted on the optimization problem. The algorithm starts with a rough approximation of the original tree and locally refines this approximation as long as necessary. Promising numerical results for scenario tree reductions in the settings of portfolio management and power management with uncertain load are presented.     

Term Structure Models in Multistage Stochastic Programming: Estimation and Approximation

This paper investigates some common interest rate models for scenario generation in financial applications of stochastic optimization. We discuss conditions for the underlying distributions of state variables which preserve convexity of value functions in a multistage stochastic program. One- and multi-factor term structure models are estimated based on historical data for the Swiss Franc. An analysis of the dynamic behavior of interest rates generated with these models reveals several deficiencies which have an impact on the performance of investment policies derived from the stochastic program. While barycentric approximation is used here for the generation of scenario trees, these insights may be generalized to other discretization techniques as well.     

Multistage stochastic demand-side management for price-making major consumers of electricity in a co-optimized energy and reserve market

In this paper, we take an optimization-driven heuristic approach, motivated by dynamic programming, to solve a class of non-convex multistage stochastic optimization problems. We apply this to the problem of optimizing the timing of energy consumption for a large manufacturer who is a price-making major consumer of electricity. We introduce a mixed-integer program that co-optimizes consumption bids and interruptible load reserve offers, for such a major consumer over a finite time horizon. By utilizing Lagrangian methods, we decompose our model through approximately pricing the constraints that link the stages together. We construct look-up tables in the form of consumption-utility curves, and use these to determine optimal consumption levels. We also present heuristics, in order to tackle the non-convexities within our model, and improve the accuracy of our policies. In the second part of the paper, we present stochastic solution methods for our model in which, we reduce the size of the scenario tree by utilizing a tailor-made scenario clustering method. Furthermore, we report on a case study that implements our models for a major consumer in the (full) New Zealand Electricity Market and present numerical results.     

Particle methods for stochastic optimal control problems

When dealing with numerical solution of stochastic optimal control problems, stochastic dynamic programming is the natural framework. In order to try to overcome the so-called curse of dimensionality, the stochastic programming school promoted another approach based on scenario trees which can be seen as the combination of Monte Carlo sampling ideas on the one hand, and of a heuristic technique to handle causality (or nonanticipativeness) constraints on the other hand. However, if one considers that the solution of a stochastic optimal control problem is a feedback law which relates control to state variables, the numerical resolution of the optimization problem over a scenario tree should be completed by a feedback synthesis stage in which, at each time step of the scenario tree, control values at nodes are plotted against corresponding state values to provide a first discrete shape of this feedback law from which a continuous function can be finally inferred. From this point of view, the scenario tree approach faces an important difficulty: at the first time stages (close to the tree root), there are a few nodes (or Monte-Carlo particles), and therefore a relatively scarce amount of information to guess a feedback law, but this information is generally of a good quality (that is, viewed as a set of control value estimates for some particular state values, it has a small variance because the future of those nodes is rich enough); on the contrary, at the final time stages (near the tree leaves), the number of nodes increases but the variance gets large because the future of each node gets poor (and sometimes even deterministic). After this dilemma has been confirmed by numerical experiments, we have tried to derive new variational approaches. First of all, two different formulations of the essential constraint of nonanticipativeness are considered: one is called algebraic and the other one is called functional. Next, in both settings, we obtain optimality conditions for the corresponding optimal control problem. For the numerical resolution of those optimality conditions, an adaptive mesh discretization method is used in the state space in order to provide information for feedback synthesis. This mesh is naturally derived from a bunch of sample noise trajectories which need not to be put into the form of a tree prior to numerical resolution. In particular, an important consequence of this discrepancy with the scenario tree approach is that the same number of nodes (or points) are available from the beginning to the end of the time horizon. And this will be obtained without sacrifying the quality of the results (that is, the variance of the estimates). Results of experiments with a hydro-electric dam production management problem will be presented and will demonstrate the claimed improvements. A more realistic problem will also be presented in order to demonstrate the effectiveness of the method for high dimensional problems.     

Cost/risk balanced management of scarce resources using stochastic programming

We consider the situation when a scarce renewable resource should be periodically distributed between different users by a Resource Management Authority (RMA). The replenishment of this resource as well as users demand is subject to considerable uncertainty. We develop cost optimization and risk management models that can assist the RMA in its decision about striking the balance between the level of target delivery to the users and the level of risk that this delivery will not be met. These models are based on utilization and further development of the general methodology of stochastic programming for scenario optimization, taking into account appropriate risk management approaches. By a scenario optimization model we obtain a target barycentric value with respect to selected decision variables. A successive reoptimization of deterministic model for the worst case scenarios allows the reduction of the risk of negative consequences derived from unmet resources demand. Our reference case study is the distribution of scarce water resources. We show results of some numerical experiments in real physical systems.     

Scenario tree generation approaches using K-means and LP moment matching methods

We consider in this paper the efficient ways to generate multi-stage scenario trees. A general modified K-means clustering method is first presented to generate the scenario tree with a general structure. This method takes the time dependency of the simulated path into account. Based on the traditional and modified K-means analyses, the moment matching of multi-stage scenario trees is described as a linear programming (LP) problem. By simultaneously utilizing simulation, clustering, non-linear time series and moment matching skills, a sequential generation method and another new hybrid approach which can generate the whole multi-stage tree right off are proposed. The advantages of these new methods are: the vector autoregressive and multivariate generalized autoregressive conditional heteroscedasticity (VAR-MGARCH) model is adopted to properly reflect the inter-stage dependency and the time-varying volatilities of the data process, the LP-based moment matching technique ensures that the scenario tree generation problem can be solved more efficiently and the tree scale can be further controlled, and in the meanwhile, the statistical properties of the random data process are maintained properly. What is more important, our new LP methods can guarantee at least two branches are derived from each non-leaf node and thus overcome the drawback in relevant papers. We carry out a series of numerical experiments and apply the scenario tree generation methods to a portfolio management problem, which demonstrate the practicality, efficiency and advantages of our new approaches over other models or methods.     

Knowledge‐based scenario tree generation methods and application in multiperiod portfolio selection problem

A scenario tree is an efficient way to represent a stochastic data process in decision problems under uncertainty. This paper addresses how to efficiently generate appropriate scenario trees. A knowledge‐based scenario tree generation method is proposed; the new method is further improved by accounting for subjective judgements or expectations about the random future. Compared with existing approaches, complicated mathematical models and time‐consuming estimation, simulation and optimization problem solution are avoided in our knowledge‐based algorithms, and large‐scale scenario trees can be quickly generated. To show the advantages of the new algorithms, a multiperiod portfolio selection problem is considered, and a dynamic risk measure is adopted to control the intermediate risk, which is superior to the single‐period risk measure used in the existing literature. A series of numerical experiments are carried out by using real trading data from the Shanghai stock market. The results show that the scenarios generated by our algorithms can properly represent the underlying distribution; our algorithms have high performance, say, a scenario tree with up to 10,000 scenarios can be generated in less than a half minute. The applications in the multiperiod portfolio management problem demonstrate that our scenario tree generation methods are stable, and the optimal trading strategies obtained with the generated scenario tree are reasonable, efficient and robust. Copyright © 2013 John Wiley & Sons, Ltd.     

Scenario tree generation for multiperiod financial optimization by optimal discretization

Multiperiod financial optimization is usually based on a stochastic model for the possible market situations. There is a rich literature about modeling and estimation of continuous-state financial processes, but little attention has been paid how to approximate such a process by a discrete-state scenario process and how to measure the pertaining approximation error.?In this paper we show how a scenario tree may be constructed in an optimal manner on the basis of a simulation model of the underlying financial process by using a stochastic approximation technique. Consistency relations for the tree may also be taken into account. Received: December 15, 1998 / Accepted: October 1, 2000?Published online December 15, 2000     

Efficient Reduced Order State Space Model Computation for a Class of Second Order Index One Systems

Simulation, design optimization and controller design of modern machine tools heavily rely on adequat numerical models. In order to achieve results in shorter computation times, reduced order models (ROMs) are applied in either of these tasks. Most modern simulation tools expect these ROMs to come in standard state space form. Structural models of the machine tool are however of second order type. In case piezo actuators are used in the device they are even differential algebraic equations (DAEs) of index one due to the coupling to the equations describing the electric potentials. This contribution is dedicated especially to those systems. We combine the ideas for balanced truncation model order reduction of large and sparse index 1 DAEs with methods developed for the efficient numerical handling of second order systems. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Asymptotic arbitrage in large financial markets with friction

In the modern version of arbitrage pricing theory suggested by Kabanov and Kramkov the fundamental financially meaningful concept is an asymptotic arbitrage. The ??real world?? large market is represented by a sequence of ??models?? and, though each of them is arbitrage free, investors may obtain non-risky profits in the limit. Mathematically, absence of the asymptotic arbitrage is expressed as contiguity of envelopes of the sets of equivalent martingale measures and objective probabilities. The classical theory deals with frictionless markets. In the present paper we extend it to markets with transaction costs. Assuming that each model admits consistent price systems, we relate them with families of probability measures and consider their upper and lower envelopes. The main result concerns the necessary and sufficient conditions for absence of asymptotic arbitrage opportunities of the first and second kinds expressed in terms of contiguity. We provide also more specific conditions involving Hellinger processes and give applications to particular models of large financial markets.     

Scenario tree reduction for multistage stochastic programs

A framework for the reduction of scenario trees as inputs of (linear) multistage stochastic programs is provided such that optimal values and approximate solution sets remain close to each other. The argument is based on upper bounds of the L _r -distance and the filtration distance, and on quantitative stability results for multistage stochastic programs. The important difference from scenario reduction in two-stage models consists in incorporating the filtration distance. An algorithm is presented for selecting and removing nodes of a scenario tree such that a prescribed error tolerance is met. Some numerical experience is reported.     

Financial scenario generation for stochastic multi-stage decision processes as facility location problems

The quality of multi-stage stochastic optimization models as they appear in asset liability management, energy planning, transportation, supply chain management, and other applications depends heavily on the quality of the underlying scenario model, describing the uncertain processes influencing the profit/cost function, such as asset prices and liabilities, the energy demand process, demand for transportation, and the like. A common approach to generate scenarios is based on estimating an unknown distribution and matching its moments with moments of a discrete scenario model. This paper demonstrates that the problem of finding valuable scenario approximations can be viewed as the problem of optimally approximating a given distribution with some distance function. We show that for Lipschitz continuous cost/profit functions it is best to employ the Wasserstein distance. The resulting optimization problem can be viewed as a multi-dimensional facility location problem, for which at least good heuristic algorithms exist. For multi-stage problems, a scenario tree is constructed as a nested facility location problem. Numerical convergence results for financial mean-risk portfolio selection conclude the paper.     

Correlation stress testing for value-at-risk: an unconstrained convex optimization approach

Correlation stress testing is employed in several financial models for determining the value-at-risk (VaR) of a financial institution’s portfolio. The possible lack of mathematical consistence in the target correlation matrix, which must be positive semidefinite, often causes breakdown of these models. The target matrix is obtained by fixing some of the correlations (often contained in blocks of submatrices) in the current correlation matrix while stressing the remaining to a certain level to reflect various stressing scenarios. The combination of fixing and stressing effects often leads to mathematical inconsistence of the target matrix. It is then naturally to find the nearest correlation matrix to the target matrix with the fixed correlations unaltered. However, the number of fixed correlations could be potentially very large, posing a computational challenge to existing methods. In this paper, we propose an unconstrained convex optimization approach by solving one or a sequence of continuously differentiable (but not twice continuously differentiable) convex optimization problems, depending on different stress patterns. This research fully takes advantage of the recently developed theory of strongly semismooth matrix valued functions, which makes fast convergent numerical methods applicable to the underlying unconstrained optimization problem. Promising numerical results on practical data (RiskMetrics database) and randomly generated problems of larger sizes are reported.     

Arbitrage theory for non convex financial market models

We propose a unified approach where a security market is described by a liquidation value process. This allows to extend the frictionless models of the classical theory as well as the recent proportional transaction costs models to a larger class of financial markets with transaction costs including non proportional trading costs. The usual tools from convex analysis however become inadequate to characterize the absence of arbitrage opportunities in non-convex financial market models. The natural question is to which extent the results of the classical arbitrage theory are still valid. Our contribution is a first attempt to characterize the absence of arbitrage opportunities in non convex financial market models.     

Stochastic measures of arbitrage

Empirical research has provided evidence supporting the existence of arbitrage opportunities in real financial markets although market imperfections are often the main reason to explain these empirical deviations. Consequently, recent literature has turned the attention to imperfect markets in order to extend the most significant results on asset pricing. This paper develops several stochastic measures providing relative arbitrage earnings available in a financial market. The measures allow us to take into account different type of frictions. They are introduced by means of several dual pairs of vector optimization problems. Primal problems permit us to characterize the arbitrage absence even in an imperfect market and they also provide optimal arbitrage portfolios if the arbitrage absence fails. Dual ones allow us to extend the risk-neutral valuation methodology for imperfect and noarbitrage free markets and provide new interpretations for the measures in terms of “frictions effect” or “committed errors” in the valuation process. Partially funded by Comunidad Autónoma de Madrid (ref: CAM 07T/0027/2000) and Spanish Ministry of Science and Technology (ref: BEC2000-1388-C04)     

The stochastic bottleneck linear programming problem

In this paper we consider some stochastic bottleneck linear programming problems. We overview the solution methods in the literature. In the case when the coefficients of the objective functions are simple randomized, the minimum-risk approach will be used for solving these problems. We prove that, under some positivity conditions, these stochastic problems are reduced to certain deterministic bottleneck linear problems. An application of these problems to bottleneck spanning tree problems is given. Two simple numerical examples are presented. This paper was written when I.M. Stancu-Minasian was visiting the Instituto Complutense de Análisis Económico, in the Universidad Complutensen de Madrid, from October 1, 1997 to November 15, 1997 and from October 24, 1998 to November, 9, 1998, as invited researcher. He is grateful to the Institution.     

A general framework for multistage mean-variance post-tax optimization

An investor’s decisions affect the way taxes are paid in a general portfolio investment, modifying the net redemption value and the yearly optimal portfolio distribution. We investigate the role of these decisions on multistage mean-variance portfolio allocation model. A number of risky assets grouped in wrappers with special taxation rules is integrated in a multistage financial portfolio optimization problem. The uncertainty on the returns of assets is specified as a scenario tree generated by simulation/clustering based approach. We show the impact of decisions in the yearly reallocation of the investments for three typical cases with an annual fixed withdrawal in a fixed horizon that utilizes completely the option of taper relief offered by banks in UK. Our computational framework can be used as a tool for testing decisions in this context.