1. Do podanego zadania prymalnego zbudować zadanie dualne.
2. Tw. weierstrassa.

Jeżeli zbiór omega jest zamknięty i ograniczony to każda funkcja ciągła osiąga w tym zbiorze swoje maksimum i minimum (w różnych punktach)

3. Różnica między minimum silnym a spłaszczonym.
4. Jeżeli wszystkie wartości własne hesjanu są dodatnie to czy istnieje ekstremum? Jeżeli tak to jakiego rodzaju?
5. Jaką metodę wybrałabyś/wybrałbyś do rozwiązania zadania nieliniowego bez ograniczeń? Uzasadnij. Podaj, jakie muszą być spełnione warunki.
6. Opisz metodę Lagrange'a.
7. Na czym polega rozwiązywanie metodą zewnętrznej funkcji kary?

8. Różnica między metodami matematycznymi a heurystycznymi.

Nie wiem, czy to coś pomoże, ale metody heurystyczne to takie, w których nie zna się dokładnego algorytmu rozwiązywania, bo np. problem jest zbyt duży do ogarnięcia go w ramy.

Zna ktoś odpowiedź na pytania:
1. Jaka metode zastosować do zadania w którym f celu jest jednokrotnie różniczkowalna?

Wydaje mi się że Metode najszybszego spadku, W pierwszym może być, że każda metoda gradientowa, bo pierwsza różniczka to gradient... jak się nie mylę.... A co do 1 to można stosować metode najszybszego spadku, ale również mozna stosować wtedy metody poszukiwania prostych, dlatego, że są łatwiejsze niż met. Gradientowe

2. Jaka metode zastosować do zadania w którym f celu jest niejawna?

A tutaj chyba Metody Poszukiwania Prostych, bo wnioskuje, że poprzez ruchy robocze metody te wyznaczają właśnie funkcje celu. Ale moge sie mylić

1. Jeśli zadanie pierwotne ZPL ma skończone rozwiązanie optymalne, to czy odpowiadające mu zadanie dualne ZPL ma skończone rozwiązanie optymalne. Jeśli tak, to jaką przyjmuje ono wartość. Tak, przyjmuje ona wartość taką samą

2. Podaj różnicę pomiędzy minimum lokalnym a minimum globalnym. Minimum lokalne jest określane na danym podzbiorze zbioru rozwiązań dopuszczalnych, a minimum globalne jest to punkt minimalny określony dla całego zbioru rozwiązań dopuszczalnych.

3. Czy wektor gradientu funkcji wskazuje kierunek najszybszego spadku wartości funkcji celu. Odpowiedź uzasadnij. Nie, wynika to z definicji gradientu, która mówi iż jest to kierunek najszybszego wzrostu wartości danego pola skalarnego

4. Jeśli wszystkie wartości własne hesjanu funkcji celu są dodatnie to czy funkcja te posiada optimum. Jeśli tak to jakiego typu jest to optimum. Tak, posiada, jest to minimum silne lokalnie

5. Mając dokonać optymalizacji funkcji celu w postaci funkcji nieliniowej, przy czym nie istnieją żadne ograniczenia, jaką metodę optymalizacji wybrałbyś/wybrałabyś i dlaczego. Czy muszą zostać spełnione dodatkowe warunki ?? Wybrałabym metody poszukiwania prostych. Metody te są metodami dokładnymi, nie ma w nich konieczności różniczkowania funkcji celu, więc nie tworzą się dodatkowe ograniczenia

6. Na jakim twierdzeniu opierają się analityczne metody rozwiązywania zadań optymalizacji nieliniowej z ograniczeniami równościowymi i nierównościowymi. Na twierdzeniu Kuhna-Tuckera

7. Na czym polega rozwiązywanie ZPN z ograniczeniami przy pomocy metod funkcji kary? Polegają na zastąpieniu zadania z ograniczeniami ciągiem zadań bez ograniczeń. Ich rozwiązania tworzą ciąg, który powinien zbiegać do rozwiązania zadania pierwotnego. Zwykle do funkcji celu zadania z ograniczeniami dodaję się karę za naruszenie ograniczeń

8. Jakimi metodami optymalizacji można rozwiązać zadanie, w którym funkcja celu jest nie ciągłą funkcją nieliniową. Metody programowania nieliniowego z ograniczeniami

