Minimizar $\|x\|_\infty$ tal que $Ax=b$

Question

He a $A \in \mathbb{R^{n,m}}$ $n\leq m$ y $b \in \mathbb{R^{n}}$. $A$ es de rango $n$ (máximo posible de clasificación).

Estoy buscando a $x \in\mathbb{R^{m}}$ tal que $Ax=b$ y para el que $\|x\|_\infty$ es mínima.

Algunos mirando alrededor de la Internet me dice que la solución sería $x= (AA^T)^{-1}A^Tb$ si yo estuviese interesado en minimizar $\|x\|_2$, pero estoy muy interesado en minimizar $\|x\|_\infty$.

Si que puede ayudar a dar una información más detallada de la solución, el caso que yo estoy particularmente interesada en el es $(n,m)=(3,4)$.

¿Ves cómo resolver este problema ?

Answer 1

Observar que $\|x\|_\infty = \min_z \{z : -z \leq x_i \leq z \ \text{for} \ i = 1,\dots, m\}$. Por lo tanto

$$\min_{\{x_i\}}\{\|x\|_\infty : Ax = b\} = \min_{\{x_i\},z}\{z : Ax = b, -z \leq x_i \leq z \}$$ Este es un problema de programación lineal:

$$\min z \\ s.t. \ -z \leq x_i \leq z \\ \quad \sum_j A_{ij}x_j = b_i \tag{1}$$ En la mayoría de los casos (1) no se puede resolver analíticamente, pero puede ser fácilmente resuelto numéricamente, incluso para problemas muy grandes.