# Particle swarm optimization

Manopt.particle_swarmFunction
patricle_swarm(M, f; kwargs...)
patricle_swarm(M, f, swarm; kwargs...)
patricle_swarm(M, mco::AbstractManifoldCostObjective; kwargs..)
patricle_swarm(M, mco::AbstractManifoldCostObjective, swarm; kwargs..)
particle_swarm!(M, f, swarm; kwargs...)
particle_swarm!(M, mco::AbstractManifoldCostObjective, swarm; kwargs..)

perform the particle swarm optimization algorithm (PSO) to solve

$$$\operatorname{arg\,min}_{p ∈ \mathcal M} f(p)$$$

PSO starts with an initial swarm [BIA10] of points on the manifold. If no swarm is provided, the swarm_size keyword is used to generate random points. The computation can be perfomed in-place of swarm.

To this end, a swarm $S = \{s_1, \ldots, s_n\}$ of particles is moved around the manifold M in the following manner. For every particle $s_k^{(i)}$ the new particle velocities $X_k^{(i)}$ are computed in every step $i$ of the algorithm by

$$$X_k^{(i)} = ω \mathcal T_{s_k^{(i)←s_k^{(i-1)}} X_k^{(i-1)} + c r_1 \operatorname{retr}^{-1}_{s_k^{(i)}}(p_k^{(i)}) + s r_2 \operatorname{retr}^{-1}_{s_k^{(i)}}(p),$$$

where

• $s_k^{(i)}$ is the current particle position,
• $ω$ denotes the inertia,
• $c$ and $s$ are a cognitive and a social weight, respectively,
• $r_j$, $j=1,2$ are random factors which are computed new for each particle and step
• \mathcal T_{⋅←⋅} is a vector transport, and
• \operatorname{retr}^{-1} is an inverse retraction

Then the position of the particle is updated as

$$$s_k^{(i+1)} = \operatorname{retr}_{s_k^{(i)}}(X_k^{(i)}),$$$

Then the single particles best entries $p_k^{(i)}$ are updated as

$$$p_k^{(i+1)} = \begin{cases} s_k^{(i+1)}, & \text{if } F(s_k^{(i+1)}) and the global best position $$\[g^{(i+1)} = \begin{cases} p_k^{(i+1)}, & \text{if } F(p_k^{(i+1)}) Input • M::AbstractManifold: a Riemannian manifold \mathcal M • f: a cost function f: \mathcal M→ ℝ implemented as (M, p) -> v • swarm = [rand(M) for _ in 1:swarm_size]: an initial swarm of points. Instead of a cost function f you can also provide an AbstractManifoldCostObjective mco. Keyword Arguments All other keyword arguments are passed to decorate_state! for state decorators or decorate_objective! for objective decorators, respectively. If you provide the objective directly, these decorations can still be specified Output The obtained approximate minimizer p^*. To obtain the whole final state of the solver, see get_solver_return for details, especially the return_state= keyword. source Manopt.particle_swarm!Function patricle_swarm(M, f; kwargs...) patricle_swarm(M, f, swarm; kwargs...) patricle_swarm(M, mco::AbstractManifoldCostObjective; kwargs..) patricle_swarm(M, mco::AbstractManifoldCostObjective, swarm; kwargs..) particle_swarm!(M, f, swarm; kwargs...) particle_swarm!(M, mco::AbstractManifoldCostObjective, swarm; kwargs..) perform the particle swarm optimization algorithm (PSO) to solve $$\[\operatorname{arg\,min}_{p ∈ \mathcal M} f(p)$$$

PSO starts with an initial swarm [BIA10] of points on the manifold. If no swarm is provided, the swarm_size keyword is used to generate random points. The computation can be perfomed in-place of swarm.

To this end, a swarm $S = \{s_1, \ldots, s_n\}$ of particles is moved around the manifold M in the following manner. For every particle $s_k^{(i)}$ the new particle velocities $X_k^{(i)}$ are computed in every step $i$ of the algorithm by

$$$X_k^{(i)} = ω \mathcal T_{s_k^{(i)←s_k^{(i-1)}} X_k^{(i-1)} + c r_1 \operatorname{retr}^{-1}_{s_k^{(i)}}(p_k^{(i)}) + s r_2 \operatorname{retr}^{-1}_{s_k^{(i)}}(p),$$$

where

• $s_k^{(i)}$ is the current particle position,
• $ω$ denotes the inertia,
• $c$ and $s$ are a cognitive and a social weight, respectively,
• $r_j$, $j=1,2$ are random factors which are computed new for each particle and step
• \mathcal T_{⋅←⋅} is a vector transport, and
• \operatorname{retr}^{-1} is an inverse retraction

Then the position of the particle is updated as

$$$s_k^{(i+1)} = \operatorname{retr}_{s_k^{(i)}}(X_k^{(i)}),$$$

Then the single particles best entries $p_k^{(i)}$ are updated as

$$\[p_k^{(i+1)} = \begin{cases} s_k^{(i+1)}, & \text{if } F(s_k^{(i+1)})

and the global best position

$$\[g^{(i+1)} = \begin{cases} p_k^{(i+1)}, & \text{if } F(p_k^{(i+1)})

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal M$
• f: a cost function $f: \mathcal M→ ℝ$ implemented as (M, p) -> v
• swarm = [rand(M) for _ in 1:swarm_size]: an initial swarm of points.

Instead of a cost function f you can also provide an AbstractManifoldCostObjective mco.

Keyword Arguments

All other keyword arguments are passed to decorate_state! for state decorators or decorate_objective! for objective decorators, respectively. If you provide the objective directly, these decorations can still be specified

Output

The obtained approximate minimizer $p^*$. To obtain the whole final state of the solver, see get_solver_return for details, especially the return_state= keyword.

source

## State

Manopt.ParticleSwarmStateType
ParticleSwarmState{P,T} <: AbstractManoptSolverState

Describes a particle swarm optimizing algorithm, with

Fields

• cognitive_weight: a cognitive weight factor
• inertia: the inertia of the particles
• inverse_retraction_method::AbstractInverseRetractionMethod: an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• retraction_method::AbstractRetractionMethod: a retraction $\operatorname{retr}$ to use, see the section on retractions
• social_weight: a social weight factor
• stop::StoppingCriterion: a functor indicating that the stopping criterion is fulfilled
• vector_transport_method::AbstractVectorTransportMethodP: a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• velocity: a set of tangent vectors (of type AbstractVector{T}) representing the velocities of the particles

Internal and temporary fields

• cognitive_vector: temporary storage for a tangent vector related to cognitive_weight
• p::P: a point on the manifold $\mathcal M$ storing the best point visited by all particles
• positional_best: storing the best position $p_i$ every single swarm participant visited
• q::P: a point on the manifold $\mathcal M$ serving as temporary storage for interims results; avoids allocations
• social_vec: temporary storage for a tangent vector related to social_weight
• swarm: a set of points (of type AbstractVector{P}) on a manifold $\{a_i\}_{i=1}^{N}$

Constructor

ParticleSwarmState(M, initial_swarm, velocity; kawrgs...)

construct a particle swarm solver state for the manifold M starting with the initial population initial_swarm with velocities. The p used in the following defaults is the type of one point from the swarm.

Keyword arguments

particle_swarm

source

## Stopping criteria

Manopt.StopWhenSwarmVelocityLessType
StopWhenSwarmVelocityLess <: StoppingCriterion

Stopping criterion for particle_swarm, when the velocity of the swarm is less than a threshold.

Fields

• threshold: the threshold
• at_iteration: store the iteration the stopping criterion was (last) fulfilled
• reason: store the reason why the stopping criterion was fulfilled, see get_reason
• velocity_norms: interim vector to store the norms of the velocities before computing its norm

Constructor

StopWhenSwarmVelocityLess(tolerance::Float64)

initialize the stopping criterion to a certain tolerance.

source

## Technical details

The particle_swarm solver requires the following functions of a manifold to be available

## Literature

[BIA10]
P. B. Borckmans, M. Ishteva and P.-A. Absil. A Modified Particle Swarm Optimization Algorithm for the Best Low Multilinear Rank Approximation of Higher-Order Tensors. In: 7th International Conference on Swarm INtelligence (Springer Berlin Heidelberg, 2010); pp. 13–23.