Παρουσίαση/Προβολή

(DI346) -  Γρηγόρης Καραγιώργος

Περιγραφή Μαθήματος

1)Μοντέλα βελτιστοποίησης.

2) Θεμελιώδεις αρχές βελτιστοποίησης

Εφικτότητα και βελτιστοποίηση, Κυρτά σύνολα και κυρτές συναρτήσεις, ταχύτητα σύγκλισης, η μέθοδος Newton για μη γραμμικές εξισώσεις.

3) Αναπαράσταση γραμμικών περιορισμών

4) Γραμμικός προγραμματισμός (ΓΠ)

Εισαγωγή, Γεωμετρία ΓΠ, θεωρία δυικότητας, προβλήματα δικτύων, υπολογιστική πολυπλοκότητα ΓΠ. Η μέθοδος Simplex,

Η ελλειψοειδής μέθδος.

5) Βελτιστοποίηση χωρίς περιορισμούς

Συνθήκες, μέθοδοι.

6) Μη γραμμικός προγραμαμτισμός (ΜΓΠ)

Συνθήκες βελτιστότητας για προβλήματα με περιορισμούς,

Συνθήκες βελτιστότητας για γραμμικούς ισωτικού περιορισμούς

Πολλαπλασιαστές Lagrange και η συνάρτηση Lagrange

Συνθήκες βελτιστότητας  για γραμμικούς ανισωτικούς περιορισμούς

Δυικότητα και παίγνια. Minimax και δυικότητα.

7) Μέθοδοι εσωτερικού σημείου.

8) Μέθοδοι Penalty Barrier

9) Μέθοδοι εσωτερικού σημείου για ΓΠ και κυρτό προγραμματισμού.

10) Path following μέθοδοι

11) Συναρτήσεις Self-Concordant

12) Semi-definite Programming (SDP)

Το πρόβλημα Max-cut, Unique Game Conecture, Small Set Expansion Hypothesis.

 

Ημερομηνία δημιουργίας

Τρίτη 6 Μαΐου 2014