Cómo relajar las restricciones lógicas

Question

Considere dos $m\times 1$ vectores, $x\equiv (x_1,x_2,...,x_m),\tilde{x}\equiv (\tilde{x}_1,\tilde{x}_2,...,\tilde{x}_m)$ .

Dejemos que $x\leq \tilde{x}$ si y sólo si $x_i\leq \tilde{x}_i$ para cada $i=1,...,m$ .

Por último, consideremos una función $g(x,\tilde{x})\rightarrow\mathbb{R}$ . $g$ es conocido y lineal en ambos argumentos.

Tome las siguientes restricciones lógicas $$ \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\\ $$

¿Existe una forma de relajar estas restricciones de manera que se conviertan en lineales en $x,\tilde{x}$ ?

En otras palabras, ¿estas restricciones lógicas IMPULSO algunas restricciones lineales en $x,\tilde{x}$ ?

Observación: Sé que una restricción lógica se puede reescribir de forma equivalente utilizando la modelización big-M después de haber introducido algunas variables binarias. Esto no es lo que estoy buscando porque requiere la introducción de variables binarias. Estoy buscando implicaciones de las restricciones lógicas anteriores que sean lineales en $x,\tilde{x}$ y que no requieren la introducción de variables adicionales.

Answer 1

No creo que puedas relajar esto sin variables binarias. Deje que $m=1$ y que $g(x,\tilde{x})=x+\tilde{x}$ . Suponiendo que no hay restricciones de signo en las variables (y ninguna otra restricción), su región factible consiste en un doble cono: $\lbrace (x, \tilde{x}) : x \ge |\tilde{x}| \rbrace \cup \lbrace (x,\tilde{x}) : x \le -|\tilde{x}| \rbrace$ . El casco convexo de esa unión es todo $\mathbb{R}^2$ por lo que cualquier relajación lineal (que produciría un superconjunto convexo de la región factible original) abarcaría todo el espacio y no tendría ningún valor.

Answer 2

$\color{brown}{\textbf{Preliminary notes.}}$

De acuerdo con OP, dejemos

• $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}.$

Parece posible utilizar el método de los intervalos, cuando las restricciones condicionales \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} puede considerarse en forma de hipótesis $$ H_1 \equiv x\le \tilde{x},\quad H_2 \equiv x <> \tilde{x},\quad H_3 \equiv x\ge \tilde{x},\tag2 $$ que debe ser asumido como un priorato y comprobado como un posteriory.

Por otro lado, las condiciones $(1)$ puede presentarse en la forma alternativa de $$-b(x,\tilde x)\le g(x,\tilde x)\le b(\tilde x,x),\tag3$$ donde

\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}

Intentemos

• para convertir la función condicional $(4)$ en la forma algebraica incondicional;

• para convertir la función obtenida en la forma lineal.

$\color{brown}{\textbf{Algebraic simulation of the logic constraints.}}$

Supongamos que WLOG $\forall(i=1\dots m)\; x_i > 0,\;\tilde x_i \ge 0.$

Entonces
$$\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$$

Al mismo tiempo, si $r1>0, r_2 >0,\dots r_m>0,$ entonces $$\min(r_1,r_2,\dots r_m) = \lim\limits_{t \to -\infty}M(t,r),$$ donde $$M(t,r) = \left(\dfrac1m\sum\limits_{i=1}^m r_i^t\right)^{\large\frac1t}$$ es la media generalizada. Por lo tanto, la expresión $$b(x,\tilde x) = A\sum\limits_{i=1}^m\dfrac{x_i^k}{\tilde x_i^k},\quad(k\gg1)\tag6$$ debe proporcionar una simulación algebraica adecuada de $(4),$ si los parámetros $A,k$ se eligen con precisión.

$\color{brown}{\textbf{Linearization of the algebraic constraints.}}$

Restricciones $(6)$ son esencialmente no lineales, por lo que la linealización debe considerarse como la parte de la método iterativo , donde

• el punto de partida puede ser elegido por las otras razones (por ejemplo, a través del enfoque de las hipótesis);
• las soluciones óptimas anteriores deben utilizarse como punto de base para la aproximación lineal más precisa de $b(x,\tilde x),$ con los cálculos posteriores a través del modelo lineal.

Desde $$\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}},$$

entonces la aproximación lineal de $b(x,\tilde x)$ es posible cerca de los vectores arbitrarios no nulos $x,\tilde x$ (véase también Descenso gradual ).

A pesar de que el proceso de iteración debería converger a la solución bajo las restricciones algebraicas, esta afirmación debería confirmarse en la práctica.