L1 Objetivo como un Programa Lineal

Question

Estoy tratando de determinar cómo se puede escribir como un programa lineal el siguiente objetivo simple L1:

Minimizar $(\| Mx - p \|_1) + (\| Mx - q \|_1)$ con respecto a $x$ tal que $\| x \|_1 = 1$ y todos los elementos de $x$ son no negativos. $M$ es una matriz, y $x$, $p$ y $q$ son vectores columna. $\|\cdot\|_1$ es la norma L1.

Un programa lineal tiene la forma:

\begin{array}{ll} \text{Encuentra un vector} & \mathbf x \\ \text{que maximice} & \mathbf c^T\mathbf x \\ \text{sujeto a} & A\mathbf x \le \mathbf b \\ \text{y } & \mathbf x \ge \mathbf 0. \end{array}

Entonces, para aplicar la restricción de que $\| x \|_1 = 1$, $b = [1, -1]^T$ y $A$ sería una matriz con la primera fila siendo todos 1 y la segunda fila siendo todos -1. Pero, ¿cuál sería $c$?

Gracias por cualquier guía o retroalimentación.

Answer 1

Para representar $\|Mx-p\|_1$ en la función objetivo, queremos un término para el valor absoluto de $(Mx-p)_i$ (el componente $i^{\text{th}}$ de $Mx-p$).

$(Mx-p)_i$ en sí es una función lineal de $x$, pero su valor absoluto no lo es. Sin embargo, podemos pedir que $y_i \ge |(Mx-p)_i|$ al pedir que $y_i \ge (Mx-p)_i$ y $y_i \ge -(Mx-p)_i$. Aquí, $y_i$ es una variable nueva que introducimos solo para este componente de la función objetivo.

Cuando hacemos esto para todos los componentes $n$ de $Mx-p$, tenemos las desigualdades vectoriales $y \ge Mx-p$ y $y \ge -(Mx-p)$. Estas pueden expresarse en forma de matriz de bloques como $$ \begin{bmatrix} M & -I \\ -M & -I \end{bmatrix} \begin{bmatrix}x \\ y\end{bmatrix} \le \begin{bmatrix}p \\ -p\end{bmatrix}. $$ Una vez que tenemos las variables $y_1, \dots, y_n$ definidas de esta manera, tenemos $y_1 + y_2 + \dots + y_n \ge \|Mx-p\|_1$, por lo tanto, cuando minimizamos, $y_1 + y_2 + \dots + y_n$ será igual a $\|Mx-p\|_1$.

Podemos manejar $\|Mx-q\|_1$ de manera similar, introduciendo un tercer vector variable $z$ (por lo que la matriz de desigualdades se volverá más ancha y alta). La función objetivo estará solo en términos de los vectores $y$ y $z$.

Answer 2

$\min \{ y_p+y_q | Mx-p \le y_p, -(Mx-p) \le y_p, Mx-q \le y_q, -(Mx-q) \le y_q, e^T x = 1, x \ge 0\}$, donde $e$ es un vector de unos.