Problemem optymalizacyjnym jest problem znalezienia ekstremum (minimum lub maksimum) funkcji celu w pewnym regionie skończonej przestrzeni wektorowej ograniczonej zestawem liniowych i / lub nieliniowych równości i / lub nierówności.
Funkcja celu to zestaw kryteriów jakości, które muszą być zoptymalizowane jednocześnie. Ogólnie rzecz biorąc, funkcja celu składa się ze zmiennych kontrolowanych i niezarządzanych. Warunek wyszukiwania dla ekstremum funkcji celu jest zapisany w następującej formie:
Metody rozwiązywania problemów optymalizacyjnych to studiowanie programowania matematycznego. Programowanie matematyczne jest dyscypliną matematyczną, która bada teorię i metody rozwiązywania problemów związanych z definiowaniem ekstremów funkcji na zbiorach skończonych wymiarów przestrzeni wektorowych zdefiniowanych przez zestaw liniowych i / lub nieliniowych ograniczeń (równości i / lub nierówności). Programowanie matematyczne jest z reguły powtarzalną procedurą obliczeniową, która prowadzi do pożądanego optymalnego rozwiązania. Wybór metody programowania matematycznego do rozwiązania problemu optymalizacji zależy od rodzaju zależności w modelu matematycznym, charakteru poszukiwanych zmiennych, kategorii danych wejściowych i liczby kryteriów optymalności:
- Metody programowania liniowego są stosowane, jeśli w modelu matematycznym istnieją tylko liniowe zależności między zmiennymi, w celu rozwiązania problemu optymalizacji.
- Metody programowania nieliniowego są stosowane, gdy w modelu matematycznym występują nieliniowe zależności między zmiennymi w celu rozwiązania problemu optymalizacji.
- Metody programowania całkowitoliczbowego lub dyskretnego są stosowane, jeśli pomiędzy zmiennymi występują zmienne całkowite lub dyskretne.
- Metody programowania stochastycznego są stosowane w przypadku, gdy dane źródłowe lub ich część są zmiennymi losowymi.
- Matematyczny aparat teorii gier jest stosowany w przypadku podania niedeterministycznej (nieokreślonej) informacji początkowej.
Problem optymalizacji jest rozwiązywany przy użyciu metod wyszukiwania, które wykorzystują poprzednie informacje do zbudowania ulepszonego rozwiązania problemu (iteracyjne metody obliczeniowe). Do tej pory opracowano wiele lokalnych metod optymalizacji w celu rozwiązywania problemów w formie ogólnej. Większość z nich stosuje zasadę lokalnego zejścia, gdy metoda kolejno przechodzi do punktów o znacznie mniejszych (większych) wartościach funkcji celu na każdym kroku. Metody te różnią się między sobą metodą określania kierunku ruchu do optymalnego, wielkości kroku i czasu trwania wyszukiwania wzdłuż znalezionego kierunku, a także kryteriów zakończenia wyszukiwania. Poszukiwanie optymalnej wartości takich problemów można przedstawić jako relację iteracyjną:
gdzie jest zmienna 
jest przyrostem wektora kontrolowanych parametrów. W zależności od warunku wyszukiwania (wyszukiwanie maksymalnej lub minimalnej wartości funkcji celu) używany jest znak „+” lub znak „-”.
Przyrost wektora kontrolowanych parametrów w większości przypadków jest obliczany według wzoru:
W tym wyrażeniu 
- wartość wektora kontrolowanych parametrów w k-tym kroku, 
- krok obliczeniowy, i 
- kierunek poszukiwania ekstremum funkcji.
W zależności od liczby kontrolowanych parametrów rozróżnia się metody optymalizacji jednowymiarowej i wielowymiarowej (optymalizacja wielokryterialna). Wyszukiwanie jest uważane za jednowymiarowe, w przypadku gdy argument funkcji celu jest jednym kontrolowanym parametrem.
Krok obliczeniowy
Iteracyjna forma lokalnych metod optymalizacji do rozwiązywania problemów ze znalezieniem ekstremum funkcji celu wymaga wybrania kroku obliczeniowego wzdłuż danych kierunków na każdym kroku iteracji. Krok obliczeniowy może być stały lub zmienny, ale optymalna wartość długości kroku jest określana przez wyszukiwanie ekstremum funkcji celu w wybranym kierunku 
przy użyciu jednowymiarowych metod optymalizacji:
Innymi słowy, wartość kroku obliczania jest obliczana przez rozwiązanie następującego wyrażenia:
W wyniku rozwiązania tego równania uzyskujemy, że krok obliczeniowy w formie symbolicznej jest określony następująco:
gdzie 
- wartość argumentu funkcji w k-tym kroku iteracji;
n jest liczbą nieznanych zmiennych, które są określane podczas rozwiązywania problemu;
L - pewna stała określona na podstawie wyznacznika następującej macierzy:
W rezultacie, aby określić optymalny krok obliczeniowy, konieczne jest wykonanie dużej ilości obliczeń funkcji celu. W celu zmniejszenia liczby operacji w praktyce stosuje się inne podejście: takie wartości kroku obliczania są wybrane 
tak, aby spełniały jeden z poniższych warunków.
gdzie jest współczynnik 
i krok obliczeniowy określany iteracyjnie przez pomnożenie początkowego kroku 
według współczynnika 
dopóki warunek nie zostanie spełniony.
Kryterium wyboru kroku obliczeniowego zgodnie z zasadą Armijo
Metoda określania kroku obliczania problemu optymalizacji zgodnie z regułą Armijo jest następująca:
1. Ustaw współczynnik 
od 0 do 1.
2. Ustaw początkową wartość kroku. .
Procedura wyszukiwania (sprawdzenie spełnienia warunku zgodnie z zasadą Armiho)
3. Jeśli warunek zgodny z regułą Armijo nie zostanie spełniony , konieczne jest poprawienie kroku obliczeniowego 
gdzie zmienna 
może być dowolną wartością od 0 do 1, domyślnie zakładamy, że zmienna 
i 
- bieżący krok wyszukiwania.
4. Jeśli warunek zgodny z regułą Armijo jest spełniony , można zaakceptować jako krok obliczeniowy 
i procedura wyszukiwania została zakończona.
Ta reguła wymaga pojedynczego obliczenia gradientu, po którym niewielka liczba iteracji jest wydawana na wybór odpowiedniego kroku. Każda z tych zagnieżdżonych iteracji z kolei wymaga obliczenia wartości funkcji celu bez gradientu, tzn. Przeprowadzone testy są stosunkowo lekkie. Należy zauważyć, że warunek ten jest spełniony dla wszystkich wystarczająco małych . Reguła Armijo może zostać rozszerzona na przypadek wielokryterialny: nierówność 3.19 należy rozumieć jako komponent po komponencie.
- Drugi warunek (zasada Wolfa-Powella - Wolfe. P) jest zmodyfikowanym kryterium, które pozwala wybrać krok obliczeniowy, jeśli spełnione są dwa warunki:
- funkcja 
nie może przekraczać wartości jakiejś malejącej funkcji liniowej równej 
na zero:
- wielkość funkcji zmiany prędkości w danym kierunku 
był w 
razy szybkość zmiany funkcji w pierwotnym punkcie
Kryterium wyboru etapu obliczania zgodnie z zasadą Wolfa-Powella
Metoda określania kroku obliczania problemu optymalizacji zgodnie z zasadą Wolfa-Powella jest następująca:
1. Ustaw współczynnik 
i 
od 0 do 1 
.
2. Ustaw początkową wartość kroku 
wziąć współczynnik 
i 
Procedura wyszukiwania (kontrola warunkowa zgodnie z zasadą Wolfa-Powella)
3. Jeśli pierwszy warunek nie jest spełniony przez regułę Wolfa-Powella , to weź współczynnik 
. Przejdź do punktu nr 5 .
4. Jeśli drugi warunek nie jest spełniony przez regułę Wolfa-Powella , to weź współczynnik 
:
- w przypadku 
następnie przejdź do pozycji nr 5 ;
- w przypadku ekstrapolować przez wprowadzenie 
gdzie r jest współczynnikiem ekstrapolacji 
. Przejdź do punktu nr 3 .
5. Wykonaj bieżące obliczenie kroku za pomocą formuły
gdzie 
- współczynnik interpolacji, który jest określony w następującym zakresie 
Przejdź do punktu nr 3 .
6. Jeśli oba warunki są spełnione przez regułę Wolfa-Powella , możesz wykonać krok obliczeniowy i procedura wyszukiwania została zakończona.
- Trzeci warunek (zasada Goldsteina-Armiyo) pozwala wybrać krok obliczeniowy, biorąc pod uwagę następujące nierówności:
Metoda określania kroku obliczania problemu optymalizacji zgodnie z zasadą Goldsteina-Armymiota jest następująca:
1. Ustaw współczynnik 
i 
od 0 do 1 
.
2. Ustaw początkową wartość kroku
3. Jeśli warunek zgodny z zasadą Goldsteina-Armymiot nie jest spełniony , wówczas etap obliczania musi zostać dostosowany. gdzie zmienna może być dowolną wartością od 0 do 1, domyślnie zakładamy, że zmienna i - bieżący krok wyszukiwania.
4. Jeśli warunek zgodny z zasadą Goldstein-Armymiot jest spełniony , możesz wykonać jako krok obliczeniowy i procedura wyszukiwania została zakończona.
Kryteria zatrzymania procesu optymalizacji
Poszukiwanie optymalnego rozwiązania jest zakończone, gdy jedno (lub kilka) kryteriów zostanie spełnione na etapie iteracyjnego obliczania:
- trajektoria wyszukiwania pozostaje w niewielkim sąsiedztwie bieżącego punktu wyszukiwania:
- przyrost funkcji celu nie zmienia się:
- gradient funkcji celu w lokalnym punkcie minimalnym zanika:
Klasyfikacja metod optymalizacji.
Obecnie opracowano ogromną liczbę różnych metod matematycznych do rozwiązywania problemów optymalizacyjnych. Zastosowanie określonej metody jest określane przez sformułowanie problemu, złożoność obliczeń funkcji i jej pochodnych, zachowanie funkcji itp.
Zadania optymalizacyjne i metody ich rozwiązywania można podzielić przez obecność lub brak ograniczeń (zdefiniowanych przez system nierówności i równości lub przez bardziej złożony algorytm) w modelach matematycznych dla warunkowych i bezwarunkowych metod optymalizacji. Prawdziwe problemy charakteryzują się obecnością ograniczeń, jednak bezwarunkowe metody optymalizacji są również interesujące, ponieważ problemy z optymalizacją warunkową można zredukować do specjalnych problemów za pomocą specjalnych metod.
Bezwarunkowe metody optymalizacji
Klasyczny problem bezwarunkowej optymalizacji sformułowany jest następująco: wymagane jest znalezienie wektora zmiennych 
w którym funkcja celu przyjmuje wartość ekstremalną (wartość maksymalną lub minimalną)
Ekstremalna wartość funkcji celu odpowiada optymalnej kontroli. Graficznie sformułowanie problemu jest następujące:
Zadanie bezwarunkowej optymalizacji funkcji dwóch zmiennych
Istota metody optymalizacji zależy przede wszystkim od metody wyboru kierunku ruchu do ekstremum. W zależności od użytej kolejności pochodnych funkcji celu, metody bezwarunkowej optymalizacji są podzielone na metody zerowego, pierwszego i drugiego rzędu. Jeśli nie używa się pochodnych, stosuje się metodę rzędu zerowego, jeśli stosuje się pierwszą lub drugą pochodną, to odpowiednio metodę pierwszego lub drugiego rzędu.
- Metody zerowego rzędu (metody bezpośredniego wyszukiwania) do wyszukiwania ekstremum funkcji wymagają obliczenia tylko wartości funkcji w punktach przestrzeni optymalizacji. W tej metodzie informacje o instrumentach pochodnych nie są wykorzystywane, a zatem nie wymagają definicji formy analitycznej instrumentów pochodnych. W zależności od liczby kontrolowanych parametrów rozróżnia się metody wyszukiwania jednowymiarowego i wielowymiarowego.
Najbardziej popularne (pod względem nauczania w szkolnictwie wyższym) są następujące metody rozwiązywania problemów optymalizacji rzędu zerowego:
Jednoliniowe metody wyszukiwania:
- Metoda podziału dychotomicznego i metoda złotej sekcji są jednowymiarowymi metodami optymalizacji opartymi na podziale segmentu, na którym poszukiwane jest ekstremum, odpowiednio w połowie lub w proporcjach złotej sekcji (0,382 / 0,618).
- Metoda aproksymacji wielomianowej (metoda interpolacji kwadratowej) jest jednowymiarową metodą optymalizacji, zgodnie z którą funkcja celu jest aproksymowana przez wielomian kwadratowy.
Wielowymiarowe metody wyszukiwania:
- Metoda spadku współrzędnych (Gauss-Seidel) jest metodą bezwarunkowej optymalizacji rzędu zerowego, w której kierunki wyszukiwania są wybierane naprzemiennie wzdłuż wszystkich osi współrzędnych, krok jest obliczany na podstawie optymalizacji jednowymiarowej.
- Metoda obracania współrzędnych (metoda Rosenbroke'a) jest metodą bezwarunkowej optymalizacji rzędu zerowego, w której realizowane jest zejście koordynacyjne, ale wzdłuż osi współrzędnych obróconych tak, że kierunek jednej z osi jest zbliżony do kierunku równoległego do dna wąwozu.
- Metoda simpleks (metoda odkształcalnego wielościanu lub metoda Neldera-Meada) jest metodą bezwarunkowej optymalizacji rzędu zerowego opartą na wielokrotnie powtarzanych operacjach konstruowania wielościanu z wierzchołkami (n + 1), gdzie n jest wymiarem przestrzeni o kontrolowanych parametrach i przemieszczania najgorszego wierzchołka najgorsza wartość funkcji celu) w kierunku środka ciężkości wielościanu.
- Metody pierwszego rzędu (metody wyszukiwania gradientowego) do poszukiwania ekstremum wymagają obliczenia wartości funkcji w punktach przestrzeni optymalizacji, a także określenia formy analitycznej pochodnych pierwszego rzędu w odniesieniu do kontrolowanych parametrów. Metody pierwszego rzędu są również nazywane metodami gradientowymi, ponieważ wektor pierwszych pochodnych funkcji F (X) w odniesieniu do zoptymalizowanych zmiennych X jest gradientem funkcji celu:
Gradient w punkcie bazowym jest ściśle prostopadły do powierzchni, a jego kierunek wskazuje kierunek najbardziej stromego wzrostu funkcji, a kierunek przeciwny (odpowiednio antyradientowy) wskazuje kierunek najbardziej stromego spadku funkcji. Metody gradientowe różnią się między sobą sposobem określania kierunku ruchu do optymalnego, wielkości kroku i czasu trwania wyszukiwania wzdłuż znalezionego kierunku, a także kryteriów zakończenia wyszukiwania.
Najbardziej popularne (pod względem nauczania w szkolnictwie wyższym) są następujące metody rozwiązywania problemów optymalizacyjnych pierwszego rzędu:
- Metoda gradientu zejścia - jest to metoda znajdowania lokalnego minimum (maksimum) funkcji poprzez poruszanie się po gradiencie z krokami zmiennymi (ułamkowymi), ustawionymi przez użytkownika.
- Najbardziej stromy sposób opadania - jest metodą znajdowania lokalnego minimum (maksimum) funkcji podczas przemieszczania się wzdłuż gradientu z optymalnym krokiem. Krok obliczania jest wybierany minimum funkcji celu (zminimalizowanej) w kierunku zniżania.
- Metoda gradientu koniugatu (metoda Fletchera Reevesa) - jest to metoda bezwarunkowej optymalizacji pierwszego rzędu, w której kierunek wyszukiwania w następnym kroku jest kierunkiem gradientu, dostosowanym do kierunku wyszukiwania w poprzednim kroku.
- Metoda zmiennej metryki (metoda Davidona-Fletchera-Powella) jest bezwarunkową metodą optymalizacji, w której pobierane jest rozwiązanie układu równań wyrażających warunki konieczne dla ekstremum.
- Metody drugiego rzędu do wyszukiwania ekstremum wymagają obliczenia wartości funkcji w punktach przestrzeni optymalizacji, a także określenia postaci analitycznej pochodnych pierwszego i drugiego rzędu w odniesieniu do kontrolowanych parametrów.
Najbardziej popularne (pod względem edukacji w szkolnictwie wyższym) są następujące metody rozwiązywania problemów optymalizacyjnych drugiego rzędu:
- Metoda Newtona - jest metodą bezwarunkowej optymalizacji, opartą na wykorzystaniu niezbędnych warunków bezwarunkowego ekstremum funkcji celu: równości do zera pierwszej pochodnej. Zgodnie z tą metodą macierz drugich pochodnych cząstkowych funkcji celu jest określana przez kontrolowane parametry (macierz Hesse).
- Metoda Marquardta jest bezwarunkową metodą optymalizacji mającą na celu rozwiązywanie problemów najmniejszych kwadratów. Jest to alternatywa dla metody Gaussa - Newtona. Można to uznać za kombinację tych ostatnich z metodą gradientu zniżania lub jako metodę przedziałów ufności.
Warunkowe metody optymalizacji
Klasyczny problem optymalizacji warunkowej jest sformułowany w następujący sposób: konieczne jest znalezienie wektora zmiennych 
w którym funkcja celu przyjmuje wartość ekstremalną (wartość maksymalną lub minimalną)
w danych warunkach (równości i / lub nierówności), a liczba ograniczeń m może być większa lub mniejsza niż liczba zmiennych n.
, j = 1,2, ..., m.
Innymi słowy, konieczne jest znalezienie ekstremum funkcji celu, pod warunkiem, że wartości argumentów funkcji należą do zakresu wartości dopuszczalnych, które tworzy system ograniczeń. Ekstremalna wartość funkcji celu odpowiada optymalnej kontroli. Graficznie sformułowanie problemu jest następujące:
Warunkowy problem optymalizacji dla funkcji dwóch zmiennych
W zależności od zastosowanej metody rozwiązania, metody optymalizacji warunkowej można podzielić na metody redukcji zadania do bezwarunkowej optymalizacji i metody bezpośredniego rozwiązania.
- Metody redukcji zadania do bezwarunkowej optymalizacji to zadanie optymalizacji warunkowej polegające na przekształceniu problemu programowania nieliniowego w sekwencję nieograniczonych zadań optymalizacyjnych poprzez skonstruowanie funkcji pomocniczych.
Najbardziej popularne (pod względem nauczania w szkolnictwie wyższym) są następujące metody rozwiązywania problemów optymalizacji optymalizacji warunkowej:
- Niepewna metoda mnożników Lagrange'a - jest to metoda optymalizacji warunkowej, skupiona na poszukiwaniu ekstremum funkcji celu w obecności typu równości.
- Warunki Kuhna-Tuckera są metodą rozwiązywania problemu optymalizacji programowania matematycznego z określonymi ograniczeniami. Metoda jest uogólnieniem metody mnożników Lagrange'a na przypadek ogólnego problemu programowania nieliniowego z ograniczeniami, zarówno w postaci równości, jak i nierówności.
- Metoda funkcji karnych to metoda lub grupa metod rozwiązywania problemów programowania matematycznego, polegająca na przekształceniu problemu optymalizacji warunkowej w bezwarunkowy problem optymalizacji poprzez utworzenie nowej funkcji celu, która uwzględnia ograniczenia problemu.
- Metody bezpośredniego rozwiązywania problemu optymalizacji warunkowej to problem optymalizacji warunkowej, polegający na przemieszczaniu się z jednego dopuszczalnego punktu, w którym spełnione są wszystkie ograniczenia, do innego dopuszczalnego punktu o najlepszej wartości funkcji celu.
Najbardziej popularne (pod względem nauczania w szkolnictwie wyższym) są następujące metody rozwiązywania problemów optymalizacji optymalizacji warunkowej:
- Zmniejszona metoda gradientu - Jest to metoda optymalizacji warunkowej, skoncentrowana na rozwiązywaniu problemów z ograniczeniami typu równości. Kierunek ruchu w tej metodzie określa zredukowaną funkcję gradientu.
- Metoda możliwych kierunków (metoda Zoytendeika) - ta metoda rozwiązywania problemów programowania matematycznego polega na przechodzeniu z jednego dopuszczalnego punktu do drugiego o najlepszej wartości funkcji celu.
Metody optymalizacji numerycznej są wdrażane i szeroko stosowane w różnych pakietach matematycznych. Jednocześnie dostępność gotowego oprogramowania (biblioteki i pakiety matematyczne) nie tylko nie eliminuje potrzeby badania metod, ale wręcz przeciwnie, czyni przygotowanie w tym kierunku jeszcze bardziej istotnymi. Wynika to z faktu, że przy rozwiązywaniu prawdziwego problemu specjalista wymaga kompetentnego matematycznego sformułowania problemu, jego formalizacji, uzasadnienia i wyboru najskuteczniejszej metody obliczeniowej, a także umiejętności oceny adekwatności i dokładności uzyskanych wyników.
Aby dodać komentarz do artykułu, zarejestruj się na stronie.