Κυρτή βελτιστοποίηση — έννοιες, μέθοδοι και εφαρμογές

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

Αυτή η εγγύηση κάνει αυτά τα προβλήματα πολύ πιο αξιόπιστα από τα γενικά προβλήματα βελτιστοποίησης. Πρέπει βέβαια να μοντελοποιήσεις σωστά το πρόβλημα, αλλά μόλις το μοντέλο είναι κυρτό, δεν κυνηγάς μια λύση που φαίνεται καλύτερη μόνο σε μια μικρή γειτονιά.

Μια συνηθισμένη μορφή είναι

$$\text{minimize } f(x)$$

με περιορισμούς

$$g_i(x) \le 0 \quad \text{for } i=1,\dots,m, \qquad Ax=b,$$

όπου η $f$ και κάθε $g_i$ είναι κυρτές, και οι περιορισμοί ισότητας είναι αφινικοί. Κάτω από αυτές τις συνθήκες, το εφικτό σύνολο είναι κυρτό και το πρόβλημα βελτιστοποίησης είναι κυρτό.

Ορισμός της κυρτής βελτιστοποίησης

Μια συνάρτηση $f$ είναι κυρτή αν, για οποιαδήποτε δύο σημεία $x$ και $y$ στο πεδίο ορισμού της και για κάθε $0 \le t \le 1$,

$$f(tx + (1-t)y) \le t f(x) + (1-t) f(y).$$

Με απλά λόγια, το ευθύγραμμο τμήμα ανάμεσα σε δύο σημεία του γραφήματος βρίσκεται πάνω από το γράφημα. Σε μία μεταβλητή, πολλές κυρτές συναρτήσεις μοιάζουν με μπολ, αλλά το πραγματικό κριτήριο είναι η ανισότητα.

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

Χρειάζεσαι και τα δύο στοιχεία:

• μια κυρτή αντικειμενική συνάρτηση
• ένα κυρτό εφικτό σύνολο

Αν αποτύχει κάποιο από τα δύο, το πρόβλημα μπορεί να πάψει να είναι κυρτό.

Γιατί η κυρτή βελτιστοποίηση αναλύεται ευκολότερα

Η βελτιστοποίηση είναι συχνά δύσκολη επειδή μπορεί να υπάρχουν πολλές κοιλάδες. Ένας αλγόριθμος μπορεί να συνεχίζει να βελτιώνει την αντικειμενική συνάρτηση και παρ’ όλα αυτά να σταματήσει σε ένα σημείο που είναι μόνο τοπικά βέλτιστο.

Η κυρτή βελτιστοποίηση αφαιρεί αυτόν τον συγκεκριμένο τρόπο αποτυχίας. Αν η αντικειμενική συνάρτηση είναι κυρτή και η εφικτή περιοχή είναι κυρτή, τότε ένα σημείο που δεν μπορεί να βελτιωθεί τοπικά είναι ήδη ολικά βέλτιστο. Γι’ αυτό τα κυρτά προβλήματα έχουν σημασία στη στατιστική, στη μηχανική μάθηση, στον έλεγχο και στην επιχειρησιακή έρευνα.

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

Λυμένο παράδειγμα κυρτής βελτιστοποίησης

Θεώρησε το πρόβλημα χωρίς περιορισμούς

$$\text{minimize } f(x) = (x-3)^2 + 2.$$

Αυτό είναι πρόβλημα κυρτής βελτιστοποίησης επειδή η $f(x)$ είναι τετραγωνική συνάρτηση με θετικό συντελεστή του όρου δευτέρου βαθμού, άρα είναι κυρτή σε όλους τους πραγματικούς αριθμούς.

Για να βρούμε το ελαχιστοποιητή, παραγωγίζουμε:

$$f'(x) = 2(x-3).$$

Θέτουμε την παράγωγο ίση με το μηδέν:

$$2(x-3)=0 \quad \Rightarrow \quad x=3.$$

Τώρα υπολογίζουμε την αντικειμενική συνάρτηση:

$$f(3) = (3-3)^2 + 2 = 2.$$

