Conversión de la suma de la norma del infinito y la norma L1 en programación lineal

Question

Así que estoy tratando de convertir este problema de minimización,

min $\parallel Ax-y \parallel_{\infty}$ + $\parallel x \parallel_{1}$ donde $A$ es $m$ por $n$ , $y$ es $m$ por $1$ y $x$ es $n$ por $1$ .

en un programa lineal. Mi intento de solución es reescribirlo como sigue,

$$\min\,\, t + \textbf{1}^T z : t \in R, z \in R^n $$ con sujeción a $$z \geq x$$ $$-z \leq x$$ $$\textbf{1}t \geq Ax - y$$ $$-\textbf{1}t \leq Ax - y$$

Sin embargo, tengo dudas sobre esta solución, ya que en cierto modo ignora la relación entre $z$ y $t$ y mi corazonada es introducir algún tipo de restricción para capturar esa relación. Sería estupendo si alguien pudiera confirmar mi respuesta o, si estoy equivocado, al menos indicarme la dirección correcta.

Answer 1

Esto es absolutamente correcto. ¡Bien hecho! No estás ignorando la relación entre $z$ y $t$ y el modelo lo capta de forma natural. El hecho de que ambos estén presentes en el objetivo garantiza que un aumento de uno debe ir acompañado de una disminución del otro. Es posible demostrar que en el punto óptimo debe sea el caso que $z_i=|x_i|$ , $i=1,2,\dots,n$ y $t=\|Ax-b\|_\infty$ .

Answer 2

Creo que lo mejor es hacer la conversión paso a paso. Básicamente, sólo se necesitan tres ingredientes para reformular un problema de minimización que implique la norma 1 o la norma sup en un problema de programación lineal. Estos son: \begin{align} \|v\|_1 &= \min_z (\mathbf{1}^T z) \quad \mathrm{s.t.}\; z\geq |v|\\ \|v\|_\infty &= \min_t t \quad \mathrm{s.t.}\; \mathbf{1}t\geq |v|\\ \min_{(u,v)} f(u,v) &= \min_u \min_v f(u,v) \end{align} para cualquier vector $v$ y $u$ , donde $\leq$ y $|\cdot|$ se toman como elementos. Todas ellas son triviales de demostrar (la forma es siempre $a=\min_{b\in B} b$ Así pues, muestra $a\leq b\,\forall b\in B$ y $a\in B$ ).

Introduciendo esto en su problema de minimización se obtiene \begin{align} \min_x \|Ax-y\|_\infty + \|x\|_1 &= \min_x (\min_z (\mathbf{1}^T z) \; \mathrm{s.t.}\; z\geq |Ax-y|)+ (\min_t t \; \mathrm{s.t.}\; \mathbf{1}t\geq |x|) \\ &= \min_{x,z,t} (\mathbf{1}^T z) + t \; \mathrm{s.t.}\; z\geq |Ax-y| \wedge \mathbf{1}t\geq |x|) \end{align} Ahora sólo hay que sustituir el $|u|$ -términos con desigualdades con desigualdades que implican $u$ y $-u$ y ya está. A partir de aquí también está claro que hay que minimizar sobre los tres variables $x$ , $z$ y $t$ y que $z$ y $t$ son parejas a través de $x$ .