1. Wyjaśnienie pojęcia optymalizacja. Omówienie procesu optymalizacji. Podstawowe pojęcia i definicje. Podział zadań optymalizacji.

Optymalizacja jest to dziedzina nauki zajmująca się wyznaczaniem spośród wszystkich dopuszczalnych rozwiązań danego problemu optymalizacyjnego rozwiązania najlepszego, z określonego punktu widzenia. Wybór najlepszego rozwiązania zależy od celu i wymagań określonych w matematycznym sformułowaniu problemu.

Proces optymalizacji

- sformułowanie matematyczne postawionego problemu

- rozstrzygnięcie możliwości istnienia rozwiązania

- zbadanie własności zadania i na tej podstawie dobranie algorytmu rozwiązania

- interpretacja wyników obliczeń

Pojęcia: Zadanie z ograniczeniami – jest to zadanie którego rozwiązanie musi spełniać pewne ściśle określone warunki (ograniczenia mogą być równościowe lub nierównościowe)

Zadanie programowania całkowitoliczbowego lub dyskretnego to zadanie w których występuje konieczność zachowania całkowitych wartości wektora x. Zadanie (problem) optymalizacji – w sensie matematycznym jest to proces poszukiwania ekstremum pewnej funkcji, będącej matematycznym opisem badanych zjawisk, nazywaną funkcją celu, kryterium, bądź wskaźnikiem jakości. W większości zagadnień technicznych jest to funkcja wielu zmiennych, które nazywamy zmiennymi decyzyjnymi.

Zadania Programowania Liniowego. Metoda graficzna. Metoda Sympleks. Teoria dualności. 

Zadanie programowania liniowego (ZPL) jest to zadanie w którym definiująca je funkcja celu i ograniczenia są funkcjami liniowymi.

x ≥ 0,  m ≤ n

x – macierz kolumnowa zmiennych decyzyjnych

b – macierz kolumnowa prawych stron ograniczeń

c – macierz kolumnowa zawierająca współczynniki zwane cenami lub kosztami.

Metoda graficzna. Metoda graficzna to metoda rozwiązania ZPL polegająca na wyznaczeniu wierzchołków wielościanu wypukłego, tworzącego obszar możliwych rozwiązań Ω, a następnie wyznaczeniu wartości funkcji celu w tych wierzchołkach i wybraniu najlepszego rozwiązania.

Metoda sympleks. Metoda sympleks polega na przeszukiwaniu wierzchołków obszaru rozwiązań dopuszczalnych Ω w sposób uporządkowany, poprzez generowanie ciągu dopuszczalnych rozwiązań bazowych {x¹ , x² , … , x^k}, odpowiadających tym wierzchołkom, takich, aby kolejne rozwiązania były lepsze (lub przynajmniej nie gorsze) od poprzednich. Proces ten trwa tak długo, aż osiągnięte zostanie rozwiązanie optymalne. A zatem metoda sympleks jest metodą iteracyjną. W każdej z iteracji wyznacza się rozwiązanie bazowe a następnie sprawdza czy jest ono optymalne. Jeśli aktualne rozwiązanie bazowe jest rozwiązaniem optymalnym wówczas następuje zakończenie procesu optymalizacji. Wyniki poszczególnych iteracji zestawia się w kolejnych tablicach sympleksowych o wymiarach (m+l)x (n+1), gdzie m- liczba ograniczeń, n - liczba zmiennych decyzyjnych

