Este es un problema de desviaciones mínimas absolutas, por lo tanto, se puede convertir a programación lineal.
Sin embargo, creo que la naturaleza especial del problema significa que se puede resolver directamente, con la complejidad [matemática] O (n) [/ matemática]:
Deje [math] x = (x_1, …, x_n) [/ math] y [math] y = (y_1, …, y_n) [/ math]. Para simplificar, deje que [math] x_i \ neq 0 [/ math] para cada [math] i = 1, …, n [/ math]. Necesitamos minimizar la función [math] f: \ mathbb {R} \ to \ mathbb {R} [/ math] definida por
- Cómo mejorar la lógica o la presentación de la conjetura descrita en una respuesta para que más personas puedan entender lo que creo que es un método sorprendente para crear algorítmicamente un conjunto primo potencialmente infinito
- ¿Cómo puedo aprender las estructuras de datos en 3 meses?
- ¿Qué idioma es mejor para los algoritmos de búsqueda: Java o Python? ¿Por qué?
- ¿Cuál es tu recurso favorito para aprender sobre programación competitiva?
- ¿Cómo estudiar efectivamente estructuras de datos y algoritmos? ¿Simplemente memorizo cómo funcionan
[math] f (\ beta) = \ sum_ {i = 1} ^ n f_i (\ beta) [/ math], donde [math] f_i (\ beta) = | \ beta x_i – y_i | [/ math] para [matemáticas] i = 1, …, n [/ matemáticas].
Cada [math] f_i [/ math] es una función en forma de V lineal por partes con el mínimo en [math] y_i / x_i [/ math]. Por lo tanto, [math] f [/ math] será una función convexa lineal por partes, no diferenciable en [math] y_1 / x_1, …, y_n / x_n [/ math]. Claramente, el mínimo de dicha función se alcanza en uno (o más) de los puntos de no diferenciabilidad.
En otras palabras, el mínimo se puede encontrar evaluando [math] f [/ math] en los puntos [math] \ beta_1 = y_1 / x_1 [/ math],…., [Math] \ beta_n = y_n / x_n [/ mates].
Tenga en cuenta también que si se ordenan [math] \ beta_i [/ math], una vez que obtengamos [math] f (\ beta_k) \ geq f (\ beta_ {k-1}) [/ math] para algunos [math] k [/ math], podemos dejar de evaluar la función; ya debemos haber encontrado el mínimo.
