Article Preview
Top1. Introduction
In this paper, we propose a local search method to tackle a financial portfolio design problem (PD) proposed by Flener et al. (Flener et al., 2007) modeling practical problems in financial engineering such as CDO-squared. Local search methods have succeeded to tackle combinatorial problems with large instances in many domains (e.g., tsp, scheduling, etc.). When solving combinatorial problems, even if exact methods are complete and guaranty to treat the whole search space, they are usually inefficient on difficult and large instances. Thus, on such problems, the search space should be partially parsed, but intelligently visited, moving from solution to solution optimizing the objective function; this is the main idea of local search methods (João, 2001).
One noticeable and practical instance of this portfolio design model is the CDO-squared model which is a critical problem in equitable management of clients' portfolios (Gomes and Selman, 2001). We point out that a portfolio is a financial term denoting a collection of investments held by a financial institution or an individual. Let be a set of clients, in order to minimize the risk of loss and to maximize the gain of their investments, the bank institution should assign reliably to each client a set of assets. If we place the best assets in a sub-set of clients, we will expose the rest of clients to risky assets, and loss is certain. Therefore, the idea is to find a compromise and a balanced assignment of assets to different clients. All clients should share fairly the earning assets and the risky assets. This can be stated as a portfolio optimization (Kraft, 2003), where we want an equitable management between the clients' portfolios (Svenja, 2008).
Flener et al. (Flener et al., 2007), who proposed a solving approach based on exact methods, reported that finding the optimal solution is a hard combinatorial problem, and they provide solutions on small instances. However, they gave an analytical lower bound of the optimal value associated to the problem, but they noticed that this bound is rough (in comparison with the optimal bound) on large instances. Also, they proposed a strategy to decompose a problem in order to translate large instances to small instances, exploiting some symmetries (Crawford et al.,1996) (Flener et al., 2002). Finally, this solving approach can give one solution at some local minimum (Ravindra et al., 2002). Consequently, although Flener's approach is based on exact methods, its output has the same nature as local search methods output.
In fact, due to the combinatorial nature of this problem, we propose this first work using local search methods, applied on the original constraints. Particularly, we propose neighborhood and evaluation functions by considering the particular semantic of (PD) constraints. An efficient implementation is realized in the INCOP environment (Neveu and Trombettoni, 2003).
The paper is organized as follows. In section 2, the PD model is detailed by considering a particular specification of the CDO-squared problem. We introduce CDO (collateralized debt obligation) and the portfolio design (PD) problem. In section 3, we motivate this work on using local search methods to tackle the (PD) problem. In section 4 and 5, we introduce the used local search methods, and explain a dedicated neighborhood function and an evaluation function to the (PD) problem. The greedy algorithm computing an optimized initial configuration is detailed in section 6. In section 7, experiments on several instances taken from (Flener et al., 2007) are carried out. Finally, we give some perspectives and conclude the paper.