Minimizar $L_\infty$ norma utilizando el descenso de gradiente?

Question

Los problemas de ajuste de curvas se resuelven minimizando una función de coste/error con respecto a los parámetros del modelo. El descenso gradual y el método de Newton son algunos de los muchos algoritmos utilizados para minimizar esta función.

El $L_\infty$ también puede utilizarse como función de coste para regresión lineal/polinómica . Mi pregunta: ¿es posible utilizar el descenso de gradiente para minimizar el coste definido por el $L_\infty$ norma (es decir $\text{cost} = \max|\text{predicted} - \text{actual}|$ )? ¿Cómo se define el gradiente de esta función?

Answer 1

El enfoque tradicional consistiría en reformular el problema para hacerlo más suave. En este caso, es fácil: $$ \min_x \ \|Ax - b\|_{\infty} $$ equivale a $$ \min_{x,t} \ t \quad \text{subject to} \ -te \leq Ax - b \leq te, $$ donde $e = (1, 1, \dots, 1)$ . Se trata de un programa lineal que se puede resolver con un solucionador de LP estándar. Se puede hacer el mismo truco con el $\ell_1$ que a menudo se utiliza en el ajuste de curvas para mitigar la influencia de los valores atípicos: $$ \min_x \ \|Ax - b\|_1 $$ equivale a $$ \min_{x,s,t} \ \sum_i s_i+t_i \quad \text{subject to} \ Ax-b = s - t, \ (s, t) \geq 0. $$ De nuevo, se trata de un programa lineal.

Si quieres evitar las restricciones, puedes aplicar un método de subgradiente al objetivo no liso $\|Ax-b\|_{\infty}$ . Es casi idéntico a aplicar el método del gradiente, excepto que en lugar de un gradiente, se calcula un subgradiente. Véase http://www.seas.ucla.edu/~vandenbe/236C/lecturas/subgradientes.pdf .