¿Cómo / por qué los sistemas lineales son tan cruciales para la informática?

9

Hace poco comencé a involucrarme con la Optimización matemática y me encanta. Parece que muchos problemas de optimización se pueden expresar y resolver fácilmente como programas lineales (por ejemplo, flujos de red, cobertura de borde / vértice, vendedor ambulante, etc.) Sé que algunos de ellos son NP-hard, pero el punto es que pueden ser 'enmarcado como un programa lineal' si no se resuelve de manera óptima.

Eso me hizo pensar: siempre nos han enseñado sistemas de ecuaciones lineales, álgebra lineal en toda la escuela / universidad. Y ver el poder de los LP para expresar varios algoritmos es algo fascinante.

Pregunta: Aunque tenemos sistemas no lineales predominantes a nuestro alrededor, ¿cómo / por qué los sistemas lineales son tan cruciales para la informática? Entiendo que ayudan a simplificar la comprensión y son manejables computacionalmente la mayoría de las veces, pero ¿es eso? ¿Qué tan buena es esta 'aproximación'? ¿Estamos simplificando demasiado y los resultados siguen siendo significativos en la práctica? ¿O es simplemente "naturaleza", es decir, los problemas que son más fascinantes son simplemente lineales?

¿Sería seguro asegurar que 'álgebra lineal / ecuaciones / programación' son las piedras angulares de CS? Si no, ¿cuál sería una buena contradicción? ¿Con qué frecuencia tratamos con cosas no lineales? hasta ser lineal?)

Doctor
fuente
44
No voté en contra, pero no veo por qué la trazabilidad no es una respuesta satisfactoria para usted. Hay algunos sentidos precisos interesantes en los que los problemas no convexos son intratables, por ejemplo. arxiv.org/abs/1210.0420 .
Colin McQuillan
2
Los votantes negativos pueden tener muchas razones por las que eligen no hacer comentarios.
Tyson Williams
1
Una forma de verlo es que cualquier problema de NP puede reducirse a programación entera en tiempo polinómico, y luego el problema de programación entera puede ser relajado. pero sí usamos técnicas espectrales y relajaciones SDP, que son problemas de optimización cuadrática que se pueden resolver de manera eficiente.
Sasho Nikolov
1
¿Qué significa "sistemas lineales" en esta pregunta?
Tsuyoshi Ito
1
los sistemas lineales se encuentran a lo largo de todo el período de la ciencia ... es una simplificación que obtiene un kilometraje sorprendentemente alto ... parece un pequeño corolario de la efectividad irrazonable de las matemáticas en las ciencias naturales ... aparentemente CS se ajusta a esta categoría de "ciencias naturales" "... está estrechamente relacionado con la física, posiblemente cada vez más
constante

Respuestas:

12

La premisa de la pregunta es un poco defectuosa: hay muchos que argumentan que las cuadráticas son el "límite" real para la trazabilidad y el modelado, ya que los problemas de mínimos cuadrados son casi tan "fáciles" como los problemas lineales. Hay otros que argumentan que la convexidad (o incluso la submodularidad en ciertos casos) es el límite para la capacidad de seguimiento.

Quizás lo que es más relevante es "¿por qué los sistemas lineales admiten soluciones manejables?" que no es exactamente lo que pediste, pero está relacionado. Una perspectiva sobre esto es la componibilidad. Dado que la propiedad definitoria de un sistema lineal es que , esto imparte una especie de "falta de memoria" al sistema. Para construir una solución a un problema, puedo concentrarme en piezas individuales y combinarlas sin penalización. De hecho, la premisa de la mayoría de los algoritmos para el flujo es precisamente eso.F(X+y)=F(X)+F(y)

Esta falta de memoria imparte eficiencia: puedo romper cosas en pedazos, o trabajar de forma iterativa, y no pierdo en virtud de hacerlo. Todavía puedo tomar malas decisiones (cf algoritmos codiciosos) pero el acto de dividir las cosas en sí no me duele.

Esta es una razón por la cual la linealidad tiene tanto poder. Probablemente hay muchos otros.

Suresh Venkat
fuente
Me gusta esta respuesta, pero a aquellos que argumentan que la programación lineal no es el límite, respondo con: "¡es P-completo!" ;).
Artem Kaznatcheev
Sí, pero ¿es el caso de que (por ejemplo) los SDP no lo sean?
Suresh Venkat
No tenemos que tener un límite único, y algunos límites de P (por ejemplo, programación cuadrática con matriz positiva semi-definida para los términos al cuadrado) parecen más generales. No quise estar en desacuerdo, solo estaba señalando que el límite es más una cuestión de gustos al elegir entre problemas P-completos.
Artem Kaznatcheev
5

" Aunque tenemos sistemas no lineales predominantes a nuestro alrededor, ¿cómo / por qué los sistemas lineales son tan cruciales para la informática?"

Aquí hay una respuesta parcial en mi mente: creo que es porque la naturaleza está llena de objetos / fenómenos, representables por funciones que, aunque no son lineales en sus operandos, son en realidad miembros de espacios lineales. La onda funciona en un espacio de Hilbert, los componentes en un espectro de Fourier, anillos polinomiales, procesos estocásticos, todos se comportan de esa manera. Incluso las definiciones muy generales de espacios curvos se construyen a partir de componer pequeños cuadros de espacios planos (colectores, superficies de Riemann, ...). Además, la naturaleza está llena de simetrías y el estudio de las simetrías invariablemente entra en el estudio de los operadores lineales (la teoría de la representación, en mi opinión, se está infiltrando en muchas áreas de la informática de manera muy ubicua).

Estos se suman a los casos en que los operadores mismos son de naturaleza lineal.

Una gran parte de los problemas para los cuales necesitamos programas de computadora, surgen directamente como un fenómeno natural o se abstraen de él. ¿Quizás estudiar / resolver sistemas lineales no debería ser una gran sorpresa, después de todo?

Arnab
fuente
Ah sí, las maravillosas alegrías de levantar mapas.
Suresh Venkat