Politechnika Warszawska - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Algorytmy i metody optymalizacji

Informacje ogólne

Kod przedmiotu: 103B-ARxxx-DSP-AMO Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Algorytmy i metody optymalizacji
Jednostka: Wydział Elektroniki i Technik Informacyjnych
Grupy: ( Przedmioty techniczne )---EITI
( Przedmioty zaawansowane )-Automatyka i robotyka-dr.-EITI
( Przedmioty zaawansowane )-Automatyka i robotyka-mgr.-EITI
( Przedmioty zaawansowane obieralne )-Systemy informacyjno-decyzyjne-mgr.-EITI
( Przedmioty zaawansowane techniczne )--mgr.-EITI
Punkty ECTS i inne: 5.00
Język prowadzenia: polski
Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

AMO

Numer wersji:

2

Skrócony opis:

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 (...)

Pełny opis:

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)



  2. OPTYMALIZACJA NIELINIOWA BEZ OGRANICZEŃ
  3. 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)

  4. 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)

  5. Metody obszaru zaufania, metody jednostajnych kierunków poprawy, testy stopu w minimalizacji kierunkowej - testy Goldsteina i reguła Armijo, gradientowe metody minimalizacji kierunkowej. (2h)

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



  7. PROGRAMOWANIE LINIOWE
  8. Zastosowania programowania liniowego. Postać standardowa zadania programowania liniowego, zadania sprzeczne, nieograniczone, warunki optymalności, metoda sympleks w wersji tablicowej. (2h)

  9. Dwufazowa metoda sympleks, znajdowanie początkowego bazowego rozwiązania dopuszczalnego, jednofazowa metoda sympleks (metoda wielkiego "M"). (2h)



  10. OPTYMALIZACJA NIELINIOWA Z OGRANICZENIAMI
  11. 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)

  12. 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)



  13. PROGRAMOWANIE KWADRATOWE
  14. Zastosowania programowania kwadratowego. Metoda uogólnionej eliminacji do rozwiązywania zadań programowania kwadratowego z ograniczeniami równościowymi. (2h)

  15. Metoda ograniczeń aktywnych do rozwiązywania zadań programowania kwadratowego z ograniczeniami nierównościowymi. (2h)



  16. METODY ROZWIĄZYWANIA ZADAŃ Z OGRANICZENIAMI
  17. Metody sekwencyjnego programowania kwadratowego. (2h)

  18. Metody zewnętrznej i wewnętrznej (barierowej) funkcji kary. (2h)

  19. Metody rozszerzonej funkcji Lagrange`a. (2h)

  20. Niesympleksowe metody wielomianowe, metoda Karmarkara oraz metody oparte na barierowej logarytmicznej funkcji kary do rozwiązywania zadań programowania liniowego. (2h)


  21. Zakres projektu
    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.


Poprzedniki
Typ poprzednikaNr poprzednikaKod poprzednikaNazwa poprzednika
Zalecany1103B-INxxx-ISP-MNUMMetody numeryczne
Zalecany1103B-ARxxx-ISP-POBOPodstawy badań operacyjnych
Zalecany1103A-INSID-ISP-MNUMMetody numeryczne

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 egzaminu.

Zajęcia w cyklu "rok akademicki 2019/2020 - sem. zimowy" (w trakcie)

Okres: 2019-10-01 - 2020-02-21
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 45 miejsc więcej informacji
Wykład, 30 godzin, 45 miejsc więcej informacji
Koordynatorzy: Andrzej Stachurski
Prowadzący grup: Andrzej Stachurski
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2018/2019 - sem. zimowy" (zakończony)

Okres: 2018-10-01 - 2019-02-17
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 45 miejsc więcej informacji
Wykład, 30 godzin, 45 miejsc więcej informacji
Koordynatorzy: Andrzej Stachurski
Prowadzący grup: Andrzej Stachurski
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.