Programowanie nieliniowe

Programowanie nieliniowe (PNL) — to dział programowania matematycznego i badań operacyjnych, zajmujący się zadaniami optymalizacji, w których funkcja celu i/lub co najmniej jedno z ograniczeń są nieliniowymi funkcjami zmiennych decyzyjnych.

PNL jest uogólnieniem programowania liniowego i pozwala modelować szerszą klasę rzeczywistych systemów i procesów, w których zależności między zmiennymi nie są ściśle proporcjonalne (tzn. opisywane są krzywymi, a nie liniami prostymi).

Przedmiot i przeznaczenie

Programowanie nieliniowe stosuje się do znajdowania optymalnych rozwiązań w sytuacjach, gdy:

• Zależność wskaźnika docelowego (zysku, kosztów, efektywności itp.) od parametrów sterowanych jest nieliniowa (np. malejące przychody ze skali, koszty kwadratowe).
• Ograniczenia dotyczące zasobów lub procesów technologicznych opisywane są relacjami nieliniowymi (np. reakcje chemiczne, prawa fizyczne, zależności ekonomiczne).

Zadania PNL pojawiają się w wielu dziedzinach:

• Projektowanie inżynieryjne (optymalizacja konstrukcji, procesów).
• Ekonomia i finanse (optymalizacja portfela z uwzględnieniem ryzyka, modelowanie rynku).
• Technologia chemiczna (optymalizacja trybów pracy reaktorów).
• Machine Learning (uczenie sieci neuronowych, metoda wektorów nośnych).
• Zarządzanie procesami produkcyjnymi. Logistyka (z uwzględnieniem kosztów nieliniowych).

Matematyczne sformułowanie zadania PNL

Ogólne zadanie programowania nieliniowego formułuje się następująco:

Należy znaleźć zestaw wartości zmiennych decyzyjnych, który maksymalizuje lub minimalizuje nieliniową funkcję celu. Przy tym wartości zmiennych muszą spełniać układ ograniczeń, które mogą być wyrażone zarówno w postaci nierówności (np. „wartość A musi być mniejsza lub równa B"), jak i w postaci równości (np. „wartość C musi być dokładnie równa D"). Istotne jest, że co najmniej jedna z funkcji opisujących cel lub ograniczenia jest nieliniowa. Często dodawane są warunki nieujemności zmiennych, czyli wymóg, aby ich wartości były większe lub równe zero.

Zbiór wszystkich zestawów wartości zmiennych spełniających ograniczenia tworzy obszar rozwiązań dopuszczalnych (ORD).

Różnice w stosunku do programowania liniowego

Programowanie nieliniowe różni się zasadniczo od programowania liniowego (PL):

• Nieliniowość: Funkcja celu lub ograniczenia (lub jedno i drugie) zawierają zależności nieliniowe.
• Własności ORD: Obszar rozwiązań dopuszczalnych w PNL może być niewypukły (w odróżnieniu od PL, gdzie ORD jest zawsze wypukłym wielościanem).
• Własności optimum: Optymalne rozwiązanie w PNL niekoniecznie leży w wierzchołku ORD — może leżeć na granicy lub wewnątrz obszaru. W PNL mogą istnieć lokalne optima, które nie są globalnymi.
• Złożoność rozwiązania: Zadania PNL są na ogół znacznie trudniejsze do rozwiązania niż zadania PL. Nie istnieje jeden uniwersalny algorytm, analogiczny do metody simpleks, dla wszystkich zadań PNL.

Główne trudności i wyzwania PNL

Rozwiązywanie zadań programowania nieliniowego wiąże się z szeregiem trudności:

• Istnienie lokalnych ekstremów: Większość metod PNL gwarantuje znalezienie jedynie lokalnego optimum (rozwiązania najlepszego w pewnym otoczeniu). Poszukiwanie globalnego optimum (najlepszego rozwiązania w całym ORD) jest zadaniem trudnym, szczególnie dla problemów niewypukłych.
• Niewypukłość: Jeśli zadanie nie jest wypukłe (funkcja celu lub ORD są niewypukłe), może istnieć wiele lokalnych optimów, a standardowe metody gradientowe mogą „utknąć" w jednym z nich.
• Złożoność obliczeniowa: Algorytmy rozwiązywania PNL często wymagają znacznie większych zasobów obliczeniowych w porównaniu z PL.

Ważne klasy zadań PNL

Pomimo ogólnej złożoności, istnieją ważne podklasy zadań PNL, dla których opracowano efektywne metody rozwiązania:

• Programowanie wypukłe: Zadanie minimalizacji funkcji wypukłej na wypukłym zbiorze rozwiązań dopuszczalnych (lub maksymalizacji funkcji wklęsłej). Kluczowa własność: każde lokalne minimum jest jednocześnie globalnym minimum. Znacznie upraszcza to poszukiwanie optymalnego rozwiązania.
• Programowanie kwadratowe: Funkcja celu jest kwadratowa, a wszystkie ograniczenia — liniowe.
• Programowanie separowalne: Funkcja celu i ograniczenia mogą być przedstawione jako sumy funkcji, z których każda zależy tylko od jednej zmiennej.

Metody rozwiązywania zadań PNL

Metody rozwiązywania zadań programowania nieliniowego (PNL)

I. Metody optymalizacji bez ograniczeń:

• Metody gradientowe (metoda najszybszego spadku, metoda gradientów sprzężonych);
• Metoda Newtona i metody quasi-newtonowskie (np. BFGS);
• Metody wykorzystujące aproksymację hesjanu.

II. Metody optymalizacji warunkowej (optymalizacja z ograniczeniami):

• Metody transformacji:
  • Metoda funkcji kar (penalty methods);
  • Metoda funkcji barierowych (barrier methods).
• Metody bezpośredniego poszukiwania kierunków:
  • Metoda kierunków dopuszczalnych.
• Metody oparte na warunkach optymalności:
  • Metody Karusha-Kuhna-Tuckera (warunki KKT);
  • Metoda mnożników Lagrange'a.
• Metody iteracyjne:
  • Sekwencyjne programowanie kwadratowe (SQP);
  • Metody punktów wewnętrznych.

III. Metody optymalizacji globalnej:

• Metody heurystyczne i metaheurystyczne:
  • Algorytmy genetyczne;
  • Symulowane wyżarzanie;
  • Przeszukiwanie z tabu (tabu search).
• Metody deterministyczne:
  • Podziału i ograniczeń (branch and bound);
  • Algorytmy optymalizacji globalnej dla zadań o specjalnej strukturze.

Literatura

• Bazara M., Shetty C. Programowanie nieliniowe. Teoria i algorytmy. — Moskwa: Mir, 1982.
• Fiacco A., McCormick G. Programowanie nieliniowe. Metody sekwencyjnej minimalizacji bez ograniczeń. — Moskwa: Mir, 1972.
• Himmelblau D. Stosowane programowanie nieliniowe. — Moskwa: Mir, 1975.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)

Zobacz też

• Badania operacyjne
• Optymalizacja
• Programowanie liniowe
• Programowanie wypukłe
• Funkcja celu
• Ograniczenia
• Obszar rozwiązań dopuszczalnych