Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Algorytmy i metody optymalizacji
Koordynator przedmiotu:
Andrzej stachurski
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia II stopnia
Program:
Automatyka i Robotyka
Grupa przedmiotów:
Przedmioty techniczne - zaawansowane
Kod przedmiotu:
AMO
Semestr nominalny:
2 / rok ak. 2013/2014
Liczba punktów ECTS:
5
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Udział w wykładach: 15 x 2 godz. = 30 godz. Wykonywanie projektu: 15 x 2 godz. = 30 godz. Praca własna: 55 godz. Udział w konsultacjach: 5 godz. Łączny nakład pracy studenta: 120 godz., co odpowiada 5 ECTS
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
2
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
2
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia0h
  • Laboratorium0h
  • Projekt30h
  • Lekcje komputerowe0h
Wymagania wstępne:
Limit liczby studentów:
40
Cel przedmiotu:
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ści kształcenia:
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)
Metody oceny:
Projekt, kolokwia.
Egzamin:
nie
Literatura:
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.
Witryna www przedmiotu:
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Efekt AMO_W01
Znajomość metody sprowadzania zadania programowania liniowego do postaci standardowej oraz metody sympleks do rozwiązywania zadania w postaci standardowej.
Weryfikacja: kolokwium
Powiązane efekty kierunkowe: K_W01
Powiązane efekty obszarowe: T2A_W01, T2A_W02, T2A_W07
Efekt AMO_W02
Znajomość teorii dualności Lagrange’a dla zadań programowania liniowego oraz ogólnych zadań optymalizacji nieliniowej z ograniczeniami
Weryfikacja: kolokwium
Powiązane efekty kierunkowe: K_W01, K_W04
Powiązane efekty obszarowe: T2A_W01, T2A_W02, T2A_W07, T2A_W01, T2A_W03, T2A_W04
Efekt AMO_W03
Znajomość warunków koniecznych i dostatecznych optymalności dla różniczkowalnych zadań optymalizacji nieliniowej bez ograniczeń
Weryfikacja: kolokwium
Powiązane efekty kierunkowe: K_W01, K_W04
Powiązane efekty obszarowe: T2A_W01, T2A_W02, T2A_W07, T2A_W01, T2A_W03, T2A_W04
Efekt AMO_W04
Znajomość podstawowych metod gradientowych i bezgradientowych poszukiwania minimum bez ograniczeń
Weryfikacja: kolokwium
Powiązane efekty kierunkowe: K_W01, K_W04
Powiązane efekty obszarowe: T2A_W01, T2A_W02, T2A_W07, T2A_W01, T2A_W03, T2A_W04
Efekt AMO_W05
Znajomość warunków koniecznych i dostatecznych optymalności dla różniczkowalnych zadań optymalizacji nieliniowej z ograniczeniami
Weryfikacja: kolokwium
Powiązane efekty kierunkowe: K_W01, K_W04
Powiązane efekty obszarowe: T2A_W01, T2A_W02, T2A_W07, T2A_W01, T2A_W03, T2A_W04
Efekt AMO_W06
Znajomość metod ograniczeń aktywnych oraz funkcji kary do rozwiązywania zadań optymalizacji nieliniowej z ograniczeniami
Weryfikacja: kolokwium
Powiązane efekty kierunkowe: K_W01, K_W04
Powiązane efekty obszarowe: T2A_W01, T2A_W02, T2A_W07, T2A_W01, T2A_W03, T2A_W04

Profil ogólnoakademicki - umiejętności

Efekt AMO_U01
Umiejętność sprowadzenia zadania programowania liniowego do postaci standardowej i jego rozwiązania za pomocą metody sympleks.
Weryfikacja: projekt, kolokwium
Powiązane efekty kierunkowe: K_U03, K_U17
Powiązane efekty obszarowe: T2A_U03, T2A_U18
Efekt AMO_U02
Umiejętność znajdowania minimum/maksimum funkcji nieliniowej metodami gradientowymi albo bezgradientowymi
Weryfikacja: projekt
Powiązane efekty kierunkowe: K_U03, K_U17
Powiązane efekty obszarowe: T2A_U03, T2A_U18
Efekt AMO_U03
Umiejętność sprawdzenia, czy dany punkt jest rozwiązaniem różniczkowalnego zadania optymalizacji bez ograniczeń
Weryfikacja: projekt, kolokwium
Powiązane efekty kierunkowe: K_U03, K_U17
Powiązane efekty obszarowe: T2A_U03, T2A_U18
Efekt AMO_U04
Umiejętność sformułowania dualnego zadania Lagrange’a do danego zadania programowania liniowego albo kwadratowego
Weryfikacja: projekt, kolokwium
Powiązane efekty kierunkowe: K_U03, K_U17
Powiązane efekty obszarowe: T2A_U03, T2A_U18
Efekt AMO_U05
Umiejętność znajdowania rozwiązania zadania z ograniczeniami za pomocą metod ograniczeń aktywnych oraz metod funkcji kary
Weryfikacja: projekt
Powiązane efekty kierunkowe: K_U03, K_U17
Powiązane efekty obszarowe: T2A_U03, T2A_U18
Efekt AMO_U06
Umiejętność sprawdzenia, czy dany punkt jest rozwiązaniem regularnego, różniczkowalnego zadania optymalizacji z ograniczeniami
Weryfikacja: projekt, kolokwium
Powiązane efekty kierunkowe: K_U03, K_U17
Powiązane efekty obszarowe: T2A_U03, T2A_U18
Efekt AMO_U07
Umiejętność formułowania modelu optymalizacyjnego (liniowego albo nieliniowego), opisującego pewne typowe problemy praktyczne, zapis modelu matematycznego w języku pakietu AMPL albo w języku pakietu MATLAB
Weryfikacja: projekt
Powiązane efekty kierunkowe: K_U03, K_U17
Powiązane efekty obszarowe: T2A_U03, T2A_U18
Efekt AMO_U08
Umiejętność znajdowania rozwiązania zadania optymalizacji za pomocą narzędzi ze skrzynki narzędziowej MATLAB-a, albo odpowiedniego, dołączonego do AMPL solwera (MINOS lub CPLEX) .
Weryfikacja: projekt
Powiązane efekty kierunkowe: K_U03, K_U17
Powiązane efekty obszarowe: T2A_U03, T2A_U18