Twierdzenie o dualności. Jeśli zadanie pierwotne ZPL (bądź dualne) ma skończone rozwiązanie optymalne, to odpowiadające mu zadanie dualne ZPL (bądź pierwotne) również posiada skończone rozwiązanie optymalne a optima funkcji celu są sobie równe. tj. $_{x}^{\min}{f(x)} =_{\lambda}^{\max}{f'(\lambda)}$

1. Zadania Programowania Nieliniowego bez ograniczeń. Metody poszukiwania prostych. Metoda Najszybszego Spadku. 

Metody poszukiwania prostych (metoda Gaussa-Seidla, Hooka-Jeevesa, Rosenbrocka, metoda sympleksu Neldera-Meada)

Metoda Hooka Jeevesa

W metodzie Hooka Jeevesa w każdym kroku iteracyjnym występują dwa rodzaje ruchów, a mianowicie ruch próbny i ruch roboczy. Ruch próbny służy do badania przebiegu funkcji celu w niewielkim obszarze, wokół punktu startowego, wyznaczanym za pomocą parametru omawianej metody, jakim jest długość kroku. Badanie to polega na wykonywaniu kroków próbnych wzdłuż n-kierunków ortogonalnej bazy (gdzie n - oznacza liczbę zmiennych decyzyjnych) i sprawdzeniu wartości funkcji celu w wyznaczonych punktach. Następnie wykonuje się krok roboczy, którego wektor odpowiada sumie geometrycznej wszystkich pomyślnych kroków próbnych. Krokiem pomyślnym nazywany jest krok, w wyniku którego następuje zmniejszenie wartości funkcji celu [3, 6], Inaczej mówiąc krok roboczy polega na przejściu, w sposób ściśle zdeterminowany, do kolejnego obszaru badania przebiegu funkcji celu. W nowo wyznaczonym obszarze powtarza się kroki próbne, ale tylko w sytuacji, gdy przynajmniej jeden z kroków próbnych, wykonanych w poprzedniej iteracji, był pomyślny. W przeciwnym razie pozostaje się w poprzednio badanym obszarze i cykl poszukiwania rozpoczyna od nowa zmniejszając długość kroku.

Jako kryterium zatrzymania w metodzie Hooka Jeevesa przyjmuje się warunek, że aktualna długość kroku a jest mniejsza od założonej liczby e, określającej wymaganą dokładność obliczeń.

Metoda Rosenbrocka. Metoda Rosenbrocka jest metodą podobną do metody omawianej poprzednio. Jednak w metodzie tej kierunki poszukiwań nie pozostają stałe, ale w niektórych przypadkach ulegają zmianom w wyniku obrotu. Dlatego to metoda ta często nazywana jest metodą obrotu układu współrzędnych. W metodzie Rosenbrocka ruchy próbne tworzą cykle, a te z kolei tworzą etapy. Cykl tworzą ruchy próbne wykonane w ustalonych kierunkach, przy czym kierunki początkowe są zgodne z kierunkami kartezjańskiego układu współrzędnych. Na wstępie w każdym z kierunków kartezjańskiego układu współrzędnych wykonuje się kolejno po jednym kroku o długości α. Jeśli ruch próbny prowadzi do zmniejszenia wartości funkcji celu, to mówi się o sukcesie. Jeśli nic, to mówi się o porażce. W przypadku sukcesu w następnym cyklu długość kroku a w danym kierunku mnoży się przez γ (gdzie γ to współczynnik korekcyjny zwiększający długość kroku a; γ>l), a w przypadku porażki długość kroku a mnoży się przez β (gdzie β to współczynnik korekcyjny zmniejszający długość kroku a; 0<β<1). Etap składa się z ilości cyklów niezbędnych do uzyskania w każdym kierunku przynajmniej jednego sukcesu i jednej porażki. Następny etap rozpoczyna się od określenia nowego zbioru ortogonalnych kierunków, przy czym pierwszy kierunek jest wyznaczany przez punkt początkowy i punkt końcowy poprzedniego etapu. Pozostałe kierunki są wyznaczane za pomocą algorytmu obrotu współrzędnych. W metodzie Rosenbrocka stosuje się następujące kryteria zatrzymania:

- z góry narzuconą ilości iteracji;

- z góry założoną wielkość różnicy pomiędzy punktem początkowym a końcowym.

Metoda Powella. Metoda Powella polega na poszukiwaniu minimum funkcji celu poprzez przeszukiwanie przestrzeni n - wymiarowej w kolejnych iteracjach, wzdłuż n wyznaczonych kierunków, stanowiących bazę tej przestrzeni, gdzie n oznacza liczbę zmiennych decyzyjnych. Na zakończenie każdej iteracji dokonywana jest minimalizacja wzdłuż nowo wyznaczonego (n+l)-go kierunku poszukiwań. W przeciwieństwie do poprzednio omawianych metod, w metodzie Powella kierunki poszukiwań są ze sobą powiązane, bowiem w każdej następnej iteracji do zbioru kierunków poszukiwań dodawany jest nowo wyznaczany kierunek dⁿ⁺¹ , wyznaczany ze wzoru [4]:$d^{n + 1} = \frac{x^{n} - x^{0}}{\left\| x^{n} - x^{0} \right\|}$,a usuwany jest kierunek d¹. W tej metodzie jako kryterium zatrzymania wykorzystuje się warunek:
∥x_n + 1^k−x₀^k∥ ≤ ε x₀^k −  przyjety punkt bazowy k − tej iteracji

x_n + 1^k−punkt dla którego funkcja celu osiąga najmniejszą wartość wzdłuż n+1 kierunku w k-tej iteracji
ε - z góry założona dokładność obliczeń

Metoda Najszybszego Spadku.
Jest to najprostsza metoda oparta na modelu liniowym minimalizowanej funkcji, jako kierunek wybiera się: d^(k) = −∇f(x^(k)). Punkt x^(k+1) znajdujemy z zależności: x^(k+1) = x^(k) + α^* • d^(k)

W metodzie najszybszego spadku wartość α_k^* wybierana jest tak, aby funkcja f(x) osiągała w punkcie x^(k) + 1 minimum w kierunku: d^(k) = −∇f(x^(k))

1. Zadania Programowania Nieliniowego bez ograniczeń. Metoda Newtona i jej modyfikacja. Metody quasi-newtonowskie.

Metoda Newtona i jej modyfikacja

W metodzie Newtona zakłada się, że funkcja celu f(x^k), która jest ściśle wypukła w dół, posiada ciągłe pochodne cząstkowe do drugiego rzędu włącznie. Wówczas przy założeniu, iż punkt x^k jest pewnym przybliżeniem poszukiwanej wartości minimalnej x^* funkcji celu f(x) oraz znając wartości gradientu ∇f(x^k) i hesjanu H(x^k) funkcji celu w tym punkcie, można na podstawie szeregu Taylora funkcję celu f(x) aproksymować w otoczeniu punktu x^k funkcją kwadratową F_k(x), opisaną następująco:

$$F_{k}\left( x \right) = f\left( x^{k} \right) + \nabla f\left( x^{k} \right) \bullet \left( x - x^{k} \right) + \frac{1}{2} \bullet \left\lbrack H\left( x^{k} \right) \bullet {(x - x^{k})}^{2} \right\rbrack$$

gdzie:

x - minimum funkcji kwadratowej F_k(x) aproksymującej funkcję celu f(x) w punkcie x^k;

∇f(x^k)− gradient funkcji celu /(x) w punkcie x*;

H(x^k)− macierz hesjanu funkcji celu f(x) w punkcie x^k

Zakładając, iż kolejnym przybliżeniem poszukiwanej wartości minimalnej x^* funkcji celu f(x) jest punkt x^k+1, będący punktem minimum funkcji kwadratowej F_k(x), a więc spełniający warunek:

∇F(x^k + 1) = ∇f(x^k) − H(x^k) • (x^k + 1−x^k) = 0

uzyska się wzór na wyznaczanie wartości przybliżeń x^k+1 poszukiwanego minimum x^* funkcji celu f(x) w kolejnych iteracjach:

x^k + 1 = x^k − H(x^k)⁻¹ • ∇f(x^k)

Kryterium zatrzymania w metodzie Newtona przyjmuje postać:

∥x^k + 1−x^k∥ ≤ ε

gdzie ε jest przyjętą żądaną dokładnością obliczeń, a ||.|| oznacza normę euklidesową wektora.

Metody quasi-newtonowskie. W zadaniach praktycznych metoda Newtona nie znajduje szerokiego zastosowania ze względu na jej małą efektywność i trudności obliczeniowe związane z koniecznością wyznaczania w każdej iteracji macierzy drugich pochodnych (hesjan H(x^k )) oraz obliczania macierzy odwrotnej do macierzy hesjanu H(x^k)^-1 i mnożenia jej przez wektor gradientu∇f(x^k) (H(x^k)⁻¹ • ∇f(x^k)). W metodach quasi - newtonowskich, zwanych również metodami zmiennej metryki, powyższe niedogodności eliminuje się zastępując bądź to macierz hesjanu H(x^k), bądź to macierz do niego odwrotną H(x^k)^-1 odpowiednimi przybliżeniami. Różnice występujące pomiędzy poszczególnymi metodami zmiennej metryki polegają jedynie narożnym sposobie konstruowania uaktualnienia macierzy D^k+1, będącej aproksymacją odwrotności macierzy hesjanu H(x^k)^-1 bądź konstruowania uaktualnienia macierzy B^k+1. będącej aproksymacją macierzy hesjanu H(x^k)

Główną zaletą metod quasi newtonowskich jest wykorzystywanie informacji wyłącznie o wartości gradientu funkcji celu ∇f(x^k) w aktualnym punkcie poszukiwań x^k oraz kolejnym po nim następującym x^k+1.

Do grupy metod zmiennej metryki zalicza się m.in.: metodę Davidona (w skrócie D), metodę Pearsona (w skrócie P), metodę Wolfe'a-Broydena-Davidona (w skrócie WBD), metodę Davidona-Fletchera-Powella (w skrócie DFP), metodę Broydena-Fletchera- Goldfarba-Shanno (w skrócie BFGS).

1. Zadania Programowania Nieliniowego z ograniczeniami. Metody Funkcji Kary. Metoda Mnożników Lagrange’a.

Metoda mnożników Lagrange’a, stosowana do rozwiązywania zadań programowania nieliniowego z ograniczeniami, polega na wprowadzeniu do postaci funkcji celu f(x) dodatkowych mnożników, zależnych od typu ograniczeń nałożonych na funkcję celu. Polega ona na wyznaczeniu pary $\left( \hat{x},\bigwedge \right)$, gdzie ⋀ ≡ (λ,μ) stanowiącej punkt siodłowy funkcji Lagrange’a, tj. punktu w którym funkcja ta osiąga minimum względem x i maksimum względem ⋀, przy μ>0.

Zaletą metody mnożników Lagrange'a jest możliwość dokonywania w dość łatwy i w miarę szybki sposób obliczeń analitycznych oraz możliwość dostosowania wprowadzanych modyfikacji w zależności od typu ograniczeń występujących w zadaniu, co pozwala na uzyskiwanie dokładnych wyników.

1. Zadania Programowania Nieliniowego z ograniczeniami. Metody Funkcji Kary. Metoda Transformacji Zmiennych.

Metodę transformacji zmiennych decyzyjnych można stosować tylko w przypadku, gdy pewne zmienne decyzyjne (czasami wszystkie) są ograniczone z dołu i z góry przez stałe wartości liczbowe, co zapisano zależnościami.

W metodzie zamiany (transformacji) zmiennych przyjmuje się, iż zmienna decyzyjna x_n jest zastępowana przez nową zmienną:x_n ≡ γ_n(u_n) która może przyjmować dowolne wartości z zakresu:

u_n ∈ ( − ∞, +∞)

W zależności od rodzaju ograniczeń nałożonych na poszczególne zmienne decyzyjne stosuje się odpowiednie podstawienia.

Następnie do funkcji celu f(x) w miejsce poszczególnych zmiennych decyzyjnych x_n. podstawia się wartość wyrażoną zależnością x_n ≡ γ_n(u_n). W ten sposób otrzymywane jest zadanie optymalizacyjne bez ograniczeń równoważne zadaniu z ograniczeniami.

Należy jednak podkreślić, że funkcje γ_n(u_n) muszą być takie, aby w nowo utworzonej funkcji kryterialnej F(u)=f[γ₁(u₁), …, γ_n(u_n)] nie pojawiły się nowe ekstrema lokalne.

Metoda polegająca na transformacji zmiennych decyzyjnych jest metodą mało efektywną ponieważ zmodyfikowana funkcja kryterialna na ogół staje się bardzo złożona.

1. Algorytmy genetyczne. Optymalizacja wielokryterialna.

Algorytmy genetyczne to algorytmy oparte na naśladowaniu natury, bowiem ewolucja naturalna jest swoistym procesem optymalizacyjnym. Sposób działania algorytmów genetycznych nieprzypadkowo przypomina zjawisko ewolucji biologicznej i doboru naturalnego bowiem ich twórca, John Holland, opierając się właśnie na teorii Darwina stworzył algorytmy genetyczne. Według darwinowskiej teorii walki o życie z wielu osobników żyjących w danym środowisku przeżyją ci, którzy posiadają cechy czyniące ich najlepiej przystosowanymi do środowiska. Oni to mają większe szanse na przeżycie i szybciej rozmnażają się powodując dalsze rozpowszechnianie się ich cech. Osobniki słabsze, tzn. gorzej przystosowane, zostają wyparte przez inne i giną. A zatem natura również poszukuje rozwiązania optymalnego

Dodatkowo w algorytmach genetycznych występuje zrandomizowana wymiana informacji, konieczna do otrzymania najlepszych wyników optymalizacji.

Schemat algorytmu genetycznego i jego podstawowe operacje

Na klasyczny algorytm genetyczny, choć całkiem wystarczający dla wielu praktycznych zagadnień, nazywany także elementarnym lub prostym algorytmem genetycznym, składają się następujące kroki:

- Inicjacja czyli wybór populacji początkowej;

- Ocena przystosowania osobników;

- Sprawdzenie warunku zatrzymania;
- Selekcja osobników;
- Zastosowanie operatorów genetycznych;
- Utworzenie populacji potomnej;
- Wynik w postaci „najlepszego" osobnika.

Inicjacja, czyli utworzenie populacji początkowej, polega na wyborze żądanej liczby chromosomów (osobników) reprezentowanych przez ciągi binarne określonej długości.

Selekcja polega na wybraniu, na podstawie obliczonych wartości funkcji przystosowania, osobników przeznaczonych do reprodukcji. Najczęściej stosowaną metodą selekcji jest metoda ruletki. Metoda ta dokładnie zostanie omówiona w części praktycznej.

Reprodukcja jest procesem, w którym osobnik jest kopiowany bez zmian do następnego pokolenia w stosunku zależnym od wartości jego przystosowania do środowiska. Osobniki o wyższym przystosowaniu posiadają większe prawdopodobieństwo wprowadzenia jednego lub więcej potomków do następnego pokolenia.

Krzyżowanie odpowiada rozmnażaniu płciowemu, gdyż polega na wymianie części materiału genetycznego między parą osobników. Operacja ta przebiega w dwóch etapach. W pierwszym etapie losowo wybiera się pary rodzicielskie. Następnie każda z par ulega krzyżowaniu.

Mutacja polega na zachodzącej z niewielkim prawdopodobieństwem zamianie losowo wybranego pojedynczego bitu w chromosomie i skopiowaniu tak zmienionego osobnika do następnej populacji. Operacja ta zapobiega ewentualnej utracie interesującego materiału genetycznego, względnie pozwala na pojawienie się nowego.

Funkcja wypukła:

Funkcja ciągła h(x),  x ∈ Rⁿ jest wypukła w dół w przestrzeni Rⁿ, jeżeli dla dowolnych dwóch punktów x^′ ∈ Rⁿ x″∈Rⁿ oraz każdego α ∈ ⟨0,1⟩ zachodzi: h((1−α)x^′+αx^″) ≤ (1−α)h(x^′) + αh(x^″) Jeżeli zachodzi nierówność przeciwna, to funkcję nazywamy wypukłą w górę w przestrzeni Rⁿ.

Gdy nierówność jest ostra, to funkcję nazywamy ściśle wypukłą w dół.

Warunek konieczny istnienia ekstremum: ${(\nabla f)}_{\hat{x}} = 0$

f(x) osiąga w punkcie $\hat{x} \in \Omega\ $minimum, jeżeli dla każdego x ∈ Ω zachodzi nierówność $f(\hat{x}) \leq f(x)$

f(x) osiąga w punkcie $\hat{x} \in \Omega\ $maksimum, jeżeli dla każdego x ∈ Ω zachodzi nierówność $f(\hat{x}) \geq f(x)$

Minimum silne:

Jeżeli funkcja celu osiąga minimalną wartość tylko w jednym punkcie x^* ∈ Ω , a więc istnieje tylko jeden taki punkt x^* ∈ Ω, że w każdym punkcie x ∈ Ω różnym od x^* zachodzi f(x^*)<f(x), to mówimy, że w punkcie x^* występuje minimum silne.

Maksimum silne:

Jeżeli funkcja celu osiąga maksymalną wartość tylko w jednym punkcie x^* ∈ Ω , a więc istnieje tylko jeden taki punkt x^* ∈ Ω, że w każdym punkcie x ∈ Ω różnym od x^* zachodzi f(x^*)>f(x), to mówimy, że w punkcie x^* występuje minimum silne.

Minimum spłaszczone:

Jeżeli w zbiorze Ω można wskazać zbiór Ω^* taki, że dla każdego x^* ∈ Ω^* zachodzi f(x^*) = const oraz dla każdego x^* ∈ Ω^* i x ∈ Ω − Ω^* zachodzi f(x^*) < f(x)to mówimy, że w zbiorze Ω^* funkcja f(x) ma minimum spłaszczone.

Maksimum spłaszczone:

Jeżeli w zbiorze Ω można wskazać zbiór Ω^* taki, że dla każdego x^* ∈ Ω^* zachodzi f(x^*) = const oraz dla każdego x^* ∈ Ω^* i x ∈ Ω − Ω^* zachodzi f(x^*) > f(x)to mówimy, że w zbiorze Ω^* funkcja f(x) ma maksimum spłaszczone.

Operatory genetyczne:

Krzyżowanie – wymiana informacji genetycznej między parami chromosomów.

Mutacja – wymiana pojedynczego bitu w chromosomie z bardzo małym prawdopodobieństwem.

Metoda Lagrange’a

Służy do obliczania ekstrema funkcji przy ograniczeniach równościowych.

$L\left( x,\lambda \right) = f\left( x \right) + \sum_{i = 1}^{I}{\lambda_{i}g_{i}(x)}$ wartości funkcji zależą od zmiennych λ zwanych mnożnikami lagrange’a λ ≡ (λ_i, …, λ_I)

Warunek konieczny istnienia ekstremum f(x) p.o. równościowych g_i(x) = 0

Różnice pomiędzy metodą Newtona a quasi-newtonowskimi.

W metodzie Newtona w każdej iteracji wyznaczamy macierze drugich pochodnych (hesjan H(x^k)) oraz obliczamy macierz odwrotną do macierzy hesjanu H(x^k)^-1 i mnożymy ją przez wektor gradientu, co powoduje trudności obliczeniowe. W metodach quasi-newtonowskich trudności obliczeniowe eliminuje się wprowadzając przybliżenia macierzy hesjanu bądź odwrotności macierzy hesjanu. W tej metodzie wykorzystujemy informacje wyłącznie o wartości gradientu funkcji celu.

Metoda funkcji Kary

Wyróżniamy 3 metody f. Kary:

- metoda wewnętrznej f. kary

- metoda zewnętrznej f. kary

- metoda mieszanej f. kary

Metoda wewnętrzna (gdy nie można przekroczyć warunków ograniczających)

$\Phi\left( x,r \right) \equiv \frac{1}{r}B\left( x \right),\ \ r \in (0, + \infty)$ przy czym B(x) musi być funkcją ciągłą określoną w zbiorze Ω będącym wewnątrz zbioru, ponadto musi spełniać warunek: dla każdego $x \in \dot{\Omega}$ musi być B(x)≥0 oraz b(x) = +∞ y – punkt brzegowy zbioru Ω

Metoda zewnętrzna – metoda bardziej ogólna, może być stosowana przy warunkach równościowych.

Φ(x,r) ≡ rK(x),   r ∈ (0, +∞) przy czym K(x) musi być funkcją ciągłą dla każdego x ∈ R^N. Metoda ta w przeciwieństwie do metody wewnętrznej nie zapewnia, że wszystkie x^k należą do zbioru Ω

Metoda mieszana – stosuje się ją gdy istnieją pary warunków ograniczających równoważne równościowym i pewne warunki nierównościowe były zawsze spełnione. $\Phi\left( x,r \right) \equiv \frac{1}{r}B\left( x \right) + rK(x)$

Optymalizacja wielokryterialna

Polega na poszukiwaniu zbioru Pareto punktów niezdominowanych. Zbiór Pareto jest to zbiór w którym nie można poprawić żadnego z kryteriów nie pogarszając pozostałych. Elementy tego zbioru są nieulepszalne i nazywamy je optymalnymi w sensie Pareto. Wśród zadań optymalizacji wielokryterialnej możemy wyróżnić dwa przypadki szczególne: poszukiwanie niezdominowanego punkty oraz poszukiwanie zbioru punków zdominowanych.