Jak / dlaczego systemy liniowe są tak ważne dla informatyki?

Zainteresowałem się optymalizacją matematyczną całkiem niedawno i bardzo mi się podoba. Wydaje się, że wiele problemów związanych z optymalizacją można łatwo wyrazić i rozwiązać jako programy liniowe (np. Przepływy sieciowe, pokrycie krawędzi / wierzchołków, podróżujący sprzedawca itp.) Wiem, że niektóre z nich są trudne do NP, ale chodzi o to, że można je „sformułowane jako program liniowy”, jeśli nie zostaną optymalnie rozwiązane.

To sprawiło, że pomyślałem: zawsze uczono nas układów równań liniowych, algebry liniowej przez całą szkołę. I widząc moc LP do wyrażania różnych algorytmów, jest to trochę fascynujące.

Pytanie: Mimo że wszędzie wokół nas panują systemy nieliniowe, w jaki sposób / dlaczego systemy liniowe są tak ważne dla informatyki? Rozumiem, że pomagają uprościć zrozumienie i są w większości przypadków wykonalne obliczeniowo, ale czy to prawda? Jak dobre jest to „przybliżenie”? Czy nadmiernie upraszczamy i czy wyniki są nadal znaczące w praktyce? A może to tylko „natura”, tzn. Problemy, które są najbardziej fascynujące, są po prostu liniowe?

Czy bezpiecznie byłoby zabezpieczyć, że „algebra liniowa / równania / programowanie” są kamieniami węgielnymi CS? Jeśli nie, to jaka byłaby dobra sprzeczność? Jak często mamy do czynienia z rzeczami nieliniowymi (niekoniecznie mam na myśli teoretycznie, ale także z punktu widzenia „możliwości rozwiązania”, to znaczy, że samo stwierdzenie, że NP nie je rozwiąże, powinno być dobre przybliżenie problemu i czy wyląduje czy jesteś liniowy?)

Przesłanka tego pytania jest nieco błędna: wielu twierdziło, że kwadraty to prawdziwa „granica” dla podatności i modelowania, ponieważ problemy z najmniejszymi kwadratami są prawie tak „łatwe” jak problemy liniowe. Są inni, którzy twierdzą, że wypukłość (aw niektórych przypadkach nawet submodialność) stanowi granicę podatności na wycięcie.

Być może bardziej istotne jest „dlaczego systemy liniowe dopuszczają możliwe do rozwiązania rozwiązania?” co nie jest dokładnie tym, o co prosiłeś, ale jest powiązane. Jedną perspektywą na to jest kompozycyjność. Ponieważ jest to właściwość definiująca układ liniowy$f(x + y) = f(x) + f(y)$, to nadaje systemowi rodzaj „bez pamięci”. Aby znaleźć rozwiązanie problemu, mogę skupić się na poszczególnych elementach i łączyć je bez kary. Rzeczywiście, założenie większości algorytmów przepływu jest właśnie takie.

Ta bez pamięci nadaje wydajności: mogę rozbijać rzeczy na kawałki lub pracować iteracyjnie i nie tracę dzięki temu. Nadal mogę podejmować złe decyzje (patrz chciwe algorytmy), ale sam proces dzielenia rzeczy mnie nie boli.

To jeden z powodów, dla których liniowość ma taką moc. Prawdopodobnie jest wiele innych.

„ Mimo że wszędzie wokół nas panują systemy nieliniowe, dlaczego / dlaczego systemy liniowe są tak ważne dla informatyki?”

Oto częściowa odpowiedź w mojej opinii: myślę, że dzieje się tak, ponieważ przyroda obfituje w obiekty / zjawiska - reprezentowane przez funkcje, które choć nieliniowe na operandach, są w rzeczywistości członami przestrzeni liniowych. Fala funkcjonuje w przestrzeni Hilberta, komponenty w widmie czterokierunkowym, pierścienie wielomianowe, procesy stochastyczne - wszystkie zachowują się w ten sposób. Nawet bardzo ogólne definicje zakrzywionych przestrzeni są zbudowane z komponowania małych wykresów płaskich przestrzeni (rozmaitości, powierzchnie Riemanna, ..). Co więcej, natura jest pełna symetrii, a studiowanie symetrii niezmiennie prowadzi do badania operatorów liniowych (teoria reprezentacji, moim zdaniem, wkrada się w wiele dziedzin informatyki tak wszechobecnie).

Są to dodatkowe przypadki, w których sami operatorzy mają charakter liniowy.

Duża część problemów, dla których potrzebujemy programów komputerowych, powstaje albo bezpośrednio, albo w sposób abstrakcyjny, od naturalnie występujących zjawisk. Być może w końcu studiowanie / rozwiązywanie układów liniowych nie powinno być wielką niespodzianką?