Ξεχάσατε τον κωδικό σας?
Η Μέθοδος της Μέγιστης Αρνητικής Κλίσης
Document Actions
Next: Η Μέθοδος Up: ΠΟΛΥΔΙΑΣΤΑΤΗ ΦΥΣΙΚΗ ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ Previous: μεσες Μέθοδοι Έρευνας Contents
Η Μέθοδος της Μέγιστης Αρνητικής Κλίσης
Όπως θα περιμέναμε, περισσότερη χρήση της συνάρτησης κόστους και των παραγώγων της οδηγεί σε γρηγορότερες μεθόδους. Έστω ότι η 1202#1202 είναι μία συνάρτηση πραγματικών τιμών 366#366 πραγματικών μεταβλητών. Θυμηθείτε ότι η κλίση της 51#51 εκτιμόμενη στο 33#33, που υποδηλώνεται από την 1206#1206, είναι μία συνάρτηση με τιμές-διανύσματα της οποίας το 824#824-στό στοιχείο-διάνυσμα είναι η μερική παράγωγος της 51#51 ως προς το 1203#1203, 1207#1207. Από υπολογισμούς, γνωρίζουμε ότι σε ένα δοσμένο σημείο 33#33 όπου το διάνυσμα της κλίσης είναι μη μηδενικό, η αρνητική κλίση, 1284#1284, δείχνει προς τα κάτω προς τις μικρότερες τιμές της συνάρτησης 51#51. Στην ουσία, η 1284#1284 είναι τοπικά η διεύθυνση της μεγαλύτερης αρνητικής κλίσης της συνάρτησης 51#51 με την έννοια ότι η τιμή της μειώνεται πιο απότομα κατά μήκος της διεύθυνσης της αρνητικής κλίσης από ότι κατά μήκος οποιασδήποτε άλλης διεύθυνσης.
Αυτό το γεγονός οδηγεί σε μία από τις παλαιότερες μεθόδους βελτιστοποίησης στις πολλές διαστάσεις, στη μέθοδο της μέγιστης αρνητικής κλίσης. Ξεκινώντας από κάποια αρχική υπόθεση για το 1092#1092, κάθε διαδοχική προσεγγιστική λύση δίνεται από τον
όπου το 1286#1286 είναι μία παράμετρος έρευνας ευθείας η οποία καθορίζει πόσο να προχωρήσουμε πάνω στη δοσμένη διεύθυνση.
Δοσμένης μίας διεύθυνσης αρνητικής κλίσης, όπως η αρνητική κλίση, ο καθορισμός μίας κατάλληλης τιμής για την παράμετρο έρευνας ευθείας 1287#1287 σε κάθε επανάληψη είναι ένα μονοδιάστατο πρόβλημα ελαχιστοποίησης
το οποίο μπορεί να λυθεί με τις μεθόδους που μελετήσαμε στην Ενότητα 6.2. Η μέθοδος μέγιστης αρνητικής κλίσης είναι πολύ αξιόπιστη με την έννοια ότι μπορεί πάντα να επιφέρει βελτίωση δεδομένου ότι η κλίση είναι μη μηδενική. Αλλά όπως δείχνει το παράδειγμα που ακολουθεί, η μέθοδος σχετικά μυωπική ως προς το πώς βλέπει τη συμπεριφορά της συνάρτησης, και οι τελικές επαναλήψεις μπορούν να πηγαινοέρχονται μπρος-πίσω, πηγαίνοντας προοδευτικά, πολύ αργά προς τη λύση. Γενικά, ο βαθμός σύγκλισης της μέγιστης αρνητικής κλίσης είναι μόνο γραμμικός, με ένα σταθερό παράγοντα ο οποίος μπορεί αυθαίρετα να είναι κοντά στο 1.
της οποίας η κλίση δίνεται από την
Αν πάρουμε το
1291#1291 ως αρχικό σημείο, η κλίση είναι
1292#1292. Στη συνέχεια επιδεικνύουμε μία έρευνα ευθείας κατά μήκος
της διεύθυνσης της αρνητικής κλίσης, π.χ.,
Η μονοδιάστατη ελαχιστοποίηση της 51#51 ως συνάρτηση του 431#431 κατά μήκος της ευθείας δίνει 1294#1294, οπότε η επόμενη προσέγγιση είναι η 1295#1295. Στη συνέχεια υπολογίζουμε την κλίση σε αυτό το νέο σημείο για να καθορίσουμε τη διεύθυνση της επόμενης έρευνας και επαναλαμβάνουμε τη διαδικασία. Η ακολουθία των επαναλήψεων που προκύπτει φαίνεται αριθμητικά στον πίνακα που ακολουθεί και γραφικά στο Σχήμα 6.5, όπου οι ελλείψεις αναπαριστούν καμπύλες επιπέδων, ή περιγεγραμμένα σχήματα, στα οποία η συνάρτηση 51#51 έχει σταθερή τιμή. Η διεύθυνση της κλίσης για κάθε δοσμένο σημείο είναι πάντα κανονική ως προς την καμπύλη της ευθείας που περνάει από αυτό το σημείο. Παρατηρείστε ότι το ελάχιστο κατά μήκος μίας δοσμένης κατεύθυνσης έρευνας το συναντάμε όταν η κλίση σε αυτό το νέο σημείο είναι ορθογώνιο στην κατεύθυνση έρευνας. Η ακολουθία των επαναλήψεων που παίρνουμε από τη μέγιστη αρνητική κλίση συγκλίνει αργά προς τη λύση, η οποία για αυτό το πρόβλημα βρίσκεται στην αρχή των συντεταγμένων, όπου η ελάχιστη συνάρτηση είναι μηδενική.
Manolis Vavalis 2000-03-24
