A Local Search Approach to Solve a Financial Portfolio Design Problem

A Local Search Approach to Solve a Financial Portfolio Design Problem

Fatima Zohra Lebbah (LITIO Laboratory, University of Oran, Oran, Algeria and Science and Techniques Preparatory School of Oran, Oran, Algeria) and Yahia Lebbah (LITIO Laboratory, University of Oran, Oran, Algeria)
Copyright: © 2015 |Pages: 17
DOI: 10.4018/IJAMC.2015040101


This paper introduces a local search optimization technique for solving efficiently a financial portfolio design problem which consists to affect assets to portfolios, allowing a compromise between maximizing gains and minimizing losses. This practical problem appears usually in financial engineering, such as in the design of CDO-squared portfolios. This problem has been modeled by Flener et al. who proposed an exact method to solve it. It can be formulated as a quadratic program on the 0-1 domain. It is well known that exact solving approaches on difficult and large instances of quadratic integer programs are known to be inefficient. That is why this work has adopted a local search method. It proposes neighborhood and evaluation functions specialized on this problem. To boost the local search process, it also proposes a greedy algorithm to start the search with an optimized initial configuration. Experimental results on non-trivial instances of the problem show the effectiveness of this work's approach.
Article Preview

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

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 9: 4 Issues (2018): 2 Released, 2 Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing