Podstawy optymalizacji

103000 - Wydział Elektroniki i Technik Informacyjnych

POPTY

3

Podstawowym celem wykładu jest zapoznanie studentów z pewnymi pakietami modelowania i rozwiązywania zadań optymalizacyjnych (AMPL, LP_SOLVE, MATLAB) oraz z pojęciem optimum, warunkami koniecznymi i dostatecznymi optymalności dla zadań optymalizacji bez ograniczeń i z ograniczeniami pozwalającymi na weryfikację poprawności uzyskiwanych z pakietów rozwiązań. Ponadto w ramach wykładu zapoznają się z elementami teorii dualności Lagrange`a oraz niektórymi z metod numerycznego rozwiązywania zadań optymalizacji. Szczególnie dużo uwagi poświęca się zadaniom programowania liniowego i kwadratowego. Celem dodatkowym jest zapoznanie studentów z pewnymi rzeczywistymi zastosowaniami metod optymalizacyjnych, formułowaniem modeli optymalizacyjnych oraz różnymi problemami, z którymi mogą się zetknąć w trakcie ich rozwiązywania, jak również praktycznym wykorzystaniem istniejących pakietów optymalizacyjnych.
Pierwszy wykład jest zwykle poświęcony omówieniu przykładowych zastosowań (...)

Podstawowym celem wykładu jest zapoznanie studentów z pewnymi pakietami modelowania i rozwiązywania zadań optymalizacyjnych (AMPL, LP_SOLVE, MATLAB) oraz z pojęciem optimum, warunkami koniecznymi i dostatecznymi optymalności dla zadań optymalizacji bez ograniczeń i z ograniczeniami pozwalającymi na weryfikację poprawności uzyskiwanych z pakietów rozwiązań. Ponadto w ramach wykładu zapoznają się z elementami teorii dualności Lagrange`a oraz niektórymi z metod numerycznego rozwiązywania zadań optymalizacji. Szczególnie dużo uwagi poświęca się zadaniom programowania liniowego i kwadratowego. Celem dodatkowym jest zapoznanie studentów z pewnymi rzeczywistymi zastosowaniami metod optymalizacyjnych, formułowaniem modeli optymalizacyjnych oraz różnymi problemami, z którymi mogą się zetknąć w trakcie ich rozwiązywania, jak również praktycznym wykorzystaniem istniejących pakietów optymalizacyjnych.

Pierwszy wykład jest zwykle poświęcony omówieniu przykładowych zastosowań metod optymalizacyjnych oraz różnych typów zadań, które powstają w trakcie formułowania ich formalnego opisu. Następne wykłady i odpowiednio zajęcia laboratoryjne dzielą się na trzy mniej więcej równe objętościowo bloki tematyczne: programowanie liniowe, optymalizacja bez ograniczeń i optymalizacja nieliniowa z ograniczeniami.


Treść wykładu

1. Zastosowania metod optymalizacyjnych, pojęcia i działy optymalizacji i programowania matematycznego.

PROGRAMOWANIE LINIOWE


2. Postać standardowa zadania programowania liniowego, zadania sprzeczne, nieograniczone, warunki optymalności, algebraiczne sformułowanie metody sympleks, zrewidowana metoda sympleks.
3. 
   Dwufazowa metoda sympleks, znajdowanie początkowego bazowego rozwiązania dopuszczalnego, jednofazowa metoda sympleks (metoda wielkiego "M").


4. Dualność w zadaniach programowania liniowego.


5. Dualna metoda sympleks, informacja o algorytmach wielomianowych do rozwiązywania zadań programowania liniowego, idea metody Karmarkara.

OPTYMALIZACJA NIELINIOWA BEZ OGRANICZEŃ


6. Pojęcie optimum, warunki konieczne i dostateczne optymalności pierwszego i drugiego rzędu dla różniczkowalnych zadań optymalizacji bez ograniczeń, kryteria weryfikacji warunków optymalności, własności zadań optymalizacji wypukłej.


7. Gradientowe metody rozwiązywania zadań bez ograniczeń, model liniowy i metoda najszybszego spadku, modele kwadratowe i metoda Newtona, zbieżność drugiego rzędu, metody quasinewtonowskie, zbieżność superliniowa.


8. Metody jednostajnych kierunków poprawy, testy stopu w minimalizacji kierunkowej - testy Goldsteina i reguła Armijo, gradientowe metody minimalizacji kierunkowej.