Άρα η ελάχιστη τιμή είναι $2$, και επιτυγχάνεται στο $x=3$.

Αυτό το παράδειγμα είναι απλό, αλλά δείχνει τη βασική ιδέα. Μόλις φτάσεις στο $x=3$, δεν υπάρχει κάποια κρυφή χαμηλότερη κοιλάδα αλλού.

Συνήθεις μέθοδοι για κυρτή βελτιστοποίηση

Η μέθοδος εξαρτάται από τη δομή του προβλήματος.

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

Για πολλά κυρτά προβλήματα με περιορισμούς, χρησιμοποιούνται ευρέως οι μέθοδοι εσωτερικού σημείου, επειδή χειρίζονται άμεσα τους περιορισμούς και συχνά αποδίδουν καλά στην πράξη.

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

Συνηθισμένα λάθη στην κυρτή βελτιστοποίηση

Να υποθέτεις ότι ένα γράφημα αποδεικνύει την κυρτότητα

Ένα γράφημα μπορεί να φαίνεται σαν μπολ σε μία απεικόνιση και παρ’ όλα αυτά να μην είναι κυρτό σε όλο το πεδίο ορισμού ή σε υψηλότερες διαστάσεις. Ο ορισμός ή οι τυπικοί κανόνες κυρτότητας έχουν μεγαλύτερη σημασία από ένα πρόχειρο σχήμα.

Να ξεχνάς ότι οι περιορισμοί έχουν σημασία

Μια κυρτή αντικειμενική συνάρτηση από μόνη της δεν αρκεί. Αν το εφικτό σύνολο δεν είναι κυρτό, τότε το συνολικό πρόβλημα δεν είναι πρόβλημα κυρτής βελτιστοποίησης.

Να θεωρείς κάθε κρίσιμο σημείο ως ελάχιστο

Για μια παραγωγίσιμη κυρτή συνάρτηση, ένα σημείο με μηδενική κλίση είναι ολικός ελαχιστοποιητής. Χωρίς κυρτότητα, αυτό το συμπέρασμα γενικά δεν ισχύει.

Να συγχέεις την κυρτότητα με την αυστηρή κυρτότητα

Η αυστηρή κυρτότητα είναι ισχυρότερη ιδιότητα. Συχνά δίνει μοναδικό ελαχιστοποιητή, ενώ η απλή κυρτότητα δεν εγγυάται πάντα μοναδικότητα.

Πού χρησιμοποιείται η κυρτή βελτιστοποίηση

Η κυρτή βελτιστοποίηση εμφανίζεται κάθε φορά που ένα πραγματικό πρόβλημα μπορεί να μοντελοποιηθεί με κυρτά κόστη και κυρτούς περιορισμούς.

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

Πότε η κυρτότητα βοηθά στην πράξη

Η κυρτή βελτιστοποίηση είναι ιδιαίτερα χρήσιμη όταν χρειάζεσαι κάτι περισσότερο από έναν απλό αριθμό. Συχνά θέλεις μια εγγύηση ότι η απάντηση είναι πράγματι βέλτιστη για το μοντέλο που έγραψες.

Αυτή η εγγύηση έχει σημασία στη μηχανική και στην ανάλυση δεδομένων, επειδή διαχωρίζει δύο ερωτήματα:

1. Λύσαμε σωστά το μαθηματικό πρόβλημα;
2. Ήταν το μαθηματικό πρόβλημα καλό μοντέλο της πραγματικότητας;

Η κυρτότητα βοηθά πολύ στο πρώτο ερώτημα. Δεν λύνει αυτόματα το δεύτερο.

Δοκίμασε ένα παρόμοιο πρόβλημα

Πάρε τη $f(x) = (x+1)^2 + 5$ και βρες το ελάχιστό της. Έπειτα σύγκρινέ τη με τη $f(x) = -(x+1)^2 + 5$, η οποία είναι κοίλη και όχι κυρτή. Αυτός ο έλεγχος δίπλα-δίπλα κάνει τον ρόλο της κυρτότητας πολύ πιο εύκολο να φανεί.

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