提出优化双变量函数之和的新方法，可在有限域上高效求解复杂优化问题。
Optimization of Sums of Bivariate Functions: An Introduction to Relaxation-Based Methods for the Case of Finite Domains
- 基于测度松弛与熵正则化，将复杂优化转化为可解的线性规划或闭式解。
- 证明该类问题在有限域上为NP等价，但存在可利用的简化机会。
- 适用于图着色、信号重构等实际问题，尤其适合结构清晰的组合优化场景。
我们研究在有限域上对具有 n>2 个变量的函数进行优化，这些函数可表示为仅含两个变量的若干子函数之和，即双变量函数之和。证明此类优化问题为NP等价，并揭示其存在“免费午餐”——即可通过合理松弛获得可解近似。基于目标函数的测度值扩展（即松弛）、ℓ²逼近与熵正则化，我们推导出若干可通过线性规划、坐标上升或闭式解求解的可处理形式。通过一般性结果分析从二阶边缘重构测度的限制，进一步探究了此类松弛在双变量函数之和上的适用边界。实验中将所提算法应用于随机函数、顶点着色与信号重建问题，揭示了可建模为双变量函数之和的不同函数类别所呈现的定性差异。
原文摘要 · Abstract (English)
We study the optimization of functions with $n>2$ arguments that have a representation as a sum of several functions that have only $2$ of the $n$ arguments each, termed sums of bivariates, on finite domains. The complexity of optimizing sums of bivariates is shown to be NP-equivalent and it is shown that there exists free lunch in the optimization of sums of bivariates. Based on measure-valued extensions of the objective function, so-called relaxations, $\ell^2$-approximation, and entropy-regularization, we derive several tractable problem formulations solvable with linear programming, coordinate ascent as well as with closed-form solutions. The limits of applying tractable versions of such relaxations to sums of bivariates are investigated using general results for reconstructing measures from their bivariate marginals. Experiments in which the derived algorithms are applied to random functions, vertex coloring, and signal reconstruction problems provide insights into qualitatively different function classes that can be modeled as sums of bivariates.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。