Metody obliczeniowe optymalizacji

Autorzy strony: Piotr Beling i Filip Wasilewski

Zadanie optymalizacji

Zadanie optymalizacji polega na znalezieniu optimum (minimum lub maksimum) funkcji (zwanej funkcją celu). Zmienne funkcji celu nazywamy zmiennymi decyzyjnymi.

Jeżeli N = 1 (funkcja celu jest jednowymiarowa) mówimy o optymalizacji jednowymiarowej, w przeciwnym razie o wielowymiarowej.

Często dziedzina funkcji celu jest ograniczona (tzn. że zmienne decyzyjne nie mogą przyjmować dowolnych wartości), mamy wtedy do czynienia z optymalizacją z ograniczeniami.

Czasami zdarza się też rozważać funkcje celu postaci, czyli tzw. problem optymalizacji wielokryterialnej (na ogół można go jednak sprowadzić do optymalizacji jednokrytrialnej przyjmując jako wartość optymalizowanej funkcji ważoną sumę kryteriów).

Optymalizacja bez ograniczeń
Metody bezgradientowe

Metody bezgradientowe są metodami które zazwyczaj traktują funkcje celu jak „czarną skrzynkę”, tzn. zakładają że można odczytać wartość funkcji celu w dowolnym punkcie jej dziedziny, ale nie wymagają żadnych informacji na temat jej krzywizny (tzn. znajomości jej pochodnych). Są to na przykład metody:

Metody gradientowe (I rzędu)

Metody te wymagają znajomości pierwszych pochodnych funkcji celu.

Pierwsze pochodne możemy policzyć analitycznie (i następnie zaimplementować w programie odpowiednią procedurę) lub przybliżyć ich wartość w sposób numeryczny (np. metodą różnic skończonych). Istnieją też dokładne, automatyczne metody policzenia pochodnych, np. z wykorzystaniem obliczeń symbolicznych lub metoda automatycznego różniczkowania programów komputerowych (AD).

Popularnymi metodami gradientowymi są metody:

Metody wymagające znajomości drugich pochodnych (II rzędu)

Znajomości drugich pochodnych wymagają metody:

Optymalizacja z ograniczeniami

Wiele metod bez ograniczeń można przystosować do optymalizacji z ograniczeniami (np. dodając do funkcji celu składnik kary za naruszenie ograniczeń). Typowymi metodami optymalizacji z ograniczeniami są: