Cómo hallar el mínimo global de la siguiente expresión

Question

¿Cuál es el mínimo global de la expresión \begin{align} |x-1| &+ |x-2|+|x-5|+|x-6|+|x-8|+|x-9|+|x- 10| \\&+ |x-11|+|x-12|+|x-17|+|x-24|+|x-31|+ |x-32|? \end{align}

He resuelto preguntas de este tipo antes, pero sólo había 3 términos. Las resolví expandiendo todos los términos en el módulo y dibujando una gráfica. Esta pregunta venía en un trabajo que requiere que el alumno la resuelva en 5 minutos. ¿Cuál es un método mejor?

Answer 1

En principio, se puede escribir la función en muchos intervalos. Pero probablemente llevaría demasiado tiempo. Sin embargo, utilizaré este hecho, sin hacerlo explícitamente. Sabemos que si escribimos esta función, va a ser lineal en cada intervalo (suma de funciones lineales es una función lineal), y va a ser continua (suma de funciones continuas es una función continua). También sabemos que en una recta se obtiene mínimo en un extremo, en el otro, o en ambos (recta constante). Así que todo lo que necesitas hacer es calcular tu función en $1,2,5,6,...$ y encontrar el mínimo.

Answer 2

Por desgracia, he necesitado unos minutos para pensar en el problema antes de encontrar una solución que se puede calcular muy rápidamente:

Imagina la gráfica de la función $f_a(x)=|x-a|$ . Teniendo en cuenta el gráfico se ve que la derivación $f'(x)=-1$ para $x<a$ y $f'(x)=1$ para $x>a$ .

Para los intervalos: $(-\infty,1)$ , $(1,2)$ , $(2,5)$ , ..., $(32,\infty)$ ahora podemos calcular fácilmente la derivada $f'(x)=f'_1(x)+f'_2(x)+f'_5(x)+...-f'_{32}(x)$ :

En la gama $(-\infty,1)$ es $f'(x)=-1-1-1-...-1+1=-11$ .
En la gama $(1,2)$ es $f'(x)=+1-1-1-...-1+1=-9$ .
En la gama $(2,5)$ es $f'(x)=+1+1+1-...-1+1=-7$ .
...

En cada paso simplemente tenemos que invertir un signo para que "-1" se convierta en "+1". Esto significa que la derivada cambia en 2 en los puntos x=1,2,5,...

Comenzamos calculando la derivada para $x<1$ es -11.

Ahora simplemente recorremos los rangos:

<1: -11
1..2: -9
2..5: -7
5..6: -5
6..8: -3
8..9: -1
9..10: +1
10..11: +3
11..12: +5
12..17: +7
17..24: +9
24..31: +11
31..32: +13
>32: +11

En $x=32$ la derivación disminuye en 2 debido al signo menos antes de $|x-32|$ Por supuesto, se puede adaptar este método para sumas de elementos de la forma $b|x-a|$ .

Vemos que para $x<9$ la derivación es negativa y para $x>9$ la derivación es positiva. También sabemos que la función es continua. (Esto es importante porque la derivación no está definida en x=1,2,5,...) Esto significa que la función es estrictamente decreciente o creciente para $x<9$ y para $x>9$ .

Así que sabemos que el mínimo global debe estar en $x=9$ .

Answer 3

La respuesta (minimizador) en este caso es $10$ la mediana de la secuencia $$(1,2,5,6,8,9,10,11,12,17,24,31,32).$$

Puede conectar $x=10$ en la función y encontrará que el valor mínimo es $96$ . En general, la solución al siguiente problema de minimización

$$\min\{|x-a_1| + |x-a_2| + \cdots + |x-a_n|\}$$ es la mediana de $(a_1,\ldots,a_n)$ . Para ver por qué, considere primero cuándo $n=2$ y sin pérdida de generalidad supongamos $a_1<a_2$ . Entonces $|x-a_1|+|x-a_2|$ es la distancia entre $x$ y $a_1$ más la distancia entre $x$ y $a_2$ . Es fácil ver que sólo cuando $x$ está en medio de $a_1$ y $a_2$ si la suma de las distancias es mínima, lo que equivale a $|a_2-a_1|$ en este caso. En este caso el minimizador no es único. Cualquier punto de $[a_1,a_2]$ es un minimizador.

