Given a positive integer $n$, a constant $k=2/3$, and $7$ variables $x_1, x_2, x_3, x_{12}, x_{13}, x_{23}, x_{123}$ (non-negative reals or integers) I would like to find:
$$\min \binom{x_1}2$$
subject to:
$$\binom{x_1}2 \ge \binom{x_2}2 \ge \binom{x_3}2 \tag{1}$$
$$\binom{n}2 \ge \binom{x_1}2+\binom{x_2}2+\binom{x_3}2-\binom{x_{12}}2-\binom{x_{23}}2-\binom{x_{13}}2 \ge k\binom{n-1}2 \tag{2}$$
$$\binom{x_1}2 \ge \binom{x_{12}}2+\binom{x_{13}}2 \ge k\binom{x_1-1}2 \tag{3}$$
$$\binom{x_2}2 \ge \binom{x_{12}}2+\binom{x_{23}}2 \ge k\binom{x_2-1}2 \tag{4}$$
$$\binom{x_3}2 \ge \binom{x_{13}}2+\binom{x_{23}}2 \ge k\binom{x_3-1}2 \tag{5}$$
$$x_1+x_2+x_3-x_{12}-x_{13}-x_{23}+x_{123} = n \tag{6}$$
This is a starting example, because from this I would like to solve the natural extension of the problem with $2^q-1$ variables, $q \gt 3$.
If we remove $(6)$ from the problem and we could replace $\binom{x_1-1}2, \binom{x_2-1}2, \binom{x_3-1}2$ with $\binom{x_1}2, \binom{x_2}2, \binom{x_3}2$ on the RHS of $(3), (4), (5)$ and then set $y_1=\binom{x_1}2, y_2=\binom{x_2}2, y_3=\binom{x_3}2, y_{12}=\binom{x_{12}}2, y_{13}=\binom{x_{13}}2, y_{23}=\binom{x_{23}}2, y_{123}=\binom{x_{123}}2$ we would get a linear program. Unfortunately, we can't do that, that's why we have a "nearly" linear program.
One idea that came to mind is that e.g.:
$$k\binom{x_1-1}2 = k\frac{x_1-2}{x_1}\binom{x_1}2 \ge \frac{2}{3}k\binom{x_1}2$$
when $x_1 \ge 6$, therefore we could replace the RHS for $x_1 \ge 6$ and enumerate all the possible values of $x_1$ for $x_1 \lt 6$, but we would have another $6$ linear programs to solve. If we fix $\binom{x_2-1}2$ and $\binom{x_3-1}2$ in the same way, the additional programs to solve would be $6^3 = 216$. That will be much bigger for $q \gt 3$.
Another idea is keep $(6)$, then use the identity:
$$\binom{x_1-1}2=\binom{x_1}2-x_1+1$$
however, with this one we would need a way to enforce the relation between $y_1 = \binom{x_1}2$ and $x_1$, i.e. linearize:
$$y_1 = \frac{x_1(x_1-1)}2$$
Any idea or suggestion?
