Odabrane optimizacijske metode i algoritmi

Prikazani su podaci za akademsku godinu: 2024./2025.

Nositelji

Prof. dr. sc.
Nikica Hlupić

Opis predmeta

Optimizacija je proces kojim se nešto dovodi u najbolje moguće stanje s obzirom na zahtjeve i ograničenja (uvjete). U suvremenom društvu i gospodarstvu uloga optimizacije je sve izraženija, stoga se u ovom predmetu studentima pruža pregled najvažnijih dostignuća tog područja znanosti, s naglaskom na primjenjiva znanja. U nastavku je načelni popis tema. Teorijska podloga optimizacije: diferencijali, usmjerena derivacija, Taylorov red, ekstremi, konveksnost i konkavnost funkcija, O-notacija u optimizaciji. Uvod u teoriju optimizacije. Optimizacija bez ograničenja: jednodimenzijska optimizacija, gradijentna metoda, izračun koraka, kriteriji zaustavljanja, Newtonova metoda, metoda konjugiranih gradijenata, kvazi-Newtonova metoda, metode područja povjerenja, Nelder-Mead simpleks algoritam. Optimizacija pod ograničenjima: Karush-Kuhn-Tuckerovi uvjeti optimalnosti, Lagrangeova dualnost, projekcije, Lagrangeovi algoritmi, penalne metode, proširena Lagrangeova metoda. Odabrane heurističke metode (simulirano žarenje, roj čestica, skupina mrava, genetski algoritmi). Višeciljna optimizacija.

Preduvjeti

(srednja razina): matematička analiza po više varijabli, linearna algebra, vladanje programiranjem (i/ili poznavanje Matlaba ili sličnog alata)

Studijski programi

Sveučilišni diplomski
[FER3-HR] Audiotehnologije i elektroakustika - profil
Izborni predmeti (2. semestar)
[FER3-HR] Automatika i robotika - profil
Izborni predmeti (2. semestar)
[FER3-HR] Elektroenergetika - profil
Izborni predmeti (2. semestar)
[FER3-HR] Elektroničko i računalno inženjerstvo - profil
Izborni predmeti (2. semestar)
[FER3-HR] Elektronika - profil
Izborni predmeti (2. semestar)
[FER3-HR] Elektrostrojarstvo i automatizacija - profil
Izborni predmeti (2. semestar)
[FER3-HR] Informacijsko i komunikacijsko inženjerstvo - profil
Izborni predmeti (2. semestar)
[FER3-HR] Komunikacijske i svemirske tehnologije - profil
Izborni predmeti (2. semestar)
[FER3-HR] Programsko inženjerstvo i informacijski sustavi - profil
Izborni predmeti (2. semestar)
Izborni predmet profila (2. semestar)
[FER3-HR] Računalno inženjerstvo - profil
Izborni predmeti (2. semestar)
[FER3-HR] Računalno modeliranje u inženjerstvu - profil
Izborni predmeti (2. semestar)
[FER3-HR] Računarska znanost - profil
Izborni predmeti (2. semestar)
[FER3-HR] Znanost o mrežama - profil
Izborni predmeti (2. semestar)
[FER3-HR] Znanost o podacima - profil
Izborni predmeti (2. semestar)

Ishodi učenja

  1. prepoznati i analizirati problem kao optimizacijski
  2. povezati postavljeni problem s istovrsnim ili sličnim već riješenim problemima
  3. odabrati najbolju metodu rješavanja za već riješeni (poznati) problem
  4. prilagoditi metode i algoritme za slične probleme tako da budu primjenjivi na zadani
  5. osmisliti vlastito rješenje za nepoznati problem
  6. ocijeniti valjanost vlastitog rješenja, u smislu procjene konvergencije i složenosti algoritma
  7. usporediti svoju metodu s možebitnim drugim idejama
  8. preporučiti algoritam za nepoznati problem na temelju usporedbe predloženih rješenja

Oblici nastave

Predavanja

Izlaganje predavača i dodatna pojašnjenja prema pitanjima studenata.

Samostalni zadaci

Svaki student će za polaganje predmeta teorijski i programski riješiti neki optimizacijski problem po vlastitom izboru.

Mentorski rad

Pomoć studentu pri rješavanju odabranog optimizacijskog problema.

Način ocjenjivanja

Kontinuirana nastava Ispitni rok
Vrsta provjere Prag Udio u ocjeni Prag Udio u ocjeni
Seminar/Projekt 0 % 70 % 0 % 0 %
Završni ispit: Usmeni 30 %
Ispit: Pismeni 0 % 70 %
Ispit: Usmeni 30 %

Tjedni plan nastave

  1. Konstantna. logaritamska. linearna. kvadratna i eksponencijalna klasa složenosti
  2. Tangenta i normala na graf funkcije. Rast i pad funkcija
  3. Usmjerene derivacije. Derivacija implicitnih funkcija. Teorem o implicitnoj funkciji, Ekstremi. Lokalni ekstremi
  4. Drugi diferencijal i kvadratne forme, Taylorova formula
  5. Konveksnost i konkavnost funkcije. Nalaženje ekstrema funkcije. nužni i dovoljni uvjeti, Optimizacija u jednoj dimenziji (metoda zlatnog reza. sukcesivna parabolička interpolacija. Newtonova metoda)
  6. Algoritmi direktnog traženja (Hooke-Jeeves metoda). Gradijentne metode (metoda najbržeg silaska), Newtonova metoda. Metoda sekante, Kriteriji zaustavljanja
  7. Metode konjugiranih gradijenata, Kvazi-Newtonove metode
  8. Međuispit
  9. Metode područja povjerenja
  10. Vezani ekstremi. Lagrangeovi multiplikatori, Proširena Lagrangeova metoda
  11. Konveksni optimizacijski problemi
  12. Dualnost. Lagrangeova funkcija. Perturbacije i analiza osjetljivosti
  13. Deterministički i heuristički pristupi
  14. Meta-heuristika: simulirano žarenje, tabu pretraga, evolucijske strategije, algoritam skupine mrava, algoritam roja čestica, algoritam roja pčela, postupci pohlepnog nasumičnog prilagodljivog pretraživanja (GRASP)
  15. Završni ispit

Literatura

Edwin K. P. Chong, Wu-Sheng Lu, and Stanislaw H. Żak (2023.), An Introduction to Optimization, 5th Edition, With Applications to Machine Learning, Wiley
Jorge Nocedal, Stephen J. Wright (2006.), Numerical Optimization, 2nd Edition, Springer
Omid Bozorg-Haddad, Mohammad Solgi, Hugo A. Loáiciga (2017.), Meta-heuristic and Evolutionary Algorithms for Engineering Optimization, Wiley
Carl D. Meyer (2000.), Matrix Analysis and Applied Linear Algebra, SIAM
G.A.F. Seber, A.J. Lee (2003.), Linear Regression Analysis, 2nd edition, Wiley
G.A.F. Seber and C. J. Wild (2005.), Nonlinear Regression, Wiley

Izvedba

ID 222557
  Ljetni semestar
5 ECTS
R1 Engleski jezik
R1 E-učenje
45 Predavanja
0 Seminar
0 Auditorne vježbe
15 Laboratorijske vježbe
0 Konstrukcijske vježbe
0 Vježbe tjelesnog odgoja

Ocjenjivanje

90 izvrstan
75 vrlo dobar
60 dobar
50 dovoljan

Sličan predmet