En $n=3$ la función es $|x-a_1|+|x-a_2|+|x-a_3|$ y volvemos a ordenar los parámetros de forma que $a_1<a_2<a_3$ . En $x$ coincide con $a_2$ es decir $x=a_2$ el valor pasa a ser $|a_2-a_1|+|a_2-a_3|=|a_3-a_1|$ la distancia entre $a_3$ y $a_1$ . Pero cuando $x\in[a_1,a_3], x\neq a_2$ el valor de la función es $$|x-a_2|+|x-a_1|+|x-a_3| = |a_3-a_1| + |x-a_2|,$$ que es más grande que $|a_3-a_1|$ la distancia entre $a_3$ y $a_1$ . Del mismo modo, el valor sería mayor cuando $x$ está fuera $[a_1,a_3]$ . En este caso, el minimizador es único e igual a $a_2$ la mediana de $(a_1,a_2,a_3)$ .

En general, cuando $n$ es impar, existe un minimizador único, que es igual a la mediana (única) de los parámetros $(a_1,\ldots,a_n)$ . En $n$ es par, la función es mínima y constante en el intervalo $[a_i,a_j]$ donde $a_i$ y $a_j$ son los dos valores medios.

Answer 4

TL;DR: Pon los valores absolutos en orden ascendente, y mira la suma de los coeficientes principales. Cambia uno a uno los signos de la suma de derecha a izquierda. Cuando la suma cambia de signo, se ha superado un extremo local. Cuando la suma es igual a cero, hay un extremo en un intervalo entero.

---

Como alternativa a la excelente respuesta de Andrei, o tal vez como ampliación, también podrías considerar la derivada. Es evidente que la función es continua en todas partes, y es diferenciable en todos los puntos menos en un número finito, llamémoslos $a_1,\ldots,a_n$ en orden ascendente. Entonces queremos minimizar $$f(x)=\sum_{k=1}^nc_k|x-a_k|=\sum_{k=1}^n(-1)^{\delta_{x\leq a_k}}c_k(x-a_k),$$ donde $\delta$ denota el delta de Kronecker, en este caso definido como $$\delta_{x\leq a_k}:=\left\{\begin{array}{ll}1&\text{ if } x\leq a_k\\0&\text{ otherwise}\end{array}\right..$$ Esto tiene derivadas (para todos $x$ aparte del $a_k$ ) $$f'(x)=\sum_{k=1}^n(-1)^{\delta_{x\leq a_k}}c_k.$$ La expresión tiene un mínimo local en $x$ si $f'(x)=0$ o si $x=a_k$ para algunos $k$ y $f'(y)<0$ para $a_{k-1}<y<a_k$ y $f'(y)>0$ para $a_k<y<a_{k+1}$ .

Todo esto es bastante formal; en la práctica esto significa que se pone el $c_k$ en orden ascendente, así que aquí $n=13$ y $c_1=\cdots=c_{12}=1$ y $c_{13}=-1$ y encontrar todos $m$ tal que al voltear el último $m$ signos en la suma $$c_1+c_2+c_3+c_4+c_5+c_6+c_7+c_8+c_9+c_{10}+c_{11}+c_{12}+c_{13}$$ hace que la suma cambie de signo en comparación con cambiar el último $m-1$ signos. Aquí un vistazo rápido da $$c_1+c_2+c_3+c_4+c_5+c_6-c_7-c_8-c_9-c_{10}-c_{11}-c_{12}-c_{13}=1,$$ $$c_1+c_2+c_3+c_4+c_5-c_6-c_7-c_8-c_9-c_{10}-c_{11}-c_{12}-c_{13}=-1,$$ así que $f$ tiene un mínimo local en $a_6=9$ y no es difícil ver que no hay otro mínimo.