Globally convergent modification of PSO by a surrogate-based Newton method

One of the key point of the Particle Swarm Optimization (PSO) algorithm is the absence of use of local derivatives of the objective function. PSO is usually able to rapidly converge toward the basin of attraction of a global optimum, and its derivative-free nature is reflected in the small number of objective function evaluations. The side effects of the absence of local information are essentially twofold. Firstly, once the basin of attraction has been identified, the exploitation of the successive local exploration is pretty slow. Secondly, there is not any guarantee about the qualities of the converging point, whose qualification cannot be performed without an analysis of the first and second order local information. To tackle this problem, the application of a local algorithm as soon as a partial convergence of PSO is detected has been successfully investigated in cite{OPTE}. Unfortunately, the computational cost of the local algorithm is added to the overall computational cost, and this may become unsustainable in case of expensive objectives to be considered. Furthermore, the use of a local algorithm simply at the end of the exploration by PSO is only exploring in deep the selected basin of attraction, and this is not helping PSO in detecting the global optimum: in this sense, the use of local information during the course of PSO is much more interesting and possibly fruitful, but is too expensive to be performed by central differences or other schemes. To this aim, the use of surrogate models for the computation of first and second order local information may represents a good option in order to better address the search of the global optimum and also to add some value to the converging point, preserving also the small computational cost of PSO. By the way, the distribution and evolution of a swarm into the design space can provide similar data as a DOE for the derivation of approximated models of the objective function: as a consequence, no further evaluations are needed to this aim. In this paper, the classical PSO algorithm cite{Clerc} is coupled with a Newton method. In order to produce a monotonically descendent sequence, the PSO iteration scheme is adopted, while the Newton step is substituting the classical PSO iteration when this is not able to detect a descent direction. Gradient and Hessian of the objective function are approximated by means of a surrogate model: the training of the surrogate model is obtained by using all the previously computed values of the objective function as from the PSO algorithm. The use of a trust-region approach is helping in maintaining some global convergence properties.