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 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.     

Multi-stage portfolio selection problem with dynamic stochastic dominance constraints

We study the multi-stage portfolio selection problem where the utility function of an investor is ambiguous. The ambiguity is characterized by dynamic stochastic dominance constraints, which are able to capture the dynamics of the random return sequence during the investment process. We propose a multi-stage dynamic stochastic dominance constrained portfolio selection model, and use a mixed normal distribution with time-varying weights and the K-means clustering technique to generate a scenario tree for the transformation of the proposed model. Based on the scenario tree representation, we derive two linear programming approximation problems, using the sampling approach or the duality theory, which provide an upper bound approximation and a lower bound approximation for the original nonconvex problem. The upper bound is asymptotically tight with infinitely many samples. Numerical results illustrate the practicality and efficiency of the proposed new model and solution techniques.

     

Multi-stage scenario generation by the combined moment matching and scenario reduction method

We describe an opportunity to speed up multi-stage scenario generation and reduction using a combination of two well-known methods: the moment matching method (Høyland and Wallace, 2001) and the method for scenario reduction to approximately minimize a metric (Heitsch and Römish, 2009). Our suggestion is to combine them rather than using them in serial by making use of a stage-wise approximation to the moment matching algorithm. Computational results show that combining the methods can bring significant benefits.     

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.     

A Multi-Stage Stochastic Integer Programming Approach for Capacity Expansion under Uncertainty

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.     

Scenario generation and stochastic programming models for asset liability management

In this paper, we develop and test scenario generation methods for asset liability management models. We propose a multi-stage stochastic programming model for a Dutch pension fund. Both randomly sampled event trees and event trees fitting the mean and the covariance of the return distribution are used for generating the coefficients of the stochastic program. In order to investigate the performance of the model and the scenario generation procedures we conduct rolling horizon simulations. The average cost and the risk of the stochastic programming policy are compared to the results of a simple fixed mix model. We compare the average switching behavior of the optimal investment policies. Our results show that the performance of the multi-stage stochastic program could be improved drastically by choosing an appropriate scenario generation method.     

基于SIFT特征向量的图像检索优化

基于SIFT(scale-invariant feature transform,尺度不变特征转换)向量的图像检索在精度和实时性方面都与使用者的心理预期有较大的偏差,该文在建树（build vocabulary tree）、检索、以及匹配度计算方面做了一些改进,在满足实时性的要求下,提高了检索精度;在建树过程中,重新定义了SIFT特征向量聚类机制,将分类和K均值聚类法结合起来代替传统的K均值聚类法;在进行图像检索时,直接利用已有欧氏距离信息,减少向量之间距离的计算,对SIFT向量统一化处理;最后通过改进单位化处理方法,克服SIFT大数据造成的误差．数值结果表明,改进后vocabulary tree的节点有更强的差异性, 克服了将训练集按数量均分而不是按距离均分和直接决定树的层数的缺陷;使得检索时间很好地满足了实时性的要求;改进的单位化方法消除了SIFT大数据的误差,从而极大地提高了检索精度．     

Generating scenario trees: A parallel integrated simulation-optimization approach

A crucial issue for addressing decision-making problems under uncertainty is the approximate representation of multivariate stochastic processes in the form of scenario tree. This paper proposes a scenario generation approach based on the idea of integrating simulation and optimization techniques. In particular, simulation is used to generate outcomes associated with the nodes of the scenario tree which, in turn, provide the input parameters for an optimization model aimed at determining the scenarios’ probabilities matching some prescribed targets. The approach relies on the moment-matching technique originally proposed in [K. Høyland, S.W. Wallace, Generating scenario trees for multistage decision problems, Manag. Sci. 47 (2001) 295-307] and further refined in [K. Høyland, M. Kaut, S.W. Wallace, A heuristic for moment-matching scenario generation, Comput. Optim. Appl. 24 (2003) 169-185]. By taking advantage of the iterative nature of our approach, a parallel implementation has been designed and extensively tested on financial data. Numerical results show the efficiency of the parallel algorithm and the improvement in accuracy and effectiveness.     

A warm-start approach for large-scale stochastic linear programs

