arXiv:2601.06434math.OCcs.AI2026-01中稿 · TMLR被引 3

首个基于梯度的切比雪夫中心求解框架,显著提升函数学习效率。

On a Gradient Approach to Chebyshev Center Problems with Applications to Function Learning

  • 将无穷维问题转化为有限维极小极大优化,支持梯度法求解
  • 在强凸范数下可精确恢复最优中心与半径,34个基准测试精度提升明显
  • 适用于大规模函数学习与凸半无限规划,适合需要高效稳定算法的研究者

我们提出 $ extsf{gradOL}$,首个基于梯度的切比雪夫中心求解框架,解决最优函数学习与几何优化中的核心难题。该方法将半无限问题重构成有限维极大极小优化,利用自动微分实现高精度梯度计算,确保数值稳定与可扩展性。在环境范数强凸条件下,$ extsf{gradOL}$ 可严格恢复最优切比雪夫中心并直接计算对应半径,克服了构建稳定最优插值函数的关键瓶颈。在 $ extsf{CSIP}$ 基准库中的34个切比雪夫中心问题上,$ extsf{gradOL}$ 显著提升准确率与效率。进一步拓展至一般凸半无限规划(CSIP),在含67个基准问题的 $ extsf{CSIP}$ 库上相比最先进求解器 $ exttt{SIPAMPL}$ 最快达4000倍加速。同时,首次为梯度法应用于切比雪夫中心问题建立理论基础,实现严谨分析与实用算法的融合。$ extsf{gradOL}$ 提供了统一求解框架,适用于切比雪夫中心及更广泛的CSIP问题。

原文摘要 · Abstract (English)

We introduce $\textsf{gradOL}$, the first gradient-based optimization framework for solving Chebyshev center problems, a fundamental challenge in optimal function learning and geometric optimization. $\textsf{gradOL}$ hinges on reformulating the semi-infinite problem as a finitary max-min optimization, making it amenable to gradient-based techniques. By leveraging automatic differentiation for precise numerical gradient computation, $\textsf{gradOL}$ ensures numerical stability and scalability, making it suitable for large-scale settings. Under strong convexity of the ambient norm, $\textsf{gradOL}$ provably recovers optimal Chebyshev centers while directly computing the associated radius. This addresses a key bottleneck in constructing stable optimal interpolants. Empirically, $\textsf{gradOL}$ achieves significant improvements in accuracy and efficiency on 34 benchmark Chebyshev center problems from a benchmark $\textsf{CSIP}$ library. Moreover, we extend $\textsf{gradOL}$ to general convex semi-infinite programming (CSIP), attaining up to $4000\times$ speedups over the state-of-the-art $\texttt{SIPAMPL}$ solver tested on the indicated $\textsf{CSIP}$ library containing 67 benchmark problems. Furthermore, we provide the first theoretical foundation for applying gradient-based methods to Chebyshev center problems, bridging rigorous analysis with practical algorithms. $\textsf{gradOL}$ thus offers a unified solution framework for Chebyshev centers and broader CSIPs.

优化算法切比雪夫中心梯度法函数学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。