Comment / pourquoi les systèmes linéaires sont-ils si cruciaux pour l'informatique?

J'ai commencé à m'intéresser à l'optimisation mathématique assez récemment et je l'adore. Il semble que beaucoup de problèmes d'optimisation peuvent être facilement exprimés et résolus sous forme de programmes linéaires (par exemple, flux de réseau, couverture de bord / sommet, vendeur itinérant, etc.) Je sais que certains d'entre eux sont NP-difficiles, mais le fait est qu'ils peuvent être «encadré comme un programme linéaire» s'il n'est pas résolu de manière optimale.

Cela m'a fait penser: on nous a toujours enseigné des systèmes d'équations linéaires, l'algèbre linéaire tout au long de l'école / collège. Et voir la puissance des LP pour exprimer divers algorithmes, c'est un peu fascinant.

Question: Bien que nous ayons des systèmes non linéaires répandus tout autour de nous, comment / pourquoi les systèmes linéaires sont-ils si cruciaux pour l'informatique? Je comprends qu'ils aident à simplifier la compréhension et sont calculables la plupart du temps, mais est-ce le cas? Quelle est la valeur de cette «approximation»? Sommes-nous en train de simplifier à l'excès et les résultats sont-ils toujours significatifs dans la pratique? Ou s'agit-il simplement de «nature», c'est-à-dire que les problèmes les plus fascinants sont en effet simplement linéaires?

Serait-il sûr que «l'algèbre linéaire / les équations / la programmation» soient les pierres angulaires de CS? Sinon, quelle serait une bonne contradiction? À quelle fréquence traitons-nous des choses non linéaires (je ne veux pas nécessairement dire théoriquement, mais aussi du point de vue de la «solvabilité», c'est-à-dire que dire que son NP ne le coupe pas; il devrait y avoir une bonne approximation du problème et at-il atterri jusqu'à être linéaire?)

La prémisse de la question est un peu erronée: nombreux sont ceux qui diraient que les quadratiques sont la véritable «frontière» pour la tractabilité et la modélisation, car les problèmes des moindres carrés sont presque aussi «faciles» que les problèmes linéaires. D'autres soutiennent que la convexité (ou même la sous-modularité dans certains cas) est la limite de la tractabilité.

Peut-être ce qui est plus pertinent est "pourquoi les systèmes linéaires admettent-ils des solutions exploitables?" ce qui n'est pas exactement ce que vous avez demandé, mais qui est lié. Une perspective à ce sujet est la composabilité. Puisque la propriété qui définit un système linéaire est que , cela confère au système une sorte d '"absence de mémoire". Pour trouver une solution à un problème, je peux me concentrer sur des pièces individuelles et les combiner sans pénalité. En effet, la prémisse de la plupart des algorithmes de flux est précisément cela.$f(x + y) = f(x) + f(y)$

Cette absence de mémoire confère de l'efficacité: je peux briser les choses ou travailler de manière itérative, et je ne perds pas en le faisant. Je peux toujours prendre de mauvaises décisions (cf algorithmes gourmands) mais le fait de diviser les choses ne me fait pas de mal.

C'est une des raisons pour lesquelles la linéarité a un tel pouvoir. Il y en a probablement beaucoup d'autres.

" Bien que nous ayons des systèmes non linéaires répandus tout autour de nous, comment / pourquoi les systèmes linéaires sont-ils si cruciaux pour l'informatique?"

Voici une réponse partielle dans mon esprit: je pense que c'est parce que la nature regorge d'objets / phénomènes - représentables par des fonctions qui, bien que non linéaires sur leurs opérandes, sont en fait des membres d'espaces linéaires. Les fonctions d'onde dans un espace de Hilbert, les composants d'un spectre de Fourier, les anneaux polynomiaux, les processus stochastiques - ils se comportent tous de cette façon. Même les définitions très générales des espaces courbes sont construites à partir de la composition de petites cartes d'espaces plats (variétés, surfaces de Riemann, ..). De plus, la nature est pleine de symétries et l'étude des symétries entre invariablement dans l'étude des opérateurs linéaires (la théorie de la représentation, dans mon esprit, se glisse dans de nombreux domaines de l'informatique de manière omniprésente).

Ce sont en plus des cas où les opérateurs eux-mêmes sont de nature linéaire.

Une grande partie des problèmes pour lesquels nous avons besoin de programmes informatiques surviennent directement ou sont abstraits de phénomènes naturels. Peut-être que l'étude / la résolution de systèmes linéaires ne devrait pas être une grande surprise, après tout?