9. Bezgradientowe metody minimizacji kierunkowej, metoda sympleks Neldera-Meada jako przykład metody poszukiwań prostych do znalezienia minimum funkcji wielu zmiennych.

OPTYMALIZACJA NIELINIOWA Z OGRANICZENIAMI


10. Warunki konieczne optymalności Karusha-Kuhna-Tuckera dla zadań optymalizacji z ograniczeniami nierównościowymi oraz równościowymi, warunki regularności.


11. Warunki dostateczne optymalności dla zadań optymalizacji nieliniowej z ograniczeniami.


12. Metody bezpośredniej i uogólnionej eliminacji do rozwiązywania zadań programowania kwadratowego z ograniczeniami równościowymi. Metoda ograniczeń aktywnych do rozwiązywania zadań programowania kwadratowego z ograniczeniami nierównościowymi.


13. Teoria dualności Lagrange`a, pojęcie odstępu dualności, twierdzenia o słabej i silnej dualności.


14. Zadania dualne dla różnych typów zadań programowania liniowego oraz w zadaniach programowania kwadratowego. Metody wewnętrznej (barierowej) funkcji kary.


15. Niesympleksowe metody wielomianowe oparte na barierowej logarytmicznej funkcji kary do rozwiązywania zadań programowania liniowego.

1. 
   Rozwiązanie prostego zadania programowania liniowego przy pomocy dwufazowej tablicowej metody sympleks.


2. Sformułowanie zadania dualnego do danego prostego zadania programowania liniowego, rozwiązanie zadania dualnego przy pomocy dwufazowej metody sympleks i określenie rozwiązania zadania prymalnego na podstawie analizy warunków komplementarności.


3. Sformułowanie liniowego modelu optymalizacyjnego dla zadania optymalnego przydziału na zmiany pracowników obsługi tunelu pod kanałem La Manche, rozwiązanie go przy pomocy pakietu AMPL, analiza wyników.

1. Metody minimalizacji w kierunku.


2. Metody gradientów sprzężonych, metoda Newtona i metody quasinewtonowskie.


3. Sformułowanie modelu i rozwiązanie zadania ustalenia pozycji podróżnika poruszającego się po powierzchni Ziemi na podstawie sygnałów odbieranych z geostacjonarnych satelitów systemu GPS.

1. Rozwiązanie w środowisku MATLAB-a prostego zadania programowania kwadratowego z ograniczeniami równościowymi przy pomocy metody uogólnionej eliminacji.


2. Rozwiązanie w środowisku MATLAB-a prostego zadania programowania kwadratowego z ograniczeniami nierównościowymi przy pomocy metody ograniczeń aktywnych.


3. Budowa nieliniowego modelu optymalizacyjnego dla pewnego zadania mającego odniesienia do realnych zastosowań i rozwiązanie go przy pomocy pakietu AMPL lub innego swobodnie dostępnego w internecie, analiza wyników.

Pozycje podstawowe:


1. Stachurski A., A.P. Wierzbicki: Podstawy optymalizacji, Oficyna Wydawnicza PW, 1999.


2. Brdyś J., A. Ruszczyński: Metody optymalizacji w zadaniach, WNT 1985.


3. Findeisen W., J. Szymanowski i A. Wierzbicki: Teoria i metody optymalizacji.
PWN 1977.
Pozycje uzupełniające:


1. Bazaraa M.S., Sherali H.D., C.M. Shetty: Nonlinear Programming. Theory and Algorithms. (sec. edition) John Wiley & Sons, New York 1993.


2. Gill P., W. Murray, M. Wright: Practical Optimization. Academic Press 1981.


3. Fletcher R.: Practical Methods of Optimization. (sec. edition) John Wiley & Sons, Chichester 1987.


4. Bertsekas D.P.: Nonlinear Programming. Athena Scientific,Belmont, Massachusets 1995.

Uzyskanie powyżej połowy punktów z laboratoriów (22 z 42) oraz powyżej
połowy punktów z egzaminu (30 z 58); punkty sumują się do 100, oceny są
wystawiane zgodnie ze zwyczajową skalą:

51-60 ocena 3

61-70 ocena 3,5

71-80 ocena 4

103100 - Instytut Automatyki i Informatyki Stosowanej

103100 - Instytut Automatyki i Informatyki Stosowanej

103100 - Instytut Automatyki i Informatyki Stosowanej

103100 - Instytut Automatyki i Informatyki Stosowanej

103100 - Instytut Automatyki i Informatyki Stosowanej