Μη-Γραμμική Βελτιστοποίηση (ΘΠ14)

Προσεγγιστικοί αλγόριθμοι. Κλάσεις πολυπλοκότητας για προσεγγιστικά προβλήματα. Προβλήματα  με σταθερό προσεγγιστικό λόγο.
Μοντέλα βελτιτοποίησης; γραμμικές εξισώσεις, μη-γραμμικός προγραμματισμός. Εφικτότητα και βελτιστοποίηση, Παράγωγοι και κυρτότητα. Βελτιστοποίηση χωρίς περιορισμούς. Συνθήκες βελιστοποίησης για γραμμικούς και μη-γραμμικούς περιορισμούς. Πολλαπλασιαστές Lagrange, Μέθοδοι εφικτού σημείου. Μέθοδοι penalty και barrier. Semi-definite προγραμματισμός.  Μοντελοποίηση προβλημάτων σαν πρόβλημα Semi-definite προγραμματισμού.

1) Linear and Nonlinear programming, S. Nash, A. Sofer
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