Optymalizacja wypukła – poddziedzina optymalizacji matematycznej zajmująca się problemem minimalizacji funkcji wypukłych na zbiorach wypukłych (lub równoważnie – maksymalizacji funkcji wklęsłych na zbiorach wypukłych). Wiele klas problemów optymalizacji wypukłej można rozwiązać za pomocą algorytmów działających w czasie wielomianowym, podczas gdy problemy optymalizacji matematycznej w ogólności są NP-trudne.
Definicja
Postać abstrakcyjna Problem optymalizacji wypukłej definiowany jest przez dwa podstawowe elementy:
funkcję celu, będącą rzeczywistą funkcją wypukłą n zmiennych, ; zbiór dopuszczalny, będący podzbiorem wypukłym .
Celem jest znalezienie punktu , dla którego funkcja celu osiąga wartość
.
Ogólnie rzecz biorąc, istnieją trzy możliwości dotyczące istnienia rozwiązania:
Jeżeli taki punkt istnieje, nazywa się go punktem (lub rozwiązaniem) optymalnym; zbiór wszystkich punktów optymalnych określa się jako zbiór optymalny, a sam problem nazywa się rozwiązywalnym. Jeśli funkcja jest nieograniczona z dołu na zbiorze , lub kres dolny (infimum) nie jest osiągany, wówczas problem optymalizacji określa się jako nieograniczony. Jeżeli natomiast zbiór dopuszczalny jest zbiorem pustym, problem nazywa się niedopuszczalnym.
Postać standardowa Problem optymalizacji wypukłej ma postać standardową, jeżeli jest zapisany w następującej postaci:
gdzie:
jest wektorem zmiennych decyzyjnych (zmiennych optymalizacyjnych); funkcja celu jest funkcją wypukłą; funkcje ograniczeń nierównowościowych , , są funkcjami wypukłymi; funkcje ograniczeń równościowych , , są funkcjami afinicznymi, tzn. mają postać: , gdzie jest wektorem, a jest skalarem.
Zbiór dopuszczalny problemu optymalizacyjnego składa się ze wszystkich punktów , które spełniają zarówno ograniczenia nierównościowe, jak i równościowe. Zbiór ten jest wypukły, ponieważ dziedzina jest zbiorem wypukłym, zbiory podpoziomowe funkcji wypukłych są wypukłe, zbiory afiniczne są wypukłe, a część wspólna zbiorów wypukłych jest również wypukła.
Wiele problemów optymalizacyjnych można równoważnie przedstawić w postaci standardowej. Na przykład problem maksymalizacji funkcji wklęsłej. można sformułować równoważnie jako problem minimalizacji funkcji wypukłej . Z tego względu problem maksymalizacji funkcji wklęsłej na zbiorze wypukłym jest powszechnie zaliczany do klasy problemów optymalizacji wypukłej.
Zastosowania Optymalizacja wypukła może być stosowana do modelowania problemów w szerokim zakresie dyscyplin, takich jak systemy sterowania automatycznego, przetwarzanie sygnałów, komunikacja i sieci, projektowanie układów elektronicznych, analiza i modelowanie danych, finanse (np. optymalizacja portfela), statystyka (odmiany analizy regresji, w tym regularyzacja i regresja kwantylowa) czy uczenie maszynowe (np. klasyfikacja wieloklasowa).
Przypisy
Kategoria:Metody optymalizacji