Elsevier

Applied Mathematics and Computation

Volume 224, 1 November 2013, Pages 611-624
Applied Mathematics and Computation

Particle Swarm Optimization with non-smooth penalty reformulation, for a complex portfolio selection problem

https://doi.org/10.1016/j.amc.2013.07.091Get rights and content

Abstract

In the classical model for portfolio selection the risk is measured by the variance of returns. It is well known that, if returns are not elliptically distributed, this may cause inaccurate investment decisions. To address this issue, several alternative measures of risk have been proposed. In this contribution we focus on a class of measures that uses information contained both in lower and in upper tail of the distribution of the returns. We consider a nonlinear mixed-integer portfolio selection model which takes into account several constraints used in fund management practice. The latter problem is NP-hard in general, and exact algorithms for its minimization, which are both effective and efficient, are still sought at present. Thus, to approximately solve this model we experience the heuristics Particle Swarm Optimization (PSO). Since PSO was originally conceived for unconstrained global optimization problems, we apply it to a novel reformulation of our mixed-integer model, where a standard exact penalty function is introduced.

Introduction

Making effective portfolio selection in real stock markets is a not-so-easy task for at least the following three reasons.

First, we need to gauge the risk by measures that both satisfy appropriate formal properties (namely coherence) and better couple with the non normal return distributions (which characterize the stock markets). Moreover, it should be desirable that these risk measures were suitably parameterized with respect to the investors’ risk attitude. In other terms, we need personalized coherent risk measures that well fit a non Gaussian (financial) world.

Second, we have to take into account several practices and rules of the portfolio management industry that can affect the portfolio selection process (for instance, the use of bounds for the minimum and the maximum number of stocks to trade). Generally, such aspects are formalized in terms of constraints that very often yield NP-hard mathematical programming formulations.

Third, portfolio selection problems arising from the joint use of the considered risk measures, practices and rules are possibly highly nonlinear, nondifferentiable, nonconvex and mixed-integer, which contributes to yield NP-hardness. Therefore, the development of ad hoc solution approaches is usually needed to find the optimal solution of such problems. However, the portfolio management industry usually does not possess the mathematical knowledge and/or the research capabilities to handle such approaches. Furthermore, it could be not convenient for it to build up a team of external experts. As a consequence, part of the investors’ demand might remain unsatisfied or (worse) satisfied by the use of inappropriate solution technologies. Therefore, we need a general tool encompassing a large variety of real portfolio selection problems.

In this paper we deal with such issues, and we propose a tool for managing each of them. Then, we perform a numerical experience on the resulting scheme, by applying it to the selection of large and complex portfolios. In particular, we tackle the above mentioned issues as follows.

First, as measure of risk of the portfolio returns we consider a recently proposed coherent risk measure, based on the combination of upper and lower moments of different orders of the returns distribution (see [7]). The latter measure shows to be able to effectively manage non Gaussian distributions of asset returns and to appropriately reflect different investors’ risk attitudes (see Section 2 for details). In particular, given personal investors’ weighting, it permits to take into account both the risk contained in the “bad tail” (the left one of the portfolio returns), and the chances contained in the “good tail” (the right one of the same portfolio). Further, to the best of our knowledge, apart from [7] this is one of the first applications of such risk measure to large and complex portfolios. In addition, we highlight that the portfolio selection problem considered in [7] is large but-not-complex, since the associated optimization problem is linearly constrained (i.e. relatively “easy” to solve). Conversely, our portfolio selection problem is large and complex, due to the presence of nonlinear mixed-integer constraints (see Section 2 for details) which make the associated optimization problem NP-hard (i.e. difficult to solve).

Second, as the professional practices and rules are concerned, following the indications of a north-eastern Italian company skilled in automatic financial trading systems, we adapt our analysis to the use of bounds for the minimum and the maximum number of stocks to trade.1 Moreover, our model also includes the minimum and the maximum capital percentage to invest in each asset (see also [20] where the quantity to invest in each asset is a positive integer). These bounds are often of interest for the fund manager industry, in order to control (in an indirect way) the transaction costs. All these practices/rules are formalized in terms of constraints, that surely make the corresponding mathematical programming problem NP-hard (see Section 2 for details). Notice that the portfolio selection problem so arising is new in the specialized literature.

Third, our resulting selection problem, which takes into account also standard constraints (namely, the minimum return and the budget constraints) is nonlinear, nondifferentiable and mixed-integer. At present, for such mathematical programming problem (which is NP-hard, see [23]) both efficient and effective solution algorithms are still sought. Thus, in order to both investigate the numerical complexity of our portfolio selection problem and to provide a cheap and reliable solution, we adopt an exact penalty method (see [31], [24], [9], [16]) combined with the Particle Swarm Optimization (PSO), a recently proposed bio-inspired population-based metaheuristic (see [17] as, likely, first contribution on it). In short, our solution approach runs as follows (see Section 3 for details):

  • a standard exact penalty scheme transforms the considered mixed-integer portfolio selection problem into an equivalent nondifferentiable unconstrained minimization problem;

  • then, as also the latter model is nonlinear, nondifferentiable and non convex, for its minimization a derivative-free algorithm is a possible solution method. Among the various approaches proposed in the specialized literature, we consider the PSO in order to approximately computing a global minimizer of the overall exact penalty-based model.

