Abstract:
We study the problem of the existence of a convex extension of any Boolean function $f(x_1,x_2,\dots,x_n)$ to the set $[0,1]^n$. A convex extension $f_C(x_1,x_2,\dots,x_n)$ of an arbitrary Boolean function $f(x_1,x_2,\dots,x_n)$ to the set $[0,1]^n$ is constructed. On the basis of a single convex extension $f_C(x_1,x_2,\dots,x_n)$, it is proved that any Boolean function $f(x_1,x_2,\dots,x_n)$ has infinitely many convex extensions to $[0,1]^n$. Moreover, it is proved constructively that, for any Boolean function $f(x_1,x_2,\dots,x_n)$, there exists a unique function $f_{DM}(x_1,x_2,\dots,x_n)$ being its maximal convex extensions to $[0,1]^n$.
Keywords:Boolean function, convex extension of a Boolean function, convex function, global optimization, local minimum.
Fulltext:
PDF file (632 kB)
