Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Algorytmy i metody optymalizacji
Koordynator przedmiotu:
Rajmund Kożuszek
Status przedmiotu:
Fakultatywny dowolnego wyboru
Poziom kształcenia:
Studia II stopnia
Program:
Informatyka
Grupa przedmiotów:
Przedmioty techniczne - zaawansowane
Kod przedmiotu:
AMO
Semestr nominalny:
4 / rok ak. 2021/2022
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
1. liczba godzin kontaktowych – 60 godz., w tym obecność na wykładach 30 godz., spotkania projektowe – 30 godz. 2. praca własna studenta –60 godz., w tym przygotowanie do kolokwiów 10 godz., przygotowanie do realizacji projektów – 10 godz. realizacja projektów – 30 godz. opracowanie sprawozdań z projektów – 10 godz. Łączny nakład pracy studenta wynosi 120 godz., co odpowiada 4 pkt. ECTS.
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
2,00 pkt. ECTS, co odpowiada 60 godz. kontaktowym
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
1,67 pkt. ECTS, co odpowiada 10 godz. na przygotowanie do realizacji projektów, plus 30 godz. na realizację projektów, plus 10 godz. na opracowanie sprawozdań z projektów
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia0h
  • Laboratorium0h
  • Projekt30h
  • Lekcje komputerowe0h
