Facet Enumeration
BellScenario.LocalPolytope.facets — Functionfacets(
vertices :: Vector{Vector{Int64}};
dir = "./" :: String,
cleanup=true :: Bool
) :: Dict{String, Vector{Vector{Int64}}}Computes the facet inequalities and equalities which bound the convex polyhedron defined by the set of vertices. If the optimal representation is used for the vertices, then no equalitities will be present. For example, if the "generalized" vertex representation is used the normalization constraints will be included in the resulting equalities. The output of this method is structured:
Dict(
"facets" => inequalities, # :: Vector{Vector{Int64}}
"equalitites" => equalities, # :: Vector{Vector{Int64}}
)Facet inequalities and equalities are represented as single vector f where f[1:(end-1)] contains the coefficients of the linear inquality and f[end] is the bound. Facet inequalities and equalities act upon a vertex v where inequalities are arranged such that there is an implicit f[1:(end-1)]' * v ≤ f[end] and equalities are arranged such that f[1:(end-1)]' * v == f[end]
Vertex -> facet transformations are notoriously difficult computational problems. The performance limits of this method will be met far before the limits the vertex enumeration methods.
facets(poly::Polyhedron) :: Vector{Vector{Int64}}Returns the facets of the local polytope poly. If the facets have not already been computed, then they are transformed into the half-space representation from the vertex representation.
Linear Programming of Facets
BellScenario.LocalPolytope.linear_nonclassicality_witness — Functionlinear_nonclassicality_witness(
vertices :: Vector{Vector{T}} where T <: Real,
test_behavior :: Vector{<:Real};
verbose=false :: Bool
) :: Vector{Float64}Obtains a linear inequality $(\mathbf{G}^\star, \beta^\star)$ bounding the convex hull of the set of vertices ($\mathcal{V}$) and is violated by the test_behavior $(\mathbf{P}\notin \text{Conv}(\mathcal{V}))$. This task is achieved using the linear program described by Brunner et al. in Eq. 19 of https://arxiv.org/abs/1303.2849. The linear program is
\[\begin{align} \min_{(\mathbf{G}, \beta)} \quad & \langle \mathbf{G},\mathbf{P}\rangle - \beta & \notag\\ \text{s.t.} \quad & \langle \mathbf{G}, \mathbf{V} \rangle - \beta \leq 0 & \quad \forall \;\; \mathbf{V} \in \mathcal{V} \notag\\ & \langle \mathbf{G}, \mathbf{P} \rangle - \beta \leq 1 & \notag\\ \end{align}\]
The solution to the linear program is a linear nonclassicality witness $(\mathbf{G}^\star, \beta^\star)$ becuase the constraint $\lange\mathbf{G}^\star, \mathbf{V} \rangle - \beta^\star \leq 0$ ensures that no behavior in the polytope $\text{Conv}(\mathcal{V})$ can violate the inequality. Provided that $\mathbf{P} \notin \text{Conv}(\mathcal{V})$ technique the output linear inequality witnesses the nonclassicality of the test_behavior.
The optimized facet inequality $(\mathbf{G}^\star, \beta^\star)$ is returned as a vector $(G^\star_{0,0}, \dots, G^\star_{Y,X}, -\beta^\star)$ where $G^\star_{y,x}$ are the elements of $\mathbf{G}^\star$.
The linear programming software outputs numerical values that have numerical error. Moreover, the linear inequality is scaled such that the classical bound is zero and the test_behavior score is one. In order to convert the output inequality into a BellGame, care must be taken to obtain the correct scaling factor to ensure that elements are integers.
If the test_behavior $\mathbf{P}$ is classical, meaning it satisfies $\mathbf{P}\in\text{Conv}(\mathcal{V})$, then the zero vector is returned as the optimal solution. Note that if all elements of $\mathbf{G}^\star$ satisfy $G^\star_{y,x}=0$, then all behaviors $\mathbf{P} \in \text{Conv}(\mathcal{V})$ are trivially optimal as $\langle\mathbf{G}^{\star}, \mathbf{P} \rangle - \beta^\star \leq 0$.