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;