Μάθημα : Μη Γραμμική Βελτιστοποίηση
Κωδικός : DI280
Τρόποι αξιολόγησης / εξέτασης
Στα πλαίσια του μαθήματος θα σας ανατεθεί προαιρετικά η παρουσίαση ενός άρθρου με αντικείμενο σχετικό με το μάθημα, με βαθμολογία 4 μονάδες στις 10.
Ο Τελικός Βαθμός (ΤΒ) θα είναι:
ΤΒ = ΒΓ, αν ΒΓ < 4, ή
ΤΒ = ΒΓ+ΒΠ, αν ΒΓ >= 4.
Οπου ΒΓ, Βαθμός Γραπτού και ΒΠ, Βαθμός Παρουσίασης.
Βοηθήματα
2) Convex Optimization, Stphen Boyd, Lieven Vandeberghe
3) Linear complementarity, Linear and Nonlinear programming, Katta G. Murty
4) Introduction to Algorithms, CRLS
5) Approximation Algorithms, Vazirani
Περιεχόμενο Μαθήματος
1) Προσεγγιστικοί αλγόριθμοι. Κλάσεις πολυπλοκότητας για προσεγγιστικά προβλήματα.
Προβλήματα με σταθερό προσεγγιστικό λόγο.
2) Μοντέλα βελτιστοποίησης. Εφικτότητα και βελτιστοποίηση. Μη-γραμμικός προγραμματισμός. Παράγωγοι και κυρτότητα. Ο γενικός αλγόριθμος βελτιστοποίησης.Ταχύτητα σύγκλισης. Η μέθοδος Newton.
3) Βασικές έννοιες για βελτιστοποίηση χωρίς περιορισμούς.Μέθοδοι ελτιστοποίησης χωρις περιορισμούς: Quasi-Newton, Stepest Descent.
4) Βελτιστοποίηση με περιορισμούς. Συνθήκες βελτιστοποίησης για γραμμικούς και μη-γραμμικούς περιορισμούς. Πολλαπλασιστές Lagrange, ΚΚΚ-συνθήκες. Μέθοδοι penalty και Barrier.
5) Ημιθετικός προγραμματισμός, Η primal-dual μέθοδο.