将镜面下降思想融入共识优化,提升非凸问题求解能力
MirrorCBO: A consensus-based optimization method in the spirit of mirror descent
- 用对偶粒子群结合镜面映射,实现无梯度优化
- 在凸约束下收敛速度呈指数级,理论保障明确
- 适合稀疏优化与流形上优化,可选理想最小值
本文提出MirrorCBO,一种基于共识优化(CBO)的方法,其思想类似镜面下降对梯度下降的推广。通过在对偶粒子群上应用CBO,并利用强凸函数ϕ的次微分参数化镜面映射的逆,保留原始粒子位置。该方法融合了无梯度非凸优化与镜面下降的优势。作为特例,可处理带凸约束的优化问题。在ϕ对应的Bregman距离有界条件下,给出具有显式指数收敛率的渐近收敛结果。进一步的数值实验涵盖稀疏诱导优化与约束优化,表明MirrorCBO性能优异。实证发现其可应用于欧氏空间中的非凸子流形优化,适配其他近期CBO变体的镜面版本,并继承镜面下降选择理想最小值(如稀疏解)的能力。还综述了近期约束优化的CBO方法并进行对比。
原文摘要 · Abstract (English)
In this work we propose MirrorCBO, a consensus-based optimization (CBO) method which generalizes standard CBO in the same way that mirror descent generalizes gradient descent. For this we apply the CBO methodology to a swarm of dual particles and retain the primal particle positions by applying the inverse of the mirror map, which we parametrize as the subdifferential of a strongly convex function $ϕ$. In this way, we combine the advantages of a derivative-free non-convex optimization algorithm with those of mirror descent. As a special case, the method extends CBO to optimization problems with convex constraints. Assuming bounds on the Bregman distance associated to $ϕ$, we provide asymptotic convergence results for MirrorCBO with explicit exponential rate. Another key contribution is an exploratory numerical study of this new algorithm across different application settings, focusing on (i) sparsity-inducing optimization, and (ii) constrained optimization, demonstrating the competitive performance of MirrorCBO. We observe empirically that the method can also be used for optimization on (non-convex) submanifolds of Euclidean space, can be adapted to mirrored versions of other recent CBO variants, and that it inherits from mirror descent the capability to select desirable minimizers, like sparse ones. We also include an overview of recent CBO approaches for constrained optimization and compare their performance to MirrorCBO.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。