Wymagania wstępne:
Zalecane jest wcześniejsze zaliczenie przedmiotu Metody Numeryczne
Limit liczby studentów:
30
Cel przedmiotu:
Celem przedmiotu jest zapoznanie studentów z algorytmami optymalizacji numerycznej, opanowanie praktycznej umiejętności korzystania z nich, formułowania modelu optymalizacyjnego zadania oraz wybrania odpowiedniego algorytmu i oceny jakości numerycznej uzyskiwanego rozwiązania.
Treści kształcenia:
Wykład: Podstawowym celem wykładu jest zapoznanie studentów 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ń. Studenci zapoznają się również z pewnymi pakietami modelowania i rozwiązywania zadań optymalizacyjnych (AMPL, MATLAB). Ponadto w ramach wykładu przedstawione zostaną elementy teorii dualności Lagrange`a oraz wybrane metody 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, w tym w szczególności z liniowymi zadaniami mieszania/diety oraz klasyfikacji cech i wektorowych maszyn nośnych w data-miningu. Treść wykładu 1. Zastosowania metod optymalizacyjnych, pojęcia i działy optymalizacji i programowania matematycznego. (2h) OPTYMALIZACJA NIELINIOWA BEZ OGRANICZEŃ 2. Omówienie zastosowań optymalizacji bez ograniczeń. 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. (2h) 3. Gradientowe metody rozwiązywania zadań bez ograniczeń, model liniowy i metoda najszybszego spadku, modele kwadratowe i metoda Newtona, algorytm Levenberga-Marquardta, zbieżność drugiego rzędu, metody quasinewtonowskie, zbieżność superliniowa, metody gradientów sprzężonych. (2h) 4. Metody obszaru zaufania, metody jednostajnych kierunków poprawy, testy stopu w minimalizacji kierunkowej - testy Goldsteina i reguła Armijo, gradientowe metody minimalizacji kierunkowej. (2h) 5. Bezgradientowe metody minimizacji kierunkowej, metoda sympleks Neldera-Meada jako przykład metody poszukiwań prostych do znalezienia minimum funkcji wielu zmiennych. (2h) PROGRAMOWANIE LINIOWE 6. Zastosowania programowania liniowego. Postać standardowa zadania programowania liniowego, zadania sprzeczne, nieograniczone, warunki optymalności, metoda sympleks w wersji tablicowej. (2h) 7. Dwufazowa metoda sympleks, znajdowanie początkowego bazowego rozwiązania dopuszczalnego, jednofazowa metoda sympleks (metoda wielkiego "M"). (2h) OPTYMALIZACJA NIELINIOWA Z OGRANICZENIAMI 8. Zastosowania optymalizacji nieliniowej z ograniczeniami. Warunki konieczne i dostateczne optymalności Karusha-Kuhna-Tuckera dla zadań optymalizacji z ograniczeniami nierównościowymi oraz równościowymi, warunki regularności. (2h) 9. Teoria dualności Lagrange`a, pojęcie odstępu dualności, twierdzenia o słabej i silnej dualności. Zadania dualne dla różnych typów zadań programowania liniowego oraz kwadratowego. (2h) PROGRAMOWANIE KWADRATOWE 10. Zastosowania programowania kwadratowego. Metoda uogólnionej eliminacji do rozwiązywania zadań programowania kwadratowego z ograniczeniami równościowymi. (2h) 11. Metoda ograniczeń aktywnych do rozwiązywania zadań programowania kwadratowego z ograniczeniami nierównościowymi. (2h) METODY ROZWIĄZYWANIA ZADAŃ Z OGRANICZENIAMI 12. Metody sekwencyjnego programowania kwadratowego. (2h) 13. Metody zewnętrznej i wewnętrznej (barierowej) funkcji kary. (2h) 14. Metody rozszerzonej funkcji Lagrange`a. (2h) 15. Niesympleksowe metody wielomianowe, metoda Karmarkara oraz metody oparte na barierowej logarytmicznej funkcji kary do rozwiązywania zadań programowania liniowego. (2h) Projekt: Celem zajęć projektowych jest opanowanie przez studentów praktycznych umiejętności korzystania z metod optymalizacyjnych i przeprowadzania pewnych przykładowych obliczeń w środowisku MATLAB-a oraz AMPL (w ramach programowania liniowego również LP_SOLVE). Dopuszczalne jest również realizowanie implementacji algorytmów w języku MATLAB-a bądź innych języków programowania. W początkowej fazie wymaga to zapoznania studentów z pracą z MATLAB-em oraz AMPL-em. Projekty mają dwojaki cel: opanowanie umiejętności formułowania modelu optymalizacyjnego zadania oraz wybrania odpowiedniego algorytmu i oceny jakości numerycznej uzyskiwanego rozwiązania. Przewidywane są dwa projekty. Pierwszy o charakterze wprowadzającym dotyczący zagadnień bez ograniczeń oraz drugi, bardziej wymagający dotyczący zagadnień z ograniczeniami. Studenci mają za zadanie sformułować model matematyczny zagadnienia, wybrać odpowiedni algorytm, ocenić uzyskane rozwiązanie i ewentualnie zmodyfikować model w celu uzyskania lepszego dopasowania do rzeczywistości. Zakłada się formułowanie modelu w języku AMPL, albo przy użyciu narzędzi dostępnych w środowisku MATLAB-a, rozwiązanie go w danym środowisku i przeprowadzenie analizy uzyskanych wyników Zarówno wykład jak i zajęcia projektowe będą uwzględniać i odwoływać się do prac badawczych zespołu autorskiego. Dr hab. inż. Andrzej Stachurski był współorganizatorem konferencji naukowych oraz jest recenzentem, m. in. w Mathematical Reviews, European Journal of Operational Research, IEEE Transactions on Biomedical Engineering, Journal of Optimization Theory and Applications, Optimization Methods and Software, w zakresie metod i algorytmów rozwiązywania zadań optymalizacji.
Metody oceny:
(-)
Egzamin:
nie
Literatura:
Pozycje podstawowe: 1. Stachurski A.: Wprowadzenie do optymalizacji. Oficyna Wydawnicza PW, 2009. 2. Stachurski A., A.P. Wierzbicki: Podstawy optymalizacji, Oficyna Wydawnicza PW, 1999. 3. Brdyś J., A. Ruszczyński: Metody optymalizacji w zadaniach, WNT 1985. 4. Findeisen W., J. Szymanowski i A. Wierzbicki: Teoria i metody optymalizacji. PWN 1977. Pozycje uzupełniające: 1. Nocedal J., Wright S.J.:Numerical Optimization. Springer Verlag, Berlin, (first ed. 2000), sec. ed. 2006. 2. Bonans, J.F., Gilbert J.C., Lemarechal C., C.A. Sagastizabal: Numerical Optimization: Theoretical and Practical Aspects. Springer Verlag, Berlin, 2006. 3. Fletcher R.: Practical Methods of Optimization. (sec. edition) John Wiley & Sons, Chichester 1987. 4. Gill P., W. Murray, M. Wright: Practical Optimization. Academic Press 1981. 5. Bazaraa M.S., Sherali H.D., C.M. Shetty: Nonlinear Programming. Theory and Algorithms. (sec. edition) John Wiley & Sons, New York 1993. 6. Bertsekas D.P.: Nonlinear Programming. Athena Scientific, Belmont, Massachusets 1995. 7. Ruszczyński A.: Nonlinear Optimization. Princeton University Press, 2006. Materiały dedykowane: Notatki wykładowe w postaci plików w formacie pdf oraz zestaw pomocniczych ćwiczeń i pytań ułatwiających przygotowania do sprawdzianu.
Witryna www przedmiotu:
https://usosweb.usos.pw.edu.pl/kontroler.php?_action=katalog2/przedmioty/pokazPrzedmiot&prz_kod=103B-ARxxx-DSP-AMO
Uwagi:
(-)

Efekty uczenia się