Programowanie nieliniowe
- Autor metody
- Jorge Nocedal & Stephen Wright
- Rok
- 2006
- Typ
- Continuous mathematical optimization
- Rodzina
- Mathematical programming
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Programowanie nieliniowe (NLP) to gałąź optymalizacji matematycznej zajmująca się problemami, w których funkcja celu lub co najmniej jedno ograniczenie jest nieliniowe.
Kompleksowo sformalizowane przez Jorge Nocedala i Stephena Wrighta w ich przełomowym tekście z 2006 roku, NLP obejmuje algorytmy oparte na gradiencie — w tym sekwencyjne programowanie kwadratowe (SQP), metody punktu wewnętrznego i podejścia quasi-Newtonowskie — do znajdowania lokalnie lub globalnie optymalnych rozwiązań ciągłych problemów decyzyjnych pojawiających się w inżynierii, ekonomii i naukach przyrodniczych.
Intuicja stojąca za metodą
Wyobraź sobie schodzenie po pagórkowatym, spowitym mgłą terenie, pozostając w ogrodzonym obszarze. Nie widzisz całego terenu, więc czujesz nachylenie pod stopami (gradient), dostosowujesz kierunek kroku, aby zejść w dół, i sprawdzasz przy każdym ruchu, czy nie przekroczyłeś ogrodzenia (ograniczenia). Jeśli ogrodzenie się wygina lub wzgórza nakładają się na siebie, proste ścieżki po linii prostej nie zadziałają — musisz zakrzywić swoją ścieżkę. Programowanie nieliniowe formalizuje dokładnie ten proces, zastępując intuicyjne chodzenie po wzgórzach matematycznie rygorystycznymi zasadami długości kroku i kierunku.
Historia
Podstawy teoretyczne programowania nieliniowego sięgają warunków KKT wyprowadzonych przez Karusha (1939) oraz Kuhna i Tuckera (1951). Praktyczne algorytmy przyspieszyły w latach 60.–80. XX wieku wraz z rozwojem metod SQP, podejść z rozszerzonym Lagrangianem i aktualizacji quasi-Newtonowskich, w tym BFGS (1970). Drugie wydanie książki Nocedala i Wrighta 'Numerical Optimization' z 2006 roku stało się definitywnym odniesieniem, syntetyzując teorię zbieżności, ramy wyszukiwania liniowego i regionu zaufania oraz metody punktu wewnętrznego w spójne nowoczesne ujęcie.
Kiedy stosować
Używaj programowania nieliniowego, gdy funkcja celu lub ograniczenia nie mogą być zlinearyzowane bez istotnej utraty dokładności, a zmienne decyzyjne są ciągłe. Typowe zastosowania obejmują projektowanie inżynierskie z ograniczeniami wynikającymi z praw fizyki, optymalizację portfela z nieliniowymi miarami ryzyka oraz regresję z nieliniowymi formami modeli. Kluczowe założenia to, że f i c są co najmniej dwukrotnie ciągle różniczkowalne (dla rozwiązywaczy opartych na gradiencie) i że kwalifikacje ograniczeń są spełnione. Gdy zmienne są całkowite, stosuje się rozszerzenia mieszanego programowania nieliniowego całkowitoliczbowego (MINLP). Dla problemów wypukłych metody punktu wewnętrznego gwarantują globalną optymalność; dla problemów niewypukłych istnieją tylko gwarancje lokalne.
Ograniczenia i uwagi
- Problemy niewypukłe oferują jedynie gwarancje lokalnej optymalności; rozwiązania globalne wymagają dodatkowych strategii globalnego poszukiwania.
- Wymaga, aby funkcja celu i ograniczenia były gładkie (co najmniej różniczkowalne); problemy niegładkie wymagają specjalistycznych metod podróżniczych.
- Koszt obliczeniowy znacząco rośnie wraz z rozmiarem problemu, gdy wymagana jest dokładna ewaluacja Hesjanu.
- Kwalifikacje ograniczeń mogą zawieść (np. w zdegenerowanych punktach dopuszczalnych), powodując utratę teoretycznych podstaw warunków KKT.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Obsługuje szeroką klasę problemów świata rzeczywistego, gdzie aproksymacje liniowe lub kwadratowe są niewystarczające.
- Dojrzała teoria algorytmiczna z dobrze zbadanymi gwarancjami zbieżności dla instancji wypukłych.
- Wydajne rozwiązywacze oparte na gradiencie (SQP, punkt wewnętrzny) w praktyce skalują się do tysięcy zmiennych.
- Zunifikowana rama Lagrangianu naturalnie uwzględnia mieszane ograniczenia równościowe i nierównościowe.
Zastosowania
- Inżynieria budowlana i lotnicza: minimalizacja masy przy ograniczeniach naprężeń i ugięć.
- Zarządzanie portfelem: maksymalizacja oczekiwanego zwrotu przy nieliniowym budżecie wariancji (ryzyka).
- Projektowanie procesów chemicznych: optymalizacja wydajności reaktora przy ograniczeniach termodynamicznych i bezpieczeństwa.
- Uczenie maszynowe: trenowanie sieci neuronowych i modeli jądrowych za pomocą rozwiązywaczy NLP bez ograniczeń lub z ograniczeniami.
- Systemy energetyczne: problemy optymalnego przepływu mocy w dyspozycji sieci elektroenergetycznej z nieliniowymi ograniczeniami fizycznymi.
Jak to działa
Jak to działa
Analityk definiuje skalarną funkcję celu f(x) do minimalizacji lub maksymalizacji względem zmiennych decyzyjnych x w R^n, wraz z ograniczeniami równościowymi c_i(x) = 0 i ograniczeniami nierównościowymi c_j(x) >= 0. Identyfikacja, które ograniczenia są aktywne w kandydacie na rozwiązanie i czy warunki regularności (kwalifikacje ograniczeń) są spełnione, jest kluczowa na tym etapie i określa, która teoria optymalności ma zastosowanie.
Wzór
\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t.} \quad c_i(x) = 0,\; i \in \mathcal{E};\quad c_j(x) \ge 0,\; j \in \mathcal{I}Warunki Karusha-Kuhna-Tuckera (KKT) stanowią konieczne warunki pierwszego rzędu dla lokalnego optimum. Wymagają stacjonarności Lagrangianu, zerowania się luzów dla mnożników nierówności (lambda_j c_j = 0), dopuszczalności dualnej (lambda_j >= 0) i dopuszczalności pierwotnej. Algorytmy iteracyjnie konstruują punkty pośrednie, które coraz ściślej spełniają te warunki, a warunki wystarczalności drugiego rzędu potwierdzają, że punkt stacjonarny jest rzeczywiście minimum lokalnym.
Wzór
\nabla f(x^*) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i \nabla c_i(x^*) = 0, \quad \lambda_j c_j(x^*) = 0, \quad \lambda_j \ge 0 \; \forall j \in \mathcal{I}Na każdej iteracji k algorytm oblicza kierunek poszukiwania p_k — zazwyczaj za pomocą aproksymacji quasi-Newtonowskiej B_k Hesjanu (np. BFGS) lub dokładnego układu drugich pochodnych — oraz długość kroku alpha_k spełniającą warunki Wolfe'a lub Armijo. Metody SQP rozwiązują kwadratowy podproblem dla p_k, podczas gdy metody punktu wewnętrznego dodają człony barierowe do obsługi ograniczeń nierównościowych i kierują punkty pośrednie w stronę dopuszczalnego wnętrza.
Wzór
x_{k+1} = x_k + \alpha_k p_k, \quad p_k = -B_k^{-1} \nabla f(x_k)Zakończenie następuje, gdy norma gradientu Lagrangianu i maksymalne naruszenie ograniczeń spadną poniżej zadanych tolerancji (epsilon i delta). Ponieważ NLP jest generalnie niewypukłe, algorytmy mogą zbiegać do lokalnych optimów; zaleca się wielokrotne restarty z różnych punktów początkowych lub strategie globalnego poszukiwania (branch-and-bound, multistart), gdy wymagana jest globalna optymalność.
Wzór
\|\nabla f(x_k)\| \le \epsilon \quad \text{and} \quad \max_{i} |c_i(x_k)| \le \deltaCzęste pułapki
- Ignorowanie kwalifikacji ograniczeń i ślepe stosowanie warunków KKT w punktach zdegenerowanych lub niedopuszczalnych prowadzi do fałszywych rozwiązań.
- Używanie źle przeskalowanych zmiennych powoduje źle uwarunkowane aproksymacje Hesjanu oraz powolną lub nieudaną zbieżność.
- Akceptacja pierwszego znalezionego minimum lokalnego bez wielokrotnych restartów w ustawieniach niewypukłych może znacznie ominąć optimum globalne.
- Aproksymacje gradientu metodą różnic skończonych wprowadzają błąd numeryczny; preferowane jest różniczkowanie analityczne lub automatyczne.
Najczęściej zadawane pytania
Czy każde programowanie liniowe jest również programowaniem nieliniowym?
Tak. Programowanie liniowe jest szczególnym przypadkiem NLP, w którym zarówno funkcja celu, jak i wszystkie ograniczenia są afiniczne. Jednakże LP dopuszcza algorytmy sympleksowe i metody punktu wewnętrznego, które wykorzystują liniowość i są znacznie wydajniejsze niż ogólne rozwiązywacze NLP; używanie ogólnego rozwiązywacza NLP do LP jest marnotrawstwem, ale matematycznie poprawne.
Kiedy mogę ufać, że punkt KKT jest minimum globalnym?
Gdy NLP jest wypukłe — co oznacza, że f jest wypukła, a zbiór dopuszczalny jest zbiorem wypukłym — każdy punkt KKT jest minimum globalnym. W przypadku problemów niewypukłych ta gwarancja nie obowiązuje, a punkt KKT jest tylko minimum lokalnym (przy warunkach wystarczalności drugiego rzędu). W przeciwnym razie potrzebne są metody optymalizacji globalnej, takie jak branch-and-bound lub relaksacje wypukłe.
Jaka jest różnica między metodami SQP a metodami punktu wewnętrznego?
SQP iteracyjnie rozwiązuje podproblemy programowania kwadratowego, które lokalnie aproksymują NLP i jest często preferowane dla małych i średnich problemów z wieloma aktywnymi ograniczeniami. Metody punktu wewnętrznego (barierowe) pozostają ściśle wewnątrz obszaru dopuszczalnego i mają tendencję do lepszego skalowania dla dużych, rzadkich problemów. Oba algorytmy zbiegają superliniowo przy odpowiednich warunkach regularności.
Pokrewne metody
Źródła
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
ISBN: 978-0-387-30303-1Skopiowano.