| Abstract : | In the following thesis, we discuss algorithms for convex optimization. Is optimization for convex function on convex sets. These algorithms are based on notion of functional and convex analysis. We use functional analysis to construct sequence which are convergent in Hilbert space and \mathbb{R}^n. The basic idea is that the iterative sequence we construct converges to the minimum of objective function. We generalize the notion of gradient and differentiable functions for non-smooth, so we can minimize them. The first method we see is the gradient method, which is about convex and differentiable functions. Next algorithm, proximal point is about non-smooth functions and then we combine gradient and proximal and we have an algorithm for functions, which is the sum of smooth and non-smooth. Finally, we study the primal dual algorithm. An example of these methods is provided to Lasso function.
Στην παρούσα εργασία, θα παρουσιάσουμε αλγορίθμους για την ελαχιστοποίηση κυρτών συναρτήσεων πάνω σε κυρτά σύνολα. Αυτοί οι αλγόριθμοι βασίζονται σε έννοιες της συναρτησιακής και κυρτής ανάλυσης. Χρησιμοποιούμε βασικές έννοιες και θεωρήματα της ανάλυσης για πετύχουμε την σύγκλιση των ακολουθιών που κατασκευάστηκαν. Η βασική ιδέα είναι να φτιάξουμε επαναληπτικές διαδικασίες που συγκλίνουν στο ελάχιστο της αντικειμενικής συνάρτησης. Ο χώρος που θα δουλέψουμε περισσότερο είναι ο Hilbert με κάποια παραδείγματα και αναφορές στον \mathbb{R}^n. Θα γενικεύσουμε την έννοια της παραγώγου με σκοπό να μπορούμε να διαχειριστούμε συναρτήσεις κυρτές αλλά όχι διαφορίσιμες. Η πρώτη μέθοδος είναι η gradient method, αφορά παραγωγίσιμες συναρτήσεις. Μετά θα αναφερθούμε στον proximal point που αφορά μη παραγωγίσιμες συναρτήσεις. Οι δύο παραπάνω μέθοδοι συνδυάζονται και μας δίνουν τον proximal gradient method, με τον οποίο μπορούμε να ελαχιστοποιήσουμε συναρτήσεις που εμπλέκονται όροι διαφρορίσιμων συναρτήσεων και μη. Μετά θα αναφερθούμε στον primal-dual αλγόριθμο. Τέλος θα παρουσιάσουμε ένα παράδειγμα των παραπάνω αλγορίθμων στο πρόβλημα ελαχιστοποίησης Lasso.
|
|---|
Copyright © 2013 Library AUEB. All rights reserved.