This chapter introduces a VNS-based local search for solving efficiently a financial portfolio design problem described in Chapter 1 and modeled in Chapter 3. The mathematical model tackled is a 0-1 quadratic model. It is well known that exact solving approaches on large instances of this kind of model are costly. The authors have proposed local search approaches to solve the problem, and the efficiency of this type of method has been proved. This chapter shows that the matricial 0-1 model of the problem enables specialized VNS algorithms by taking into account the particular structure of the financial problem considered. First experiments show that VNS with simulated annealing is effective on non-trivial instances of the problem.
TopBackground
According to (Fonseca & Santos, 2014), VNS variants are able to outperform the winner of third ITC solver1, which applied a Simulated Annealing algorithm. Thus, the efficiency of applying local search methods on the (PD) problem leads to consideration of implementing Variable Neighborhood Search (VNS) techniques.
The Variable Neighborhood Search method (VNS), was proposed by Mladenovic´ and Hansen in 1997. It relies on dynamic neighborhood models in exploring the feasible region (solutions space) of a combinatorial optimization problem. It is a recently developed metaheuristic and could be considered as a frame work of building new heuristics. VNS is an approach which allows a good level of neighborhood diversification, since it offers the opportunity to explore distant neighborhoods. Indeed, the realized jumps from a neighborhood to another via the shaking step, allows a good scanning of the solutions space. Thus, the risk of getting stuck in local minima is minimized.
There are different variants of VNS, namely Variable Neighborhood Descent (VND), Reduced VNS (RVNS) and Skewed VNS (SVNS) (Hansen & Mladenovic´, 2003).
To illustrate the relevance of a VNS approach, we consider the instance 〈10,37,14,6〉, a CDO Squared portfolio including 10 tranches and 37 inner portfolios. As depicted in Table 7.1, the VNS based approach local search method provides a portfolio with the overlapping average λ-AVG = 4.91, which is due to considering all the features of the portfolio problem and the efficiency of the VNS approach.
Table 1. Solution of 〈10,37,14,6〉 with the VNS approach
0 1 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 1
0 1 1 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 1 1
0 0 0 1 0 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 1 0 0 1
1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 0 1 0 0 0 1 0
0 1 1 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0
1 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1
0 0 0 0 0 1 0 1 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0
0 1 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0
1 1 0 1 1 1 1 0 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 |