Dense conjugate initialization for deterministic PSO in applications: ORTHOinit+

https://doi.org/10.1016/j.asoc.2021.107121Get rights and content

Highlights

  • Initializations of Particle Swarm Optimization (PSO) heuristic procedure.

  • Dynamic linear system paired with the trajectory of particles in PSO.

  • Conjugacy among n-dimensional real vectors.

  • Portfolio selection problems modeled via a penalty approach.

  • Ship design optimization and analysis of possible different scenarios.

Abstract

This paper describes a class of novel initializations in Deterministic Particle Swarm Optimization (DPSO) for approximately solving costly unconstrained global optimization problems. The initializations are based on choosing specific dense initial positions and velocities for particles. These choices tend to induce in some sense orthogonality of particles’ trajectories, in the early iterations, in order to better explore the search space. Our proposal is inspired by both a theoretical analysis on a reformulation of PSO iteration, and by possible limits of the proposals reported in Campana et al. (2010); Campana et al. (2013). We explicitly show that, in comparison with other initializations from the literature, our initializations tend to scatter PSO particles, at least in the first iterations. The latter goal is obtained by imposing that the initial choice of particles’ position/velocity satisfies specific conjugacy conditions, with respect to a matrix depending on the parameters of PSO. In particular, by an appropriate condition on particles’ velocities, our initializations also resemble and partially extend a general paradigm in the literature of exact methods for derivative-free optimization. Moreover, we propose dense initializations for DPSO, so that the final approximate global solution obtained is possibly not too sparse, which might cause troubles in some applications. Numerical results, on both Portfolio Selection and Computational Fluid Dynamics problems, validate our theory and prove the effectiveness of our proposal, which applies also in case different neighborhood topologies are adopted in DPSO.

Introduction

In this paper we first consider the solution of the unconstrained global optimization problem minxRnf(x),where f:RnR is continuous and possibly nondifferentiable, so that derivatives are unavailable. In particular, we aim at detecting a global minimum x of (1), satisfying f(x)f(x), for any xRn. As well known, the existence of a global minimum of (1) can be often guaranteed under mild assumptions on f(x) (e.g., f(x) is coercive, with limxf(x)=+). Furthermore, in order to motivate the use of an heuristic procedure to solve (1), in place of possibly more expensive exact asymptotic convergent methods, we also assume that the function f(x) is computationally expensive and a fast approximate solution is sought. Observe that in the last decade we have seen a fast increasing complexity in applications, where optimization techniques are sought [1], [2], [3]. In particular, the demand of sophisticated and efficient methods which do not rely on the smoothness of the functions has considerably speeded up, because of the abundance of problems where derivatives are unavailable and the functions are only accessible through black-boxes (see [4]). In this regard, Automatic Differentiation [5] helps to exactly retrieve derivatives using only function evaluations, but it needs the analytical expression of the functions in hand. Conversely, two main derivative-free (DFO) approaches have gained the attention in the last decades, both with pros and cons. Direct Search methods, which exploit the objective function information along a precise pattern of search directions (see [6]), and Model Based DFO methods, which use information of the function based on a local model (see [4]). In particular, among recent advances we can find the class of Mesh Adaptive Direct Search (MADS) algorithms [7], [8], along with their variants. They represent a natural evolution of Direct Search methods for nonsmooth constrained problems, and are based on considering a dense set of search directions.

To our purposes in this paper we focus on the heuristic procedure PSO, which is neither able to guarantee the convergence to global minima nor it ensures global convergence (i.e. convergence from any starting iterate) to stationary points. PSO represents an iterative method for the approximate solution of global optimization problems, based on updating a swarm of P particles (see [9], [10], [11], [12] and therein references). The use of heuristic methods in place of DFO globally convergent techniques is advisable in those cases where the function evaluation is rather expensive, or the number of function evaluations, necessary for the solution of the problem in hand, tends to increase. In this regard, heuristics can offer a reasonable compromise between the accuracy of the final solution and the computational budget required to obtain it. Each particle represents a vector (position) in Rn and iteratively describes a trajectory in Rn. At the kth iteration the jth particle updates its position as xjk+1=xjk+vjk+1,j=1,,P,where xjkRn indicates its current position, vjk+1Rn is its velocity and represents a search direction. Borrowing a standard terminology from optimization, we have in general that vjk+1 is not gradient related. In other words, vjk+1 might possibly be not a descent direction for f(x) at xjk, so that any small movement along vjk+1 might not yield a function decrease. As a natural consequence, we have that as already remarked, the global convergence properties for PSO iteration (2) can be hardly proved without further additional assumptions. Observe that some papers have been proposed in the literature, where PSO was paired with derivative-free globally convergent methods, based on both linesearch methods (see [13], [14]) and pattern search methods (see [15], [16]). In the current paper our aim is limited to the study of favorable variants of PSO initializations, without issuing problems related to global convergence.