We describe a way of generating a warm-start point for interior point methods in the context of stochastic programming. Our approach exploits the structural information of the stochastic problem so that it can be seen as a structure-exploiting initial point generator. We solve a small-scale version of the problem corresponding to a reduced event tree and use the solution to generate an advanced starting point for the complete problem. The way we produce a reduced tree tries to capture the important information in the scenario space while keeping the dimension of the corresponding (reduced) deterministic equivalent small. We derive conditions which should be satisfied by the reduced tree to guarantee a successful warm-start of the complete problem. The implementation within the HOPDM and OOPS interior point solvers shows remarkable advantages.     

A dynamic stochastic programming model for international portfolio management

We develop a multi-stage stochastic programming model for international portfolio management in a dynamic setting. We model uncertainty in asset prices and exchange rates in terms of scenario trees that reflect the empirical distributions implied by market data. The model takes a holistic view of the problem. It considers portfolio rebalancing decisions over multiple periods in accordance with the contingencies of the scenario tree. The solution jointly determines capital allocations to international markets, the selection of assets within each market, and appropriate currency hedging levels. We investigate the performance of alternative hedging strategies through extensive numerical tests with real market data. We show that appropriate selection of currency forward contracts materially reduces risk in international portfolios. We further find that multi-stage models consistently outperform single-stage models. Our results demonstrate that the stochastic programming framework provides a flexible and effective decision support tool for international portfolio management.     

Stochastic lot-sizing with backlogging: computational complexity analysis

For a multi-stage stochastic programming problem, one approach is to explore a scenario tree based formulation for the problem and solve the formulation efficiently. There has been significant research progress on how to generate scenario trees in the literature. However, there is limited work on analyzing the computational complexity of the scenario-tree based formulation that considers the number of tree nodes as the input size. In this paper, we use stochastic lot-sizing problems as examples to study the computational complexity issues for the scenario-tree based formulations. We develop production path properties and a general dynamic programming framework based on these properties. The dynamic programming framework allows us to show that the optimal value function is piecewise linear and continuous, which enables us to develop polynomial time algorithms for several different problems, including those with backlogging and varying capacities under certain conditions. As special cases, we develop polynomial time algorithms that run in O(n²){\mathcal{O}(n^2)} and O(n²T log n){\mathcal{O}(n^2T\,{\rm log}\,n)} times, respectively for stochastic uncapacitated and constant capacitated lot-sizing problems with backlogging, regardless of the scenario tree structure.     

Robust portfolio selection based on a multi-stage scenario tree

The aim of this paper is to apply the concept of robust optimization introduced by Bel-Tal and Nemirovski to the portfolio selection problems based on multi-stage scenario trees. The objective of our portfolio selection is to maximize an expected utility function value (or equivalently, to minimize an expected disutility function value) as in a classical stochastic programming problem, except that we allow for ambiguities to exist in the probability distributions along the scenario tree. We show that such a problem can be formulated as a finite convex program in the conic form, on which general convex optimization techniques can be applied. In particular, if there is no short-selling, and the disutility function takes the form of semi-variance downside risk, and all the parameter ambiguity sets are ellipsoidal, then the problem becomes a second order cone program, thus tractable. We use SeDuMi to solve the resulting robust portfolio selection problem, and the simulation results show that the robust consideration helps to reduce the variability of the optimal values caused by the parameter ambiguity.     

On capacity expansion planning under strategic and operational uncertainties based on stochastic dominance risk averse management

A new scheme for dealing with uncertainty in scenario trees is presented for dynamic mixed 0–1 optimization problems with strategic and operational stochastic parameters. Let us generically name this type of problems as capacity expansion planning (CEP) in a given system, e.g., supply chain, production, rapid transit network, energy generation and transmission network, etc. The strategic scenario tree is usually a multistage one, and the replicas of the strategic nodes root structures in the form of either a special scenario graph or a two-stage scenario tree, depending on the type of operational activity in the system. Those operational scenario structures impact in the constraints of the model and, thus, in the decomposition methodology for solving usually large-scale problems. This work presents the modeling framework for some of the risk neutral and risk averse measures to consider for CEP problem solving. Two types of risk averse measures are considered. The first one is a time-inconsistent mixture of the chance-constrained and second-order stochastic dominance (SSD) functionals of the value of a given set of functions up to the strategic nodes in selected stages along the time horizon, The second type is a strategic node-based time-consistent SSD functional for the set of operational scenarios in the strategic nodes at selected stages. A specialization of the nested stochastic decomposition methodology for that problem solving is outlined. Its advantages and drawbacks as well as the framework for some schemes to, at least, partially avoid those drawbacks are also presented.     

