Consensus based optimization: Difference between revisions

Revision as of 16:27, 17 August 2024

Revision as of 16:32, 17 August 2024

Line 9:

== 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>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:

<math>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>

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 21 ⟶ 26:

== Notes on Implementation ==

In practice, the SDE in {{EquationNote|2=(1)}} 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 ==

=== CBO with momentum ===

=== Sampling ===

Consensus-based optimization can be transformed into a sampling method<ref>{{Citation |last=Carrillo |first=J. A. |title=Consensus Based Sampling |date=2021-11-04 |url=https://arxiv.org/abs/2106.02519 |access-date=2024-08-17 |doi=10.48550/arXiv.2106.02519 |last2=Hoffmann |first2=F. |last3=Stuart |first3=A. M. |last4=Vaes |first4=U.}}</ref> by modifying the noise term and choosing appropriate hyperparameters. Namely, one considers the following SDE{{NumBlk|::|<math>dx^i_t = -(x^i_t-c_\alpha(x_t))\,dt + \sqrt{2 \tilde{\lambda}^{-1}\, C_\alpha(x_t)}\,dB^i_t,</math>|{{EquationRef|2}}}}where the weighted covariance matrix is defined as

<math>dx^i_t = -(x^i_t-c_\alpha(x_t))\,dt + \sqrt{2 \tilde{\lambda}^{-1}\, C_\alpha(x_t)}\,dB^i_t,</math>

where the weighted covariance matrix is defined as

<math>C_\alpha(x_t) := \frac{1}{\sum_{i=1}^N \omega_\alpha(x_t^i)}\sum_{i=1}^N (x_t^i - c(x_t)) \otimes (x_t^i - c(x_t)) \omega(x_t^i) </math>.

Line 48 ⟶ 56:

</math>, corresponds to the mean-shift algorithm.

* '''Bounded confidence model''': When choosing a constant objective function, no noise model, but also the special kernel function <math>k(x,\tilde x) = 1_{\|x-\tilde x\| \leq \kappa}

</math>, the SDE in {{EquationNote|2=(1)}} transforms to a ODE known as the bounded confidence model<ref>{{Cite journal |last1=Deffuant |first1=Guillaume |last2=Neau |first2=David |last3=Amblard |first3=Frederic |last4=Weisbuch |first4=Gérard |date=January 2000 |title=Mixing beliefs among interacting agents |url=https://www.worldscientific.com/doi/abs/10.1142/S0219525900000078 |journal=Advances in Complex Systems |language=en |volume=03 |issue=1n04 |pages=87–98 |doi=10.1142/S0219525900000078 |s2cid=15604530 |issn=0219-5259}}</ref>, which arises in opinion dynamics.

== See also ==