Politechnika
Warszawska

Katalog
ECTS

Nazwa przedmiotu:

Metody optymalizacji

Koordynator przedmiotu:

Prof. Radosław Pytlak

Status przedmiotu:

Obowiązkowy

Poziom kształcenia:

Studia I stopnia

Program:

Inżynieria i Analiza Danych

Grupa przedmiotów:

Wspólne

Kod przedmiotu:

.

Semestr nominalny:

5 / rok ak. 2017/2018

Liczba punktów ECTS:

5

Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:

1. godziny kontaktowe – 68 h; w tym a) obecność na wykładach – 30 h b) obecność na ćwiczeniach – 15 h c) obecność na laboratoriach – 15 h d) konsultacje – 5 h e) obecność na egzaminie – 3 h 2. praca własna studenta – 60 h; w tym a) przygotowanie do ćwiczeń i do kolokwiów – 15 h b) przygotowanie do laboratoriów – 10 h c) przygotowanie sprawozdań z zadań domowych – 15 h d) zapoznanie się z literaturą – 10 h e) przygotowanie do egzaminu – 10 h Razem 128 h, co odpowiada 5 pkt. ECTS

Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:

1. obecność na wykładach – 30 h 2. obecność na ćwiczeniach – 15 h 3. obecność na laboratoriach – 15 h 4. konsultacje – 5 h 5. obecność na egzaminie – 3 h Razem 68 h, co odpowiada 3 pkt. ECTS

Język prowadzenia zajęć:

polski

Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:

1. obecność na laboratoriach – 15 h 2. przygotowanie do laboratoriów – 10 h 3. przygotowanie sprawozdań z zadań domowych – 15 h Razem 40 h, co odpowiada 2 pkt. ECTS

Formy zajęć i ich wymiar w semestrze:

• Wykład30h
• Ćwiczenia15h
• Laboratorium15h
• Projekt0h
• Lekcje komputerowe0h

Wymagania wstępne:

Analiza matematyczna (rachunek różniczkowy) Algebra liniowa (rachunek macierzowy) Metody numeryczne

Limit liczby studentów:

.

Cel przedmiotu:

Wprowadzenie do podstawowych zastosowań optymalizacji: analiza danych (wyznaczanie wartości estymatorów modeli statystycznych); rozwiązywanie zadań sterowania optymalnego (w szczególności kalibracja modeli dy-namicznych); opracowanie i weryfikacja reguł decyzyjnych; badania opera-cyjne (harmonogramowanie procesów, rozwiązywanie zadań przydziału); wyznaczanie przepływów w sieciach. Przedstawienie warunków koniecznych i dostatecznych optymalności dla zadań optymalizacji: warunki optymalności dla zadań bez ograniczeń; warunki KKT dla zadań z ograniczeniami. Przedstawienie podstawowych metod spadku dla zadań optymalizacji bez ograniczeń: szybkość zbieżności metod; metody gradientów sprzężonych; metoda Newtona; metody quasi-newtonowskie; wprowadzenie do metod obszaru zaufania (trust region methods) Omówienie podstawowych metod dla zadań z ograniczeniami: metody funkcji kary; metody rozszerzonego lagrangianu; metody dokładnej funkcji kary; metody SQP. Omówienie zadania dualnego do zadania wypukłego, metody sympleks oraz metody punktu wewnętrznego dla zadań programowania liniowego oraz kwadratowego. Wprowadzenie do zadań programowania całkowitoliczbowego, zadania zrelaksowane oraz podstawowe metody rozwiązywania zadań optymalizacji całkowitoliczbowej. W ramach laboratorium zrealizowane zostaną: rozwiązywanie zadań estymacji parametrów modeli regresji z wykorzystaniem procedury typu lasso; rozwiązywanie zadań optymalizacji za pośrednictwem środowiska Matlab, serwera NEOS oraz środowiska języka Python; zaznajomienie z podstawowymi językami modelowania zadań optymalizacji.

Treści kształcenia:

1. Przykłady i klasyfikacja zadań optymalizacji. 2. Rozwiązania globalne i lokalne zadań optymalizacji bez ograniczeń. Warunki optymalności (konieczne i dostateczne) dla zadań optymalizacji bez ograniczeń. Zbiory i funkcje wypukłe i ich znaczenie w optymalizacji. 3. Metody spadku (z minimalizacją w kierunku) oraz metody obszaru zaufania (trust region) dla zadań optymalizacji bez ograniczeń. Ogólne warunki zbieżności metod spadku. Szybkość zbieżności metod optymalizacji. 4. Metoda gradientów sprzężonych. Metoda Newtona oraz metody quasi-newtonowskie. 5. Liniowe zadanie najmniejszych kwadratów. Metoda dekompozycji QR oraz równań normalnych rozwiązywania liniowego zadania najmniejszych kwadratów. Metoda Gaussa-Newtona dla zadania najmniejszych kwadratów.. Metoda Newtona dla rozwiązywania układu nieliniowych równań algebraicznych. 6. Warunki optymalności dla zadań optymalizacji z ograniczeniami: warunki konieczne KKT; warunki dostateczne optymalności; warunki regularności ograniczeń. 7. Zadania dualne dla wypukłych zadań optymalizacji z ograniczeniami. 8. Zadanie programowania liniowego. Metoda sympleks. 9. Metody punktu wewnętrznego rozwiązywania zadań programowania liniowego. 10. Wprowadzenie do rozwiązywania zadań optymalizacji z ograniczeniami: metoda funkcji kary; metoda rozszerzonego lagrangianu; metoda dokładnej funkcji kary. 11. Metody SQP; metody eliminacji zmiennych; metody rozwiązywania zadań kwadratowych. 12. Przykłady zadań optymalizacji całkowitoliczbowej. 13. Warunki optymalności dla zadań optymalizacji całkowitoliczbowej; relaksacja zadania programowania liniowego; relaksacja Lagrange’a. Złożoność zadań optymalizacji całkowitoliczbowej. 14. Metoda podziału i ograniczeń (branch and bound) dla zadań optymalizacji całkowitoliczbowej. 15. Metoda płaszczyzn odcinających i metoda generacji kolumn dla zadań optymalizacji całkowitoliczbowej.

Metody oceny:

Ocena przedmiotu składa się z ocen cząstkowych: kolokwia – 30%; aktywność na ćwiczeniach – 10%; sprawozdania z zadań domowych – 20%; egzamin – 40%.

Egzamin:

tak

Literatura:

J. Nocedal, S.J. Wright, Numerical Optimization, Springer, 2006 S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004 L.A. Wolsey. Integer Programming, J. Wiley & Sons, 1998. D.P. Bertsekas, Nonlinear Programming, Athena Scientific, 1999.

Witryna www przedmiotu:

.

Uwagi:

.

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka W01

Ma podstawową wiedzę z zakresu warunków optymalności zadań optymalizacji.
Weryfikacja: egzamin
Powiązane charakterystyki kierunkowe: DS_W06
Powiązane charakterystyki obszarowe: I.P6S_WG

Charakterystyka W02

Ma wiedzę z zakresu metod numerycznych dla nieliniowych zadań optymalizacji.
Weryfikacja: egzamin
Powiązane charakterystyki kierunkowe: DS_W06
Powiązane charakterystyki obszarowe: I.P6S_WG

Charakterystyka W03

Ma podstawową wiedzę z zakresu teorii i metod obliczeniowych optymalizacji całkowitoliczbowej.
Weryfikacja: egzamin
Powiązane charakterystyki kierunkowe: DS_W06
Powiązane charakterystyki obszarowe: I.P6S_WG

Profil ogólnoakademicki - umiejętności

Charakterystyka U01

Potrafi rozwiązywać zadania optymalizacji z wykorzystaniem właściwego pakietu numerycznego optymalizacji.
Weryfikacja: kolokwium oraz sprawozdania z zadań domowych
Powiązane charakterystyki kierunkowe: DS_U09
Powiązane charakterystyki obszarowe: I.P6S_UW

Charakterystyka U02

Potrafi sformułować i rozwiązać złożone zadanie optymalizacji z wykorzystaniem języka modelowania optymalizacji.
Weryfikacja: kolokwium oraz sprawozdania z zadań domowych
Powiązane charakterystyki kierunkowe: DS_U09
Powiązane charakterystyki obszarowe: I.P6S_UW

Profil ogólnoakademicki - kompetencje społeczne

Charakterystyka K01

Rozumie proces postępu w dziedzinie analizy danych i konieczność ciągłego samokształcenia.
Weryfikacja: kolokwium oraz sprawozdania z zadań domowych
Powiązane charakterystyki kierunkowe: DS_K01, DS_K03
Powiązane charakterystyki obszarowe: I.P6S_KK, I.P6S_KO

Charakterystyka K02

Prawidłowo ocenia skutki pozytywne i zagrożenia związane z wdrażaniem rozwiązań dotyczących analizy danych.
Weryfikacja: kolokwium oraz sprawozdania z zadań domowych
Powiązane charakterystyki kierunkowe: DS_K02
Powiązane charakterystyki obszarowe: I.P6S_KO, I.P6S_KR