How to relax logical constraints 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.
 A: I don't think you will be able to relax this without binary variables. Let $m=1$ and let $g(x,\tilde{x})=x+\tilde{x}$. Assuming no sign restrictions on the variables (and no other constraints), your feasible region consists of a double cone: $\lbrace (x, \tilde{x}) : x \ge |\tilde{x}| \rbrace \cup \lbrace (x,\tilde{x}) : x \le -|\tilde{x}| \rbrace$. The convex hull of that union is all of $\mathbb{R}^2$, so any linear relaxation (which would yield a convex superset of the original feasible region) would encompass the entire space and be worthless.
A: $\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

*

*the starting point can be choosen by the other reasons (for example, via the hypotheses approach);

*the previous optimal solutions should be used as the base point for the more accurate linear approximation of $b(x,\tilde x),$ with the further calculations via linear model.

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.
