Edit: Here is how the following sets are created:
$S$ is the set of all $n$-dimensional, multilinear trinomials that are strictly greater than $0$ on the interval $[0,1]^n$. $T$ are all miltilinear trinomials such that they are non-negative, but have a $0$ on said interval. I was contemplating expanding out my search criteria into making it polynomials, rather than multilinear trinomials to see if that becomes easier.
Say I have two particular sets of $n$ dimensional vectors $S, T \subset \mathbb{R}^n$. Given some vector $x$, I want to know if $x$ is on the interior of $S$. Here are some properties of my sets.
- $S$ and $T$ are disjoint sets. They also are both infinite.
- $S$ is bounded on one side, but does not include its boundary (imagine the right half plane). I believe that $T=\partial S$, but I'm not sure, so I'd only like to use this assumption if necessary.
- $S$ is a convex set. Not only that, it actually is also a convex hull being closed under positive scalar addition. I think this also more strongly classifies it as a convex cone as well.
- It is easy to generate new points in either $S$ or $T$
My question is if there is a known algorithm or method for determining whether a given vector $x$ is a member of the interior of $S$ given $S$ is a convex hull. If so, how many points would we need from $S$ to use to guarantee that our method works? I did a little research to see that the finite case can be reduced to linear programming, but I haven't seen anything for the infinite case.
Any help would be appreciated!
Let $S\subseteq \mathbb{R}[x_1,\ldots,x_n]$ be the set of multilinear polynomials with degree at most $3$ on $n$ variables. To expand on my comment, a polynomial $f\in S$ (or more generally, any multilinear polynomial) is nonnegative (positive) on $[0,1]^n$ if and only if it is nonnegative (positive) on $\{0,1\}^n$, so it suffices to check $2^n$ points. Note that $f$ is multilinear if and only if it can be written as $f(x)=\sum_{S\subseteq [n]} c_S \prod_{i\in S}x_i$. In your specific case, the sum is actually over all $S\subseteq [n]$ with $\vert S\vert\leq 3$.
One direction is immediate. To show this is sufficient, fix $x\in [0,1]^n$ and we will write $f(x)$ as a convex combination of the values on $\{0,1\}^n$. To do this, define a random variable $y=(y_1,\ldots,y_n)$ where the components are independent and $y_i=1$ with probability $x_i$ and is $0$ otherwise. Then $\mathbb{E}[y_i]=x_i$, and so \begin{equation} \mathbb{E}_y[f(y)]=\sum_{S\subseteq [n]} c_S \mathbb{E}[\prod_{i\in S} y_i]=\sum_{S\subseteq [n]} c_S \prod_{i\in S}\mathbb{E}[ y_i]=\sum_{S\subseteq [n]} c_S \prod_{i\in S} x_i=f(x). \end{equation} Note we use independence in the second equality. As $y$ is supported in $\{0,1\}^n$, this means $f(x)$ is a convex combination (average) of values on this subset, so if $f$ is nonnegative (positive) on all such points, it will be nonnegative (positive) on any $x\in [0,1]^n$. So to test membership in $S$, you can check just those $2^n$ points instead of infinitely many points.
As for can you do better in general; the answer is likely no. The reason is that testing the nonnegativity of multilinear polynomials on $\{0,1\}^n$ encodes many $NP$-hard problems. For instance, it is not too hard to write (a version of) the MAXCUT problem as a degree $2$ multilinear polynomial, so if you could determine whether a multilinear polynomial is nonnegative on $\{0,1\}^n$ in polynomial time, then you would have shown that $P=NP$.
In some cases, though, you might be able to certify nonnegativity faster. One method is the so-called sum-of-squares hierarchy; the idea is that if you can show your polynomial is equal to a sum of squares of other polynomials on $\{0,1\}^n$ (as in, takes the same values on that set), then it must be nonnegative on that set. If it can be written as a sum of squares of polynomials of degree at most $d/2$, then $f$ is said to have a certificate of nonnegativity of degree $d$. It is possible to show that every nonnegative multilinear polynomial on $\{0,1\}^n$ has such a certificate of degree at most $2n$. The amazing thing is that there is a way essentially using SDPs to determine in time $n^{O(d)}$ whether a given $f$ has such a certificate of nonnegativity of degree $d$, or a proof (sometimes called a pseudodistribution) that it doesn't. So in the cases that your $f$ has a low-degree certificate, it is possible to prove it in polynomial time (if $d$ is a constant i.e. does not grow with $n$). There is a lot of research now to determine the extent to which this framework can solve problems that are very likely computationally hard. These notes by Boaz Barak and David Steurer are pretty good if you're interested.