Consensus based optimization: Difference between revisions

Revision as of 15:35, 4 February 2024

Revision as of 15:58, 4 February 2024

Line 8:

== The algorithm ==

Consider an ensemble of points <math>x_t = (x_t^1,\dots, x_t^N) \in {\cal{X}}^N</math>, dependent of the time <math>t\in[0,\infty)</math>. Then the update for the <math>i</math>th particle is formulated as a stochastic differential equation,{{NumBlk|::|<math display="block">dx^i_t = -\lambda\, \underbrace{(x^i_t-c_\alpha(x_t))\,dt}_{\text{consensus drift}} + \sigma \underbrace{D(x^i_t-c_{\alpha}(x_t))\,dB^i_t}_{\text{scaled diffusion}}</math>|{{EquationRef|1}}}}with the following components:

* '''The consensus point''' <math>c_{\alpha}(x)</math>: The key idea of CBO is that in each step the particles “agree” on a common consensus point, by computing an average of their positions, weighted by their current objective function value <math display="block">c_\alpha(x_t) = \frac{1}{\sum_{i=1}^N \omega_\alpha(x^i_t)} \sum_{i=1}^N x^i_t\ \omega_\alpha(x^i_t), \quad\text{ with }\quad \omega_\alpha(\,\cdot\,) = \mathrm{exp}(-\alpha f(\,\cdot\,)).

Line 24 ⟶ 25:

== Notes on Implementation ==

In practice, the SDE in {{EquationNote}} is discretized via the [[Euler–Maruyama method]] such that the following explicit update formula for the ensemble <math>x = (x^1,\dots,x^N)</math> is obtained,<math display="block">x^i \gets x^i-\lambda\, (x^i-c_\alpha(x))\,dt + \sigma D(x^i-c_{\alpha}(x))\, B^i.</math>If one can employ an efficient implementation of the [[LogSumExp]] functions, this can be beneficial for numerical stability of the consensus point computation. We refer to existing implementation in [[Python (programming language)|Python]] [https://pdips.github.io/CBXpy/] and [[Julia (programming language)|Julia]] [https://github.com/PdIPS/CBX.jl].

== Variants ==