Exact characterization conjecture for boundary hyperplane covers of quadratic sets

About 2 years old · traced to

Let B={x:∥x∥2≤1}B=\{\mathbf{x}:\|\mathbf{x}\|_2\leq 1\} and C={x:g(x)≤0}C=\{\mathbf{x}:g(\mathbf{x})\leq 0\}, where gg is a quadratic polynomial. Suppose that gg has one of the forms

g(x)=α(∑i=1nxi2−1)+h1(x)h2(x)g(\mathbf{x})=\alpha\left(\sum_{i=1}^n x_i^2-1\right)+h_1(\mathbf{x})h_2(\mathbf{x})

or

g(x)=α(∑i=1nxi2−1)+h1(x),g(\mathbf{x})=\alpha\left(\sum_{i=1}^n x_i^2-1\right)+h_1(\mathbf{x}),

where α≠0\alpha\neq 0 and the hih_i are non-trivial affine functions. Exact characterization conjecture. Theorem~ holds as an if and only if: BB and CC have a Boundary Hyperplane Cover if and only if gg has one of these two forms, with the hyperplanes given by hi(x)=0h_i(\mathbf{x})=0 as appropriate. The theorem supplies the sufficient direction; proving the converse requires algebraic tools to show that no other quadratic intersections have the Boundary Hyperplane Cover property.

References

Primary source

Robert Hildebrand and Adrian Göß, “Complexity of Integer Programming in Reverse Convex Sets via Boundary Hyperplane Cover”, arXiv:2409.05308 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.