提出高效算法全局优化高斯过程后验均值,适合大规模数据场景。
An Efficient Spatial Branch-and-Bound Algorithm for Global Optimization of Gaussian Process Posterior Mean Functions

- 用分段线性松弛与解析上界结合,构建可缩放的下界框架
- 在上千个训练点下仍保持求解效率,优于传统全局优化器
- 适用于需要精确全局最优的高斯过程建模任务
本文研究在超矩形域上对训练好的高斯过程后验均值函数进行确定性全局优化。尽管后验均值具有紧凑的闭式表达,但其非线性与非凸性使其优化极具挑战。现有精确方法随训练样本数增加而难以扩展,导致采用近似目标函数的启发式方法。本文提出PALM-Mean,一种嵌入降维空间分支定界法的分段解析下界框架。在每个节点中,局部重要的核项被替换为符号感知的分段线性松弛(基于标量距离变量),其余项则以闭式解析方式界定。该混合方法生成有效的后验均值下界,同时限制子问题规模。我们证明了节点下界的有效性及算法的ε-全局收敛性。在合成基准与真实应用问题上的计算结果表明,相比代表性通用确定性全局求解器,PALM-Mean在训练数据点增多时显著提升可扩展性。
原文摘要 · Abstract (English)
We study the deterministic global optimization of trained Gaussian process posterior mean functions over hyperrectangular domains. Although the posterior mean function has a compact closed-form representation, its global optimization is challenging because it remains nonlinear and nonconvex. Existing exact deterministic approaches become increasingly difficult to scale as the number of training data points grows, leading to approximation-based methods that improve tractability by optimizing a modified (inexact) objective. In this work, we propose PALM-Mean, a piecewise-analytic lower-bounding framework embedded in reduced-space spatial branch-and-bound. At each node, kernel terms that are locally important are replaced by a sign-aware piecewise-linear relaxation in an appropriate scalar distance variable, while the remaining terms are bounded analytically in closed form. We show this hybrid approach yields a valid lower bound for the posterior mean, while limiting the size of the branch-and-bound subproblems. We establish validity of the node lower bounds and $\varepsilon$-global convergence of the resulting algorithm. Computational results on synthetic benchmarks and real-world application problems show that PALM-Mean improves scalability relative to representative general-purpose deterministic global solvers, particularly as the number of training data points increases.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。