Odabrane optimizacijske metode i algoritmi

Opis predmeta

Klase složenosti algoritma; O-notacija. Analitičke osnove optimizacije (diferencijali, usmjerena derivacija, Taylorova formula, smjer porasta funkcije, ekstremi), konveksnost i konkavnost funkcija. Optimizacija bez ograničenja: jednodimenzionalna optimizacija, gradijentna metoda, kriteriji zaustavljanja, Newtonova metoda, kvazi-Newtonova metoda, metoda konjugiranih gradijenata, Nelder-Mead simpleks algoritam, metode područja povjerenja. Optimizacija s ograničenjima: Karush-Kuhn-Tucker uvjet, Lagrangeovi množitelji, proširena Lagrangeova metoda. Odabrane heurističke metode (simulirano žarenje, roj čestica, skupina mrava, genetski algoritmi). Višekriterijska optimizacija.

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 % 80 % 0 % 0 %
Završni ispit: Usmeni 20 %
Ispit: Pismeni 0 % 80 %
Ispit: Usmeni 20 %

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

Studijski programi

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

Literatura

E.K.P. Chong, S.H. Żak (2013.), An Introduction to Optimization, 4th Edition, 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

Za studente

Izvedba

ID 222557
  Ljetni semestar
5 ECTS
R1 Engleski jezik
R1 E-učenje
45 Predavanja
15 Laboratorijske vježbe

Ocjenjivanje

90 izvrstan
75 vrlo dobar
60 dobar
50 dovoljan