Convertir un programa de valor absoluto en un programa lineal

Question

Tengo el problema de optimización genérico:

$$ \max c^T|x|$$

$$ \text{s.t. } Ax \le b $$

$x$ no tiene restricciones

¿Cómo lo convierto en un problema de programación lineal?

En Internet he leído algo sobre dejar $x$ igual a la diferencia de 2 números positivos, pero no pude comprender intuitivamente por qué funcionaba. Además, el ejemplo sólo se aplicaba a problemas de minimización en los que el $c^T$ las entradas son todas mayores que $0$ .

Estoy un poco atascado

Answer 1

Creo que la pregunta que usted está tratando de hacer es la siguiente: Si tenemos un conjunto de restricciones lineales que implican una variable $x$ ¿Cómo podemos introducir $|x|$ (el valor absoluto de $x$ ) en la función objetivo?

Este es el truco. Añade una restricción de la forma $$t_1 - t_2 = x$$ donde $t_i \ge 0$ . El Algoritmo Simplex establecerá $t_1 = x$ y $t_2 = 0$ si $x \ge 0$ ; de lo contrario, $t_1 = 0$ y $t_2 = -x$ . Así que $t_1 + t_2 =|x|$ en cualquier caso.

A primera vista, este truco no debería funcionar, porque si tenemos $x = -3$ Por ejemplo, parece que hay muchas posibilidades de $t_1$ y $t_2$ que no sea $t_1 = 0$ y $t_2 = 3$ por ejemplo, $t_1 = 1$ y $t_2 = 4$ parece ser una posibilidad. Pero el Algoritmo Simplex nunca elegirá una de estas soluciones "malas" porque siempre elige un vértice de la región factible, aunque haya otras posibilidades.

EDICIÓN añadida el 29 de marzo de 2019

Para que este truco funcione, el coeficiente del valor absoluto en la función objetivo debe ser positivo y se debe estar minimizando, como en

min $2(t_1+t_2)+\dots$

o el coeficiente puede ser negativo si se está maximizando, como en

max $-2(t_1+t_2)+\dots$

De lo contrario, se termina con una función objetivo no limitada, y el problema debe ser resuelto por otros métodos, por ejemplo, la programación entera-lineal mixta.

(Si lo sabía antes, lo había olvidado. Gracias a Discretelizard por señalármelo).

Answer 2

Me doy cuenta de que esto es viejo, pero acabo de encontrarme con este problema. Por favor, vea: http://lpsolve.sourceforge.net/5.1/absolute.htm que tiene una gran explicación de la solución (tanto para la minimización como para la maximización de un valor absoluto), y me ayudó mucho.

Answer 3

Una forma más sencilla: si todos los $c_i$ son no negativos, es posible reformular el problema como

$\min c^T y$

$ y_i\leq x_i$

$ y_i\geq -x_i$

$Ax \leq b$

Si $c_i$ tienen el mismo signo se puede adaptar fácilmente la misma idea. Supongo que también se puede tratar el caso del signo genérico.

Answer 4

Llego bastante tarde a la fiesta, pero todas las respuestas actuales pasan por alto un punto importante. Las respuestas dadas aquí exponen trucos para convertir un $L^1$ -en un programa lineal, introduciendo una o más variables auxiliares. Si $A$ es cuadrado esto no es el fin del mundo. El algoritmo simplex se ejecuta en $O(n^3)$ en un caso medio, por lo que introducir una variable auxiliar multiplica el tiempo de ejecución por 8. Malo pero no horrible. Sin embargo, si su $L^1$ es, por ejemplo

$$ \text{minimize} \hspace{0.5em} \lVert b - Ax \rVert_1 \hspace{0.5em} \text{s.t.} \hspace{0.5em} x \geq 0 $$

con $x \in \mathbb{R}^{100}$ y $A \in M_{64000 \times 100}(\mathbb{R})$ entonces al convertirlo en un programa lineal has aumentado la dimensionalidad en un factor de (más de) 640, aumentando el tiempo de ejecución en un factor de más de un cuarto de millón.

Existen algoritmos especiales para aproximar $L^1$ -minimización que tienen tiempos de ejecución que dependen de la dimensionalidad de la variable "intrínseca", en contraposición a la variable "trucada". Emmanuel Candés tiene uno en su sitio web; otro lo proporciona el paquete de Python CVXOPT.

Answer 5

$$ min |X_a-X_b| $$ puede escribirse como

$$ min (X_{ab1}+X_{ab2}) $$

De tal manera que

$$ X_a -X_b = X_{ab1} - X_{ab2}; $$

$$ X_{ab1}, X_{ab2} >=0; $$