Tree template matching in unranked ordered trees

We consider the problem of tree template matching, a type of tree pattern matching, where the tree templates have some of their leaves denoted as “donʼt care”, and propose a solution based on the bottom-up technique. Specifically, we transform the tree pattern matching problem for unranked ordered trees to a string matching problem, by transforming the tree template and the subject tree to strings representing their postfix bar notation, and then propose a table-driven algorithm to solve it. The proposed algorithm is divided into two phases: the preprocessing and the searching phase. The tree template is preprocessed once, and the searching phase can be applied to many subject trees, without the need of preprocessing the tree template again. Although we prove that the space required for preprocessing is exponential in the size of the tree template in the worst case, we show that for a specific class of tree templates, the space required is linear in the size of the tree template. The time for the searching phase is linear in the size of the subject tree in the worst case. Thus, the algorithm is asymptotically optimal when one needs to search for a given tree template, of constant to logarithmic size, in many subject trees.     

On solving the dual for portfolio selection by optimizing Conditional Value at Risk

This note is focused on computational efficiency of the portfolio selection models based on the Conditional Value at Risk (CVaR) risk measure. The CVaR measure represents the mean shortfall at a specified confidence level and its optimization may be expressed with a Linear Programming (LP) model. The corresponding portfolio selection models can be solved with general purpose LP solvers. However, in the case of more advanced simulation models employed for scenario generation one may get several thousands of scenarios. This may lead to the LP model with huge number of variables and constraints thus decreasing the computational efficiency of the model. To overcome this difficulty some alternative solution approaches are explored employing cutting planes or nondifferential optimization techniques among others. Without questioning importance and quality of the introduced methods we demonstrate much better performances of the simplex method when applied to appropriately rebuilt CVaR models taking advantages of the LP duality.     

No-arbitrage conditions,scenario trees,and multi-asset financial optimization

Many numerical optimization methods use scenario trees as a discrete approximation for the true (multi-dimensional) probability distributions of the problem’s random variables. Realistic specifications in financial optimization models can lead to tree sizes that quickly become computationally intractable. In this paper we focus on the two main approaches proposed in the literature to deal with this problem: scenario reduction and state aggregation. We first state necessary conditions for the node structure of a tree to rule out arbitrage. However, currently available scenario reduction algorithms do not take these conditions explicitly into account. State aggregation excludes arbitrage opportunities by relying on the risk-neutral measure. This is, however, only appropriate for pricing purposes but not for optimization. Both limitations are illustrated by numerical examples. We conclude that neither of these methods is suitable to solve financial optimization models in asset–liability or portfolio management.     

Scenario tree modeling for multistage stochastic programs

An important issue for solving multistage stochastic programs consists in the approximate representation of the (multivariate) stochastic input process in the form of a scenario tree. In this paper, we develop (stability) theory-based heuristics for generating scenario trees out of an initial set of scenarios. They are based on forward or backward algorithms for tree generation consisting of recursive scenario reduction and bundling steps. Conditions are established implying closeness of optimal values of the original process and its tree approximation, respectively, by relying on a recent stability result in Heitsch, Römisch and Strugarek (SIAM J Optim 17:511–525, 2006) for multistage stochastic programs. Numerical experience is reported for constructing multivariate scenario trees in electricity portfolio management.     

Application of honey-bee mating optimization algorithm on clustering

Cluster analysis is one of attractive data mining technique that use in many fields. One popular class of data clustering algorithms is the center based clustering algorithm. K-means used as a popular clustering method due to its simplicity and high speed in clustering large datasets. However, K-means has two shortcomings: dependency on the initial state and convergence to local optima and global solutions of large problems cannot found with reasonable amount of computation effort. In order to overcome local optima problem lots of studies done in clustering. Over the last decade, modeling the behavior of social insects, such as ants and bees, for the purpose of search and problem solving has been the context of the emerging area of swarm intelligence. Honey-bees are among the most closely studied social insects. Honey-bee mating may also be considered as a typical swarm-based approach to optimization, in which the search algorithm is inspired by the process of marriage in real honey-bee. Honey-bee has been used to model agent-based systems. In this paper, we proposed application of honeybee mating optimization in clustering (HBMK-means). We compared HBMK-means with other heuristics algorithm in clustering, such as GA, SA, TS, and ACO, by implementing them on several well-known datasets. Our finding shows that the proposed algorithm works than the best one.