More generally, the choice of bio-inspired metaheuristics as global optimizers is also motivated by the fact that [t]hey are more universal and less exacting with respect to an optimization problem (see [12, page 9]).

Of course, PSO is not the only bio-inspired metaheuristics able to deal with minimization problems like ours. As possible alternatives we recall Differential Evolution (DE) and Genetic Algorithms (GAs). From a methodological point of view observe that our combined use of an exact penalty scheme with the PSO is not frequent in the literature. Indeed, for the solution of constrained problems the PSO is often modified with hybrid variants, which are suitably adapted to cope even with nonlinear constraints. In this respect we first provide a theoretical result ensuring the correspondence between the solutions of the original mathematical programming problem and the solutions of the exact penalty-based model (see Section 3 for details). Further, we also develop a simple original approach for the initialization of the particles’ parameters. Its use yields numerical evidence of improvements in the convergence to a global minimum (see Section 4 for details). Finally, notice that the solution approach we propose is independent of the characteristics of the objective function and of the constraints. In other terms, our proposal might play the role of universal global (approximate) optimizer for a large variety of portfolio selection problems, even if characterized by very different risk measures and systems of constraints.

The remainder of this paper is organized as follows. In the next section first we illustrate the coherent risk measures we use, then we present our portfolio selection problem. In Section 3 first we recall the basics of PSO, then we apply an exact penalty method for the reformulation of our portfolio selection problem. In Section 4 we apply our overall solution procedure to the selection of large and complex portfolios, based on the set of assets constituting the Standard & Poor’s SP 100 index. We test various settings of the solution procedure, where we use a simple approach for the initialization of the particles’ parameters. Then, we apply our approach considering different time periods from August 2004 to October 2009, in order to detect possible differences in the optimal portfolio composition. Further, we compare these results with the ones coming from a couple of suitably chosen benchmark portfolio selection models. Final remarks are given in the last section.

Section snippets

Portfolio selection and risk measures

The basic idea in the portfolio selection problem is to select stocks both maximizing portfolio performance and minimizing its risk. This implies that for a formal approach to the latter problem, a correct definition of performance and risk of the portfolio is required. While there is a general agreement about the measurement of performance using the expected value of the future return of the portfolio, the discussion regarding an adequate measure of risk is still open.

In its pioneering work

PSO for non-smooth reformulation of the portfolio selection problem

Particle Swarm Optimization is an iterative metaheuristics for the solution of nonlinear global optimization problems (see [17]). It is based on a biological paradigm, which is inspired by the flight of birds in a flock. In particular, the basic idea of PSO (see also [3] for a tutorial) is to replicate the behaviour of shoals of fishes or flocks of birds, when they cooperate in the search for food. On this purpose every member of the swarm explores the search area keeping memory of its best

Numerical results

In this section, in order to describe the effectiveness of our approach, we focus on the following two issues:

  • first we apply our solution procedure to the selection of portfolios based on the set of assets constituting the Standard & Poor’s SP 100 index, over different time periods from August 2004 to October 2009;

  • then we compare the so obtained results with the ones coming from a couple of benchmark portfolio selection models: a Markowitz-based solution procedure and a known alternative

Final remarks

In this paper we have first proposed a partially novel reformulation for the selection of large and complex portfolios, characterized by an upper-and-lower-moments-based coherent risk measure and a mixed-integer formulation. This reformulation used a nondifferentiable exact penalty method and was solved using PSO. Although the obtained results are satisfactory, this solution approach seems to offer opportunities for possible improvements and extensions. In particular:

  • As the reformulation of

Acknowledgements

M. Corazza and R. Gusso wish to thank the European Social Fund and the Regione del Veneto for the support received (research project Metodologie informatiche ed algoritmi bio-ispirati per l’ottimizzazione e la gestione in azienda [Computer science methodologies and bio-inspired algorithms for optimization and management in company], code 2120/1/11/1268/ 2008). G. Fasano wishes to thank Progetto Nazionale Bandiera RITMARE 2012–2016, along with the National Research Council-Maritime Research

References (32)

  • M. Clerc et al.

    The Particle swarm – Explosion, stability, and convergence in a multidimensional complex space

    IEEE Transaction on Evolutionary Computation

    (2002)
  • A.R. Conn

    Constrained optimization using a nondifferentiable penalty function

    SIAM Journal on Numerical Analysis

    (1973)
  • G. Di Pillo et al.

    Exact penalty functions in constrained optimization

    SIAM Journal on Control and Optimization

    (1989)
  • V. Feoktistov

    Differential Evolution: In Search of Solutions

    (2006)
  • P.C. Fishburn

    Mean-risk analysis with risk associated with below-target returns

    American Economic Review

    (1977)
  • R. Fletcher

    A class of methods for nonlinear programming with termination and convergence properties

  • Cited by (0)

    View full text