Abstract
This chapter introduces a local search optimization technique for solving efficiently a ðnancial portfolio design problem that consists of assigning assets to portfolios, allowing a compromise between maximizing gains, and minimizing losses. This practical problem appears usually in ðnancial 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 inefficient. That is why the authors have adopted local search methods, namely simple local search and population local search. They propose neighborhood and evaluation functions specialized on this problem. To boost the local search process, they propose also 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 the incomplete approach.
TopBackground
Local Search techniques (Teofilo & Gonzalez, 2007) are based on constructive and iterative algorithms. They are created to remedy against the complex methods which require significant fine-tuning. The process of a local search is based generally on starting by an initial solution and improving the current solution by making local changes (in the neighborhood of the current solution), until no progress is possible.
Population-based methods (Luke, 2013) differ from the simple local search, in terms of handling a sample of candidate solutions rather than a single solution. Each solution is involved by tweaking the quality assessment. The behavior of population approach prevents algorithm from falling into the trap of local optima, or being just a parallel hill-climber, since the candidate solutions affect how other candidates will hill-climb in the quality function. The detected good solution in the solutions’ sample should cause the rejection of poor solutions or their improvement by being incorporated into good ones.