Intro: I have a non-convex set, defined by conditional constraints, that is infeasible to construct exactly. I would like your help to characterise a superset of this set that can be feasibly obtained.
I now present my problem more precisely.
For each $j\in \{1,...,J\}$, consider a linear function $F_j: \mathbb{R}^K\rightarrow \bar{\mathbb{R}}^M$, where $\bar{\mathbb{R}}$ denotes the extended real line. For example, for $J=2$, $K=2$, $M=3$, and $x\equiv (x_1,x_2)\in \mathbb{R}^2$, we could have $$ F_1(x)\equiv \begin{pmatrix} x_1+x_2\\ \infty\\ x_1 \end{pmatrix}, \hspace{1cm}F_2(x)\equiv \begin{pmatrix} x_1-x_2\\ -\infty\\ x_2 \end{pmatrix}. $$ [In my actual case, $J=15$, $K=20$, $M=3$].
Fix $x\in \mathbb{R}^K$ and let $F(x)$ be the $M^J\times J$ matrix where each $1\times J$ row takes one element from $F_1(x)$, one element from $F_2(x)$,..., one element from $F_J(x)$. For instance, continuing the above example: $$ F(x)\equiv \begin{pmatrix} x_1+x_2 && x_1-x_2\\ \infty && x_1-x_2\\ x_1 && x_1-x_2\\ x_1+x_2 && -\infty\\ \infty && -\infty\\ x_1 && -\infty\\ x_1+x_2 &&x_2\\ \infty &&x_2\\ x_1 &&x_2\\ \end{pmatrix} $$
[In my actual case, the length of $F(x)$ is $15^{3}=3375$].
Let $[F(x)]_i$ denote the $i$-th row of the matrix $F(x)$.
Let $\mathcal{A}$ be the list of all possible unordered pairs $(i,h)$, where $i\in \{1,...,M^J\}$, $h\in \{1,...,M^J\}$, $i\neq h$.
Note that $\mathcal{A}$ has cardinality $\binom{M^J}{2}$.
In my actual case, the cardinality of $\mathcal{A}$ is $\approx Inf$.
Consider a function $Q: \mathcal{A}\rightarrow \{0,1\}^L$. That is, for every $(i,h)\in \mathcal{A}$, $Q(i,h)$ is a $1\times L$ vector of zeros and ones.
For a given $x\in \mathbb{R}^K$, consider the following inequalities with unknown $q\in \mathbb{R}^L$: \begin{aligned} (1)\hspace{1cm}&\forall (i,h)\in \mathcal{A}\\ &\text{If $[F(x)]_i\leq [F(x)]_h$, then } Q(i,h)\times q \leq 0,\\ &\text{If $[F(x)]_i\geq [F(x)]_h$, then } -Q(i,h)\times q \leq 0. \end{aligned}
(As a side note: $[F(x)]_i\leq [F(x)]_h$ iff each element of the row vector $[F(x)]_i$ is smaller than the corresponding element of the row vector $[F(x)]_h$)
Now, suppose we want to obtain the projection of the set $$ (2) \hspace{1cm} \mathcal{X}\equiv \{x\in \mathbb{R}^K: (1) \text{ is feasible with respect to $q$}\}. $$ on its first dimension.
Constructing this projection is infeasible, when dealing with my actual dimensions.
To see this, just note that one could think of applying mixed integer programming via big-M modelling. However, this is infeasible when dealing with my actual dimensions because the number of auxiliary binary variables to introduce is infinite.
Hence, what I can try is to "approximate" the projection of $\mathcal{X}$ on its first dimension. One way to do that is by grid searching over $\mathbb{R}^K$. However, this is hard as in my actual case $K=20$.
Question: Are there other ways to approximate the projection for $x_1$ that are feasible when dealing with my actual dimensions?