Η Μέθοδος 14#14

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

Διαισθητικά, η φυσική ελαχιστοποίηση είναι σαν να βρίσκεις τον πάτο ενός ημισφαιρίου αφήνοντας μία γυάλινη μπάλα να κυλήσει από τη μια του άκρη. Αν το ημισφαίριο είναι επιμήκες, τότε η μπάλα θα κινείται μπρος-πίσω στο αυλάκι πριν τελικά να σταθεροποιηθεί στον πάτο, κατά ανάλογο τρόπο με το μονοπάτι που παίρνουμε όταν πηγαινοέρχεται κατά τη μέθοδο της μέγιστης αρνητικής κλίσης. Με τη μέθοδο 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 μπορεί να μην έχει καν κατεύθυνση προς τα κάτω για τη συνάρτηση, δηλ., μπορεί να μην έχει