next up previous contents
Next: Μέθοδοι Up: ΠΟΛΥΔΙΑΣΤΑΤΗ ΦΥΣΙΚΗ ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ Previous: Η Μέθοδος της Μέγιστης   Contents

Η Μέθοδος 14#14

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

1297#1297

όπου ο 1208#1208 είναι ο Εσσιανός πίνακας των δευτέρων παραγώγων της 51#51,

1298#1298

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

1299#1299

για την τιμή του 1300#1300, και στη συνέχεια επαναλαμβάνουμε το

1301#1301

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


27#27

Παράδειγμα 6.5   Η ΜΕΘΟΔΟΣ 1274#1274. Παρουσιάζουμε τη μέθοδο 14#14 και πάλι ελαχιστοποιώντας τη συνάρτηση του παραδείγματος 6.5,

1302#1302

, της οποίας η κλίση και ο Εσσιανός πίνακας δίνονται από τις

1303#1303

Αν πάρουμε το 1291#1291 ως αρχικό σημείο, η κλίση 1292#1292. Οπότε το γραμμικό σύστημα που πρέπει να λυθεί για το βήμα της μεθόδου 14#14 είναι


1304#1304

και άρα η επόμενη προσεγγιστική λύση είναι

1305#1305

η οποία είναι η ακριβής λύση για αυτό το πρόβλημα. Το γεγονός ότι η μέθοδος 14#14 έχει φτάσει στη σύγκλιση σε μία μοναδική επανάληψη σε αυτή την περίπτωση δεν θα πρέπει να μας εκπλήσσει, αφού το να ελαχιστοποιηθεί η συνάρτηση είναι τετραγωνική μέθοδος. Φυσικά, το τετραγωνικό μοντέλο που χρησιμοποιείται από τη μέθοδο 14#14 δεν είναι ακριβές γενικά, αλλά τουλάχιστον επιτρέπει στη μέθοδο 14#14 να παίρνει μία πιο γενική άποψη του προβλήματος, παράγοντας πολύ πιο γρήγορη σύγκλιση από τη μέθοδο της μέγιστης αρνητικής κλίσης.


27#27

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

Σε αντίθεση με τη μέθοδο της μέγιστης αρνητικής κλίσης, η μέθοδος 14#14 δεν απαιτεί έρευνα για παράμετρο ευθείας επειδή το τετραγωνικό μοντέλο καθορίζει τόσο ένα κατάλληλο μήκος όσο και μία κατεύθυνση για το βήμα προς την επόμενη προσεγγιστική λύση. Παρόλα αυτά, όταν ξεκινάει μακρυά από τη λύση, μπορεί να είναι φρόνιμο να εκτελέσουμε μία έρευνα ευθείας κατά μήκος της διεύθυνσης του βήματος 1300#1300 της μεθόδου 14#14 προκειμένου να κάνουμε τη μέθοδο πιο (robust) (αυτή η διαδικασία μερικές φορές λέγεται (damped) μέθοδος 14#14). Όταν οι επαναλήψεις βρίσκονται κοντά στη λύση, η τιμή 1306#1306 για αυτή την παράμετρο έρευνας ευθείας θα πρέπει να επαρκεί για τις διαδοχικές επαναλήψεις.

Μία εναλλακτική μέθοδος για τη μέθοδο εύρεσης γραμμής είναι η μέθοδος βασικής περιοχής, στην οποία μία εκτίμηση παραμένει εντός της ακτίνας μίας περιοχής στην οποία το τετραγωνικό μοντέλο είναι αρκετά ακριβές ώστε το βήμα της μεθόδου 14#14 που υπολογίζουμε να είναι αξιόπιστο (δείτε την Ενότητα 5.3.5), και άρα η επόμενη προσεγγιστική λύση δεσμεύεται να βρίσκεται μέσα στη βασική περιοχή.

Σχήμα 6.6 Τροποποίηση του βήματος Newton από τη μέθοδο της βασικής περιοχής.

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

Αν η συνάρτηση κόστους 51#51 έχει συνεχείς δεύτερες μερικές παραγώγους, τότε ο Εσσιανός πίνακας 1307#1307 είναι συμμετρικός, και κοντά σε κάποιο ελάχιστο είναι θετικά ορισμένος. Άρα, το γραμμικό σύστημα για το βήμα στην επόμενη επανάληψη μπορεί να λυθεί μέσω της παραγοντοποίησης Cholesky, απαιτώντας περίπου μόνο τη μισή δουλειά από αυτήν που απαιτείται για την παραγοντοποίηση 2#2. Παρόλα αυτά, μακρυά από ένα ελάχιστο, η 1308#1308 μπορεί να μην είναι θετικά ορισμένη και άρα ίσως να απαιτεί μία συμμετρική αόριστη παραγοντοποίηση. Το τελικό βήμα Newton 1300#1300 μπορεί να μην έχει καν κατεύθυνση προς τα κάτω για τη συνάρτηση, δηλ., μπορεί να μην έχει

1309#1309

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



Manolis Vavalis 2000-03-24