Κυρτή Βελτιστοποίηση

    Μάθημα Επιλογής Κορμού, Εαρινό Εξάμηνο,  6 μονάδες ECTS

    Διδάσκων: Αναπληρωτής Καθηγητής Σταύρος Τουμπής

    URL: https://eclass.aueb.gr/courses/INF413/

    Περιεχόμενο

    A) Θεμελιώσεις: Κυρτά σύνολα, συναρτήσεις και προβλήματα, δυισμός. B) Εφαρμογές: προβλήματα προσεγγίσεων, εκτιμητικής, υπολογισμού ελάχιστου κόστους σε γράφους, προβλήματα γεωμετρίας, και συναφή προβλήματα. Γ) Αλγόριθμοι: Ελαχιστοποίηση χωρίς και με περιορισμούς και μέθοδοι εσωτερικού σημείου.

    Μαθησιακά Αποτελέσματα

    Μετά την επιτυχή ολοκλήρωση του μαθήματος, ο φοιτητής θα είναι σε θέση:

    • Να μοντελοποιεί πραγματικά προβλήματα που ανακύπτουν στη Επιστήμη των Υπολογιστών και συναφείς επιστήμες ως προβλήματα μαθηματικού προγραμματισμού
    • Να εντοπίζει τις βασικές ιδιότητες  και χαρακτηριστικά ενός δοσμένου προβλήματος μαθηματικού προγραμματισμού, ιδιαιτέρως κατά πόσο το πρόβλημα είναι ή μπορεί να μετατραπεί σε πρόβλημα κυρτής βελτιστοποίησης
    • Να χρησιμοποιεί και να κατασκευάζει αλγόριθμους που επιλύουν προβλήματα κυρτής βελτιστοποίησης, λαμβάνοντας υπόψη τις ιδιαιτερότητες του κάθε δοσμένου προβλήματος.

    Προαπαιτούμενα Μαθήματα

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

    Συνιστώμενη Βιβλιογραφία

    • Convex Optimization, Stephen Boyd and Lieven Vandenberghe, Cambridge University Press, 1st edition, 2004,ISBN-13: 978-0521833783
    • Convex Optimization Algorithms, Dimitri P. Bertsekas, Athens Scientific, 1st edition, 2015, ISBN-13: 978-1886529281.
    • Convex Analysis and Optimization, Dimitri Bertsekas, Angelica Nedic, and Asuman Ozdaglar, Athena Scientific, 1st edition, 2003, ISBN-13: 978-1886529458.

    Διδακτικές και Μαθησιακές Μέθοδοι

    Μια διάλεξη 3 ωρών εβδομαδιαίως, υπολογιστικές και προγραμματιστικές ασκήσεις κατ’ οίκον.

    Μέθοδοι Αξιολόγησης/Βαθμολόγησης

    Ο τελικός βαθμός διαμορφώνεται κατά 70% από την τελική εξέταση και κατά 30% από τις υπολογιστικές και προγραμματιστικές ασκήσεις. Πρέπει, όμως, ο βαθμός της τελικής εξέτασης να είναι προβιβάσιμος, προκειμένου να είναι προβιβάσιμος και ο τελικός βαθμός.