# Proving an optimization problem from continuous input to binary is optimal

Suppose we have a function $$f(x,y,z)$$ where the inputs are uniform from 0 to 1. The output is either $$+1$$ or $$-1$$. And there is a partial symmetry $$f(x,y,z) = f(z,y,x)$$.

Tell me what the minimum of this expression is over all functions $$f$$: $$E[f(a,b,c)f(b,c,d) + f(a,b,c) f(c,d,e)]$$

One way you can view this problem is finding the optimal "filling" of a cube, where the "filling" corresponds to the $$+1$$ region(s).

I am quite sure the optimal value is $$-4/9 + 1/12 = -13/36$$, with the associated function $$f' = 1$$ iff $$2b > a+c$$ and $$-1$$ otherwise. I think I can prove it is optimal among fillings that are half-spaces (imagine a plane cutting through the cube, and filling one side). But how can I prove this is optimal among all such functions $$f$$?

I've run numerics, discretizing each input to $$n\le 5$$ points, that suggest the optimal value is at most (but not too far from) $$-0.3$$.

• Letting $g(a,b) = E_c f(a,b,c)$, then the problem is equivalent to min $E_{a,b} g(a,b)g(b,a) + E_a (E_b g(a,b))^2$ subject to $|g(a,b)| \leq 1$. This is a quadratic programming problem over an (infinite dimensional) hypercube, which is NP-hard in general, but maybe there is a simple way to show that half-spaces are optimal? Jan 5, 2022 at 18:30