3
$\begingroup$

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.

  1. $S$ and $T$ are disjoint sets. They also are both infinite.
  2. $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.
  3. $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.
  4. 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!

$\endgroup$
  • $\begingroup$ How exactly is $S$ described/given to you? To run any sort of algorithm, presumably there's some sort of implicit description of $S$ via a set of inequalities or an oracle or something else... $\endgroup$ – J.G Aug 14 at 4:34
  • $\begingroup$ It is an interesting situation if you say that it is easy to generate points in $S$, but it is not easy to check membership in $S$. Does it not mean that the points you can generate are of some special, simple form, and therefore they are likely not to generate the whole $S$ too well? Or how does generating points in $S$ work? It would be helpful if you wrote more context. $\endgroup$ – Michal Adamaszek Aug 14 at 6:23
  • $\begingroup$ @JasonGaitonde I added descriptions of the sets hopefully that helps! $\endgroup$ – wjmccann Aug 14 at 21:43
  • $\begingroup$ @MichalAdamaszek Its not that I know it is not easy to check for membership in $S$, I just generally have no idea how one would go about checking membership in an infinite convex hull! I also added criteria for what makes up each set. How would one go about generating the entirety of $S$ from finite points? How many points would I need? $\endgroup$ – wjmccann Aug 14 at 21:44
  • $\begingroup$ Wait, sorry if I'm misunderstanding things, but $S$ is the set of all polynomials in $n$ variables that can be expressed as a linear combination of at most three monomials, such that the maximum degree of any variable in any monomial is at most $1$? If that's right, this isn't convex, as the convex combination of two such polynomials may not still be a trinomial... $\endgroup$ – J.G Aug 15 at 1:30
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.