Minimización restringida de la norma del infinito

Question

Tengo un problema de este tipo:

$$\min_x |Ax|_\infty \text{ s.t. } \sum_i x_i = c$$

Es decir, quiero encontrar el vector $x$ cuyos elementos suman una constante $c$ que minimiza la norma del infinito de $Ax$ .

¿Tiene este problema un nombre concreto? No he podido encontrar una función para hacer algo así en cosas como lpsolve, glpk, etc. ¿Puede alguien sugerir un solucionador de c/c++ para este problema?

Answer 1

Como se menciona en los comentarios, el problema se puede replantear como

$$\min y \\ s.t. \quad y \geq |Ax|_i \\ \quad \sum_i x_i = c$$

Para proporcionar esta forma a un solucionador (por ejemplo, lpsolve), podemos reescribir la restricción como

$$\min y \\s.t. \quad -y \leq (Ax)_i \leq y, \ i = 1, \dots, m, \\ \quad \sum_i x_i = c$$

es decir,

$$\min y \\ s.t. -y \leq (Ax)_1 \leq y\\ \quad -y \leq (Ax)_2 \leq y\\ \dots\\ \quad -y \leq (Ax)_m \leq y.\\ \quad \sum_i x_i = c $$

Esta forma significa en realidad que hay N+1 variables ( $y \in \mathbb{R}$ y el original $x$ 's).