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

Μέθοδοι Ενημέρωσης των 16#16

Όπως και με τις μεθόδους ενημέρωσης των 16#16 για την επίλυση μη γραμμικών εξισώσεων, το κίνητρο για τη χρήση μεθόδων ενημέρωσης των 16#16 για την ελαχιστοποίηση είναι το να μειώσουν την εργασία σε κάθε επανάληψη της μεθόδου Newton και πιθανόν να βελτιώσουν την 1318#1318. Θα μπορούσε κανείς απλώς να χρησιμοποιήσει τη μέθοδο 1319#1319 για να αναζητήσει ένα σημείο όπου η κλίση γίνεται μηδέν, αλλά αυτή η προσέγγιση δεν θα διατηρούσε τη συμμετρία του Εσσιανού πίνακα. Έχουν αναπτυχθεί διάφορες φόρμες ενημέρωσης 16#16 για φυσική ελαχιστοποίηση οι οποίες όχι απλά διατηρούν τη συμμετρία στον προσεγγιστικό Εσσιανό πίνακα αλλά επίσης προστατεύουν το ότι είναι θετικά ορισμένος. Η συμμετρία μειώνει τη δουλειά που πρέπει να γίνει περίπου στο μισό, και η ιδιότητα του ότι είναι θετικά ορισμένος εγγυάται ότι το βήμα της μεθόδου 1314#1314 θα έχει κατεύθυνση προς τα κάτω.

Μία από τις πιο αποτελεσματικές από τις μεθόδους ενημέρωσης @secant@ για την ελαχιστοποίηση είναι η λεγόμενη 1320#1320, από τα αρχικά των τεσσάρων ατόμων που την επινόησαν. Ξεκινώντας υποθέτωντας μία αρχική τιμή 1092#1092 και έναν συμμετρικό θετικά ορισμένο Εσσιανό πίνακα 1321#1321, τα παρακάτω βήματα επαναλαμβάνονται μέχρι να επιτευχθεί η σύγκλιση.

  1. Λύνουμε το 1322#1322
  2. 1323#1323
  3. 1324#1324
  4. 1325#1325

Στην πράξη, ενημερώνεται μία παραγοντοποίηση του 1326#1326 αντί του ίδιου του 1326#1326, έτσι ώστε το γραμμικό σύστημα του βήματος της 1314#1314 μεθόδου να μπορεί να λυθεί με κόστος εργασίας 1313#1313 αντί για 1312#1312. Παρατηρείστε ότι σε αντίθεση με τη μέθοδο Newton για την ελαχιστοποίηση, δεν απαιτούνται δεύτερες παράγωγοι. Αυτές οι μέθοδοι συχνά ξεκινάνε με 1327#1327, το οποίο σημαίνει ότι το αρχικό βήμα βρίσκεται κατά μήκος της αρνητικής κλίσης (δηλ., στη διεύθυνση της μέγιστης αρνητικής κλίσης), και τότε οι πληροφορίες για τη δεύτερη παράγωγο αναπτύσσονται βαθμιαία στον προσεγγιστικό Εσσιανό πίνακα μέσω διαδοχικών επαναλήψεων.

Όπως και οι περισσότερες μέθοδοι ενημέρωσης 16#16, η 1320#1320 κανονικά έχει υπεργραμμικό βαθμό σύγκλισης, παρόλο που ένας προσεγγιστικός Εσσιανός πίνακας δεν συγκλίνει απαραίτητα στον πραγματικό Εσσιανό. Ακόμα, μία αναζήτηση ευθείας μπορεί να χρησιμοποιηθεί για να προάγει την αποτελεσματικότητα της μεθόδου. Πράγματι, για μία τετραγωνική συνάρτηση κόστους, αν εκτελείται μία ακριβής αναζήτηση ευθείας σε κάθε επανάληψη, τότε η μέθοδος 1320#1320 καταλήγει στην ακριβή λύση μέσα σε το πολύ 366#366 επαναλήψεις, όπου 366#366 είναι η διάσταση του προβλήματος.


27#27

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

1329#1329

Ξεκινώντας με το 1291#1291 και με 1330#1330, το αρχικό βήμα είναι απλά η αρνητική κλίση, οπότε

1331#1331

Ενημερώνοντας τον προσεγγιστικό Εσσιανό πίνακα σύμφωνα με τη φόρμα του 1320#1320, παίρνουμε

1332#1332

Τώρα υπολογίζεται ένα νέο βήμα και η διαδικασία συνεχίζεται. Η ακολουθία των επαναλήψεων φαίνεται στον παρακάτω πίνακα:

Η αύξηση στην τιμή της συνάρτησης κατά την πρώτη επανάληψη θα μπορούσε να έχει αποφευχθεί χρησιμοποιώντας μία αναζήτηση ευθείας.


27#27



Manolis Vavalis 2000-03-24