In PSO, the original expression of vector vjk+1 (see also [9]), for a particle j, was given by vjk+1=vjk+cjrj(pjkxjk)+cgrg(pgkxjk),where cj and cg are constant parameters, while rj and rg are suitable random vectors. Finally, the symbol ‘’ represents a component-wise product, and pjkargmin0hk{f(xjh)},j=1,,P,pgkargmin0hk,j=1,,P{f(xjh)},being, at step k, pjk the personal best position so far of particle j, and pgk the global best position so far of the entire swarm, respectively.

Relations (2)–(3) reveal that in PSO iteration, the current position of a particle depends on its lattermost position, but is also independent of the other previous positions. Equivalently, PSO can be viewed as a Markov chain. As usually reported in the literature, cj is the so called cognitive parameter, and multiplies the contribution from the history of the jth particle. On the other hand, cg is the social parameter, and the vector cgrg(pgkxjk) in (3) attempts to balance the information from each particle’s history through a social contribution, summarized by the current global best position in the swarm.

This paper is mainly focused on addressing the initialization in PSO (for a partial analysis and a numerical experience on the impact of PSO initialization, the reader can refer to the recent paper by [17] and therein references). Specifically, we first consider a DPSO iteration as in [18]. From the latter paper we also borrow the idea of routing the particles’ trajectories so that they possibly follow nearly orthogonal patterns, in a sense which is specified in Section 4. However, in this paper we also attempt to overcome some limits in [18] and [19], as indicated in the following items.

  • (i)

    In [18] the authors tend to impose (at least in the early DPSO iterations) the orthogonality of the entire trajectories of the particles, in an extended search space. On the contrary, here we provide analytical conditions to impose only orthogonal velocities of particles, in the early iterations. The resulting approach proves to be more efficient than the one in [18].

  • (ii)

    Similarly to [19] we first tend to impose the orthogonality of particles’ velocities, in the early iterations. Then, unlike in [19] we suitably recombine vectors obtained by solving an intermediate symmetric eigenvalue problem, so that linear independency among the velocities is finally pursued, at least in the early iterations.

  • (iii)

    We can guarantee that, unlike [18], [19], our proposal here introduces ‘dense’ approximations for the initial positions and velocities of particles. I.e., we guarantee that particles initialization is not sparse, which may cause on some applications an undesired bias of the final results (see also Section 5).

On the other hand, our approach takes into account the results obtained in the landmark papers [9], [20], [21], [22], [23], along with [24], [25], [26], where several relevant issues related to PSO initialization are investigated. Note that in our numerical experience here, we are not concerned with comparing our proposal with other efficient initializations from the literature. This choice is motivated by one fact, which definitely makes the latter comparison unfair. On one hand, more standard initializations typically handle random positions and velocities, so that they require a statistical analysis in order to validate the results they provide. This turns to increase the overall number of function evaluations, which might compromise efficiency. Since our proposal does not use any random parameter, to some extent we might be possibly less flexible, however no statistics on the numerical results is needed (see also [17], [27]). The latter fact turns to be an essential requisite on our ship design problems, where each objective function evaluation is often the result of a time consuming simulation. Hence, we preferred to report our numerical experience in Section 7 including only deterministic initializations paired with DPSO.

For the sake of completeness, we also highlight that our deterministic initialization can be hardly paired with non-deterministic versions of PSO. Indeed, the presence of random parameters in PSO might cause the matrix Q(k) in (9) to yield the inequality Q(k)[Q(1)]k, which destroys the achievements in Sections 3 Computation of the free response, 4 An attempt to improve the effectiveness for our DPSO initialization .

Sections 2 PSO iteration as a linear dynamic system, 3 Computation of the free response briefly report a revised version of the proposal by [18], while Section 4 contains both the first contribution of this paper, along with some theoretical results. Sections 5 Possible drawbacks: a simple example, 6 A dense modification motivate a more specific initialization for DPSO, which is then tested on a ship design problem in Section 7. Finally, Section 8 and an Appendix will complete the paper, including some extensions and technical proofs.

We recall that with ‘det(A)’ we indicate the determinant of matrix A. ‘I’ indicates the identity matrix of suitable dimension and ‘ei’ is the ith unit vector. To avoid a burdensome notation the Euclidean norm is simply indicated by , while p represents the standard p-norm.

Section snippets

PSO iteration as a linear dynamic system

In order to describe our novel initialization for a modified PSO scheme, let us consider the next Assumption 1 (which characterizes the so called Deterministic Particle Swarm Optimization — DPSO, see also [28]).

Assumption 1 DPSO

We assume in (3) that cj=c and rj=r, for any j=1,,P. Moreover, we set cg=c̄, rg=r̄, being c,r,c̄,r̄ suitable positive constant coefficients.

Now, following the guidelines by [17], we also introduce in (3) the real parameter χ (constriction factor) and choose r=r̄=1 in Assumption 1. Then,

Computation of the free response XL(k) and choice of DPSO coefficients

Suppose that Assumption 1 holds, hereafter in order to simplify the notation we introduce the following position in (9) ω=χ(c+c̄).

