Optimization of Sums of Bivariate Functions: An Introduction to Relaxation-Based Methods for the Case of Finite Domains
This work addresses a fundamental computational challenge in optimization for domains like graph theory and signal processing, though it appears incremental in extending relaxation methods to bivariate sums.
The paper tackles the NP-equivalent problem of optimizing sums of bivariate functions on finite domains, showing that tractable relaxations based on measure extensions and entropy regularization can be solved with linear programming and coordinate ascent, with experiments applied to random functions, vertex coloring, and signal reconstruction.
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.