Fast and robust consensus-based optimization via optimal feedback control
Yuyang Huang, Michael Herty, Dante Kalise, Nikolas Kantas · 2024
Read Fast and robust consensus-based optimization via optimal feedback control by Yuyang Huang, Michael Herty, Dante Kalise, Nikolas Kantas (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-03051.txt.
Description
Abstract We propose a variant of consensus-based optimization (CBO) algorithms, controlled-CBO , which introduces a feedback control term to improve convergence towards global minimizers of non-convex functions in multiple dimensions. The feedback law is a gradient of a numerical approximation to the Hamilton-Jacobi-Bellman (HJB) equation, which serves as a proxy of the original objective function.
Catalog record
| CREATOR | Yuyang Huang, Michael Herty, Dante Kalise, Nikolas Kantas |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 94 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-03051
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Fast and robust consensus-based optimization via optimal feedback control Yuyang Huang, Michael Herty, Dante Kalise, Nikolas Kantas Abstract We propose a variant of consensus-based optimization (CBO) algorithms, controlled-CBO , which introduces a feedback control term to improve convergence towards global minimizers of non-convex functions in multiple dimensions. The feedback law is a gradient of a numerical approximation to the Hamilton-Jacobi-Bellman (HJB) equation, which serves as a proxy of the original objective function. Thus, the associated control signal furnishes gradient-like information to facilitate the identification of the global minimum without requiring derivative computation from the objective function itself. The proposed method exhibits significantly improved performance over standard CBO methods in numerical experiments, particularly in scenarios involving a limited number of particles, or where the initial particle ensemble is not well positioned with respect to the global minimum. At the same time, the modification keeps the algorithm amenable to theoretical analysis in the mean-field sense. The superior convergence rates are assessed experimentally. keywords global optimization, consensus-based optimization, Hamilton–Jacobi–Bellman PDEs, high-dimensional polynomial approximation † † runningheads: Consensus-based optimization via optimal feedback control / MSC 65K10, 35Q93, 90C56 1 Introduction Optimization plays an essential role in modern science, engineering, machine learning, and statistics [ 33 , 16 , 44 ] . Over the last decades, the flourishing of computational data science has brought significant challenges to optimization, such as high-dimensional search spaces, and non-convex, non-smooth objective functions. These features often limit the use of traditional gradient-based optimization methods [ 46 , 47 ] . For general optimization problems of the form \min_{x\in\mathbb{R}^{d}}f(x), (1) where f:\mathbb{R}^{d}\rightarrow\mathbb{R} is continuous, bounded from below, and attains a unique global minimum, the objective function is possibly nonconvex and has many local minimizers. In such settings, metaheuristic methods have been proposed as an effective alternative for addressing the challenges of global optimization. Among these metaheuristics, agent-based algorithms such as Ant Colony Optimization, Particle Swarm Optimization, or Simulated Annealing [ 57 , 26 , 11 , 24 ] have demonstrated remarkable performance when applied to NP-hard problems. More recently, a novel class of multi-particle, derivative-free methods, known as Consensus-based Optimization (CBO), has been introduced in [ 49 ] . Through a combination of probabilistic and mean field arguments, these methods are capable of effectively solving non-smooth and non-convex global optimization problems in multiple dimensions. The CBO method with anisotropic diffusion employs a system of N\in\mathbb{N} interacting particles with position vector X_{t}^{i}\in\mathbb{R}^{d},i=1,\ldots,N , evolving in time t\in[0,\infty) according to a system of stochastic differential equations (SDEs): dX_{t}^{i}=-\lambda\left(X_{t}^{i}-v_{\alpha}(\rho_{t}^{N})\right)dt+\sigma\operatorname{Diag}(X_{t}^{i}-v_{\alpha}(\rho_{t}^{N}))dW_{t}^{i}, (2) where \lambda,\sigma>0 are drift and noise parameters, respectively. The operator \operatorname{Diag}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d\times d} maps a vector \nu\in\mathbb{R}^{d} onto a diagonal matrix with elements of \nu , and \left((W_{t}^{i})_{t\geq 0}\right)_{i=1,\cdots,N} are i.i.d Wiener processes in \mathbb{R}^{d} . We assume that the initial condition of the particles X_{0}^{i}\in\mathbb{R}^{d} are i.i.d with \operatorname{law}\left(X_{0}^{i}\right)=\rho_{0}\in\mathcal{P}\left(\mathbb{R}^{d}\right) , where the set \mathcal{P}\left(\mathbb{R}^{d}\right) contains all Borel probability measures over \mathbb{R}^{d} . The particle dynamics are driven by two forces: a drift term, forcing particles to move towards the consensus point v_{\alpha}(\rho_{t}^{N}) , and a diffusion term, allowing random exploration of the search space, see [ 49 , 54 ] for a detailed description. The consensus point v_{\alpha}(\rho_{t}^{N}) is calculated by the weighted average v_{\alpha}(\rho_{t}^{N}):=\frac{1}{\sum_{i=1}^{N}\omega_{f}^{\alpha}\left(X_{t}^{i}\right)}\sum_{i=1}^{N}X_{t}^{i}\omega_{f}^{\alpha}\left(X_{t}^{i}\right), (3) where we denote by \rho_{t}^{N} the empirical measure \frac{1}{N}\sum_{i=1}^{N}\delta_{X_{t}^{i}} . The weight \omega_{f}^{\alpha} is defined as \omega_{f}^{\alpha}(x)=\exp(-\alpha f(x)),\quad\alpha>0, (4) which assigns higher weights to lower objective function values f(\cdot) . As a result, particles with lower function values have a stronger influence on both v_{\alpha}(\rho_{t}^{N}) and the motion of the rest of the particles. Due to Laplace’s principle from large deviations theory [ 23 ] , we expect v_{\alpha}(\rho_{t}^{N}) to approximate the global minimum of the particle system when \alpha is large enough, i.e., \lim_{\alpha\rightarrow\infty}v_{\alpha}(\rho_{t}^{N})\approx\operatorname{argmin}_{i=1,\ldots,N}f\left(X_{t}^{i}\right). A very relevant feature of CBO methods, as opposed to traditional metaheuristics, is the fact that they are amenable to rigorous convergence analysis in the mean-field, long-term evolution, limit [ 18 , 35 , 29 , 51 ] . Recent extensions of CBO include constrained optimization [ 14 , 30 , 10 , 19 ] , multi-objective optimization [ 13 , 43 ] and multi-level optimization [ 34 , 56 , 15 ] . Also, variants such as CBO with jump-diffusions [ 41 ] , adaptive momentum [ 36 ] , personal best information [ 55 ] and polarization [ 17 ] have been proposed to improve its performance. In this paper, we will study a novel variant of the CBO algorithm, which we refer to as controlled-CBO . By borrowing a leaf from optimal control theory, we enhance robustness and convergence towards global minimizers by introducing a feedback control term. A control-theoretical approach to global optimization The connection between control theory and global optimization has gained considerable attention over the last years. Most notably, in Chaudhari et al. [ 20 ] , Hamilton-Jacobi-Bellman (HJB) PDEs arising from dynamic programming and optimal feedback control have been studied as a tool for convexification. More recently, Bardi and Kouhkouh [ 5 ] formulated an eikonal-type HJB equation for global optimization using weak Kolmogorov-Arnold-Moser (KAM) theory and a small-discount approximation. The solution, represented as the value function of an optimal control problem, yields optimal trajectories that converge to a global minimizer of the problem ( 1 ) without computing the gradient of the objective function. In the following, we present a deterministic, infinite horizon, discounted formulation of the global-optimization-as-optimal-control approach. Consider a control system where the control variable u(\cdot) governs the state trajectory y(t)\in\mathbb{R}^{d} through the dynamics \dot{y}=u(t),\quad u(\cdot)\in\mathcal{U},\quad y(0)=x. (5) Here, the control lies in the set \mathcal{U}:=\left\{u(t):\allowbreak\mathbb{R}_{+}\mapsto\mathbb{R}^{d},\text{Lebesgue measurable a.e. in }t\right\} and x\in\mathbb{R}^{d} is a given initial condition. To quantify the performance of the control, we consider an objective function \mathcal{J}\left(u(\cdot),x\right):=\int_{0}^{\infty}e^{-\mu t}\left(f\left(y(t)\right)+\frac{\epsilon}{2}|u(t)|^{2}\right)dt, where \mu>0 is a discount factor and \epsilon>0 is a parameter for Tikhonov regularization. Then, the optimal control is obtained by solving the time-homogeneous, discounted infinite horizon optimal control problem \min_{u(\cdot)\in\mathcal{U}}\mathcal{J}\left(u(\cdot),x\right)\quad\text{subject to }\lx@cref{creftype~refnum}{control}. (6) It is well-known (e.g. [ 28 , Section II.11] ) that the optimal value function V\left(x\right)=\inf_{u(\cdot)\in\mathcal{U}}\mathcal{J}\left(u(\cdot),x\right) is the unique viscosity solution to the stationary Hamilton-Jacobi-Bellman (HJB) equation: -\mu V(x)+\min_{u\in\mathbb{R}^{d}}\left\{DV(x)^{\top}u+f(x)+\frac{\epsilon}{2}|u|^{2}\right\}=0, (7) with DV=\left(\partial_{x_{1}}V,\ldots,\partial_{x_{d}}V\right)^{\top} . Once the HJB equation eq. 7 is solved, the optimal control u^{*} of eq. 7 is given in feedback form by u^{*}(x):=\underset{u\in\mathbb{R}^{d}}{\operatorname{argmin}}\left\{DV(x)^{\top}u+f(x)+\frac{\epsilon}{2}|u|^{2}\right\}=-\frac{1}{\epsilon}DV(x), (8) which depends only on the current state x=x(t) (the initial condition for the remaining horizon) along a trajectory. The control law utilizes gradient information DV from the value function, obtained from the solution of the HJB PDE, rather than directly fetching the gradient of the objective f . Remark 1 . There are interesting connections between the optimal control problem defined in eq. 5 -( 8 ) and the global minimization ( 1 ) at the limit when the discount factor \mu\rightarrow 0 . In this regime, [ 5 ] shows (for \varepsilon= 1) that the PDE ( 7 ) converges to \min f+\frac{1}{2}|DV(x)|^{2}=f(x) , and the system governed by \dot{y}=-\frac{DV}{|DV|} converges to a global minimizer in finite time. Although establishing a rigorous connection with our approach lies beyond the scope of this work, one may interpret the control term in eq. 8 , for small values of \mu>0 , as a relaxation of the strategy proposed in [ 5 ] .