Consider two $m\times 1$ vectors, $x\equiv (x_1,x_2,…,x_m),\tilde{x}\equiv (\tilde{x}_1,\tilde{x}_2,…,\tilde{x}_m)$.
Let $x\leq \tilde{x}$ if and only if $x_i\leq \tilde{x}_i$ for each $i=1,…,m$.
Lastly, consider a function $g(x,\tilde{x})\rightarrow\mathbb{R}$. $g$ is known and linear in both arguments.
Take the following logical constraints
$$
\text{If } x\geq \tilde{x}\text{, then } g(x,\tilde{x})\geq 0\\
\text{If } x\leq \tilde{x}\text{, then } g(x,\tilde{x})\leq 0\\
$$
Is there a way to relax these constraints such that they become linear in $x,\tilde{x}$?
In other words, do these logical constraints IMPLY some linear restrictions on $x,\tilde{x}$?
Remark: I know that a logical constraint can be equivalently rewritten using big-M modelling after having introduced some binary variables. This is not what I'm looking for because it requires the introduction of binary variables. I'm looking for implications of the logical constraints above that are linear in $x,\tilde{x}$ and that do not require the introduction of additional variables.
Best Answer
$\color{brown}{\textbf{Preliminary notes.}}$
In accordance with OP, let
$x = (x_1,x_2,\dots,x_m),\; \tilde x = (\tilde x_1, \tilde x_2,\dots,\tilde x_m),$
$x \le \tilde x\;\; \overset{\text{ def }}{\equiv\!\equiv}\;\; (x_1 \le \tilde x_1)\wedge(x_2 \le \tilde x_2)\wedge\dots\wedge(x_m \le \tilde x_m),$
$x \ge \tilde x\;\; \overset{\text{ def }}{\equiv\!\equiv}\;\; (x_1 \ge \tilde x_1)\wedge(x_2 \ge \tilde x_2)\wedge\dots\wedge(x_m \ge \tilde x_m),$
$x <> \tilde x \;\; \overset{\text{ def }}{\equiv\!\equiv}\;\; \overline{x \le \tilde x}\wedge\overline{x \ge \tilde x}.$
Looks possible to use the intervals method, when the conditional constraints \begin{cases} g(x,\tilde{x})\ge 0,\;\text{if } x \ge \tilde{x}\\[4pt] g(x,\tilde{x})\le 0,\;\text{if } x \le \tilde{x}\\[4pt]\tag1 \end{cases} can be considered in the form of the hypotheses $$ H_1 \equiv x\le \tilde{x},\quad H_2 \equiv x <> \tilde{x},\quad H_3 \equiv x\ge \tilde{x},\tag2 $$ which should be assumed a priory and checked a posteriory.
On the other hand, the conditions $(1)$ can be presented in the alternative form of $$-b(x,\tilde x)\le g(x,\tilde x)\le b(\tilde x,x),\tag3$$ where
\begin{cases} b(x,\tilde x)=0,\;\text{ if } x\le \tilde{x}\\[4pt] b(x,\tilde x) > |g(x,\tilde x)|,\;\text{ otherwize}.\tag4 \end{cases}
Let us try
to convert the conditional function $(4)$ into the unconditional algebraic form;
to convert obtained function into the linear form.
$\color{brown}{\textbf{Algebraic simulation of the logic constraints.}}$
Assume WLOG $\forall(i=1\dots m)\; x_i > 0,\;\tilde x_i \ge 0.$
Then
$$\left(x \le \tilde x\right) \;\equiv\; \left(\min\limits_{i=1\dots m}\left(\dfrac{\tilde x_i}{x_i}\right) \ge 1\right).\tag5$$
At the same time, if $r1>0, r_2 >0,\dots r_m>0,$ then $$\min(r_1,r_2,\dots r_m) = \lim\limits_{t \to -\infty}M(t,r),$$ where $$M(t,r) = \left(\dfrac1m\sum\limits_{i=1}^m r_i^t\right)^{\large\frac1t}$$ is the generalized mean. Therefore, the expression $$b(x,\tilde x) = A\sum\limits_{i=1}^m\dfrac{x_i^k}{\tilde x_i^k},\quad(k\gg1)\tag6$$ should provide suitable algebraic simulation of $(4),$ if the parameters $A,k$ are choosen accurately.
$\color{brown}{\textbf{Linearization of the algebraic constraints.}}$
Constraints $(6)$ are essentially unlinear, so the linearization should be considered as the part of the iterative method, where
Since $$\dfrac{\partial}{\partial x_i}b(x,\tilde x) = A k\dfrac{x_i^{k-1}}{\tilde x_i^k},$$ $$\dfrac{\partial}{\partial \tilde x_i}b(x,\tilde x) = -A k\dfrac{x_i^k}{\tilde x_i^{k+1}},$$
then the linear approximation of $b(x,\tilde x)$ is possible near the arbitrary nonzero vectors $x,\tilde x$ (see also Gradient descent).
Despite the iteration process should converge to solution under the algebraic constraints, this claim should be confirmed in the practice.