Then, before proceeding with our analysis, we recall (see also [18], [21], [24], [25], [26]) that in order to provide necessary conditions which avoid divergence of the trajectories of particles, the relations 0<χ<10<ω<2(χ+1)must hold. In this regard other settings for DPSO parameters can be chosen, as specified by [26]. In any case, the relations (13) guarantee that

An attempt to improve the effectiveness for our DPSO initialization

This section is mainly devoted to study a possible improvement for DPSO initialization, provided that Assumption 1, Assumption 2 hold. Our proposal allows DPSO to

  • 1.

    widely exploring the search space in the early iterations,

  • 2.

    maintaining iteration (5),

  • 3.

    possibly reducing the overall computational effort, when measured throughout the number of function evaluations.

Note that as regards item 2., we are interested about improving DPSO basic iteration, rather than modifying it. That is why our proposal is

Possible drawbacks: a simple example

Here we detail reasons for the fact that on several real problems the setting (34)–(35) for the initial DPSO population might be still inadequate. This seems an important preliminary step in order to justify the analysis in the second part of this paper. To evaluate the effectiveness of the initial setting (34)–(35), we first tested it on the solution of a linearly constrained nondifferentiable portfolio selection problem, described below.

We consider a simplified version of the portfolio

A dense modification

According with the discussion in the last section, here we want to provide a modification of DPSO initialization (34)–(35), with the specific aim to possibly pursue a dense final solution for problem (1). We remark that the proposal in this section strongly differs from [19] and the analysis in Section 4.2. Indeed, here we specifically focus on the issue of density (i.e. avoiding a large number of zero entries) for the final solution provided by DPSO. On this purpose, let be given the 2n

Examples on analytic benchmark and ship design problems

Simulation-based design optimization (SBDO) paradigm supports the design process of complex engineering systems and recently replaced the traditional expensive build and test approach. SBDO integrates three key elements: computer simulations, design modification methods and optimization algorithms. Within the context of ship/ocean applications global derivative-free algorithms are widely used, since objective and constraint functions – often provided by black box tools – are non convex and

Conclusions and future work

In this paper we have analyzed novel initializations for DPSO, in order to better exploit the topology of the swarm in Rn, and speed up in the early iterations the solution of unconstrained optimization and bound-constrained optimization problems.

Unlike the proposal by [18], the theory in the current paper yields a guideline for the choice of 2n particles’ initial position/velocity, and not just n. Moreover, our initialization is dense and tends to scatter the particles in the search space. The

CRediT authorship contribution statement

Cecilia Leotardi: Conceptualization, Methodology, Software, Data curation, Writing - original draft, Writing - review & editing, Supervision, Software, Validation. Andrea Serani: Conceptualization, Methodology, Software, Data curation, Writing - original draft, Writing - review & editing, Supervision, Software, Validation. Matteo Diez: Conceptualization, Methodology, Software, Data curation, Writing - original draft, Writing - review & editing, Supervision, Software, Validation. Emilio F.

Declaration of Competing Interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Acknowledgments

The work is supported by the US Department of the Navy Office of Naval Research Global, NICOP grant N62909-18-1-2033, administered by Dr. Woei-Min Lin, Dr. Elena McCarthy, and Dr. Salahuddin Ahmed, and by the Italian Flagship Project RITMARE, funded by the Italian Ministry of Education .

References (50)

  • FasanoG. et al.

    Preconditioning Newton–Krylov methods in nonconvex large scale optimization

    Comput. Optim. Appl.

    (2013)
  • TerlakyT. et al.

    Advances and trends in optimization with engineering applications

  • ConnA. et al.

    Introduction to derivative-free optimization

    (2009)
  • GriewankA.

    Automatic differentiation

  • KoldaT.G. et al.

    Optimization by direct search: New perspectives on some classical and modern methods

    SIAM Rev.

    (2003)
  • AudetC. et al.

    Erratum: Mesh adaptive direct search algorithms for constrained optimization

    SIAM J. Optim.

    (2008)
  • AudetC. et al.

    Mesh adaptive direct search algorithms for constrained optimization

    SIAM J. Optim.

    (2006)
  • J. Kennedy, R. Eberhart, Particle swarm optimization, in; Proceedings of the Fourth IEEE Conference on Neural Networks,...
  • BonyadiM.R. et al.

    A locally convergent rotationally invariant particle swarm optimization algorithm

    Swarm Intell.

    (2014)
  • CleghornC.W. et al.

    Particle swarm convergence: Standardized analysis and topological influence

  • CleghornC.W. et al.

    Particle swarm variants: standardized convergence analysis

    Swarm Intell.

    (2015)
  • SeraniA. et al.

    Globally convergent hybridization of particle swarm optimization using line search-based derivative-free techniques

  • VazA. et al.

    Pswarm: A hybrid solver for linearly constrained global derivative-free optimization

    Optim. Methods Softw.

    (2009)
  • VazA. et al.

    A particle swarm pattern search method for bound constrained global optimization

    J. Global Optim.

    (2007)
  • CampanaE.F. et al.

    Dynamic analysis for the selection of parameters and initial population, in particle swarm optimization

    J. Global Optim.

    (2010)
  • Cited by (4)

    View full text