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

Μέθοδος Κοινών Χαρακτηριστικών των Κλίσεων

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

Όπως είδαμε στην Ενότητα 6.3.2, η μέθοδος της μέγιστης αρνητικής κλίσης τείνει να ψάχνει προς τις ίδιες διευθύνσεις επαναλαμβανόμενα, οδηγώντας σε πολύ αργή σύγκλιση. Όπως δηλώνει και το όνομά της, η μέθοδος κοινών χαρακτηριστικών των κλίσεων χρησιμοποιεί και κλίσεις, αλλά αποφεύγει τις επαναλαμβανόμενες αναζητήσεις τροποποιώντας την κλίση σε κάθε βήμα ώστε να απορρίπτει τα στοιχεία που βρίσκονται σε προηγούμενες διευθύνσεις. Η ακολουθία που προκύπτει από τα καονά χαρακτηριστικά (δηλ., ορθογώνιες σε κάποιο εσωτερικό γινόμενο) διευθύνσεων αναζήτησης αναμφίβολα συσσωρεύει πληροφορίες σχετικά με τον Εσσιανό πίνακα όσο προχωράνε οι επαναλήψεις. Θεωρητικά, η μέθοδος είναι ακριβής μετά από το πολύ 366#366 επαναλήψεις για μία τετραγωνική συνάρτηση κόστους στις 366#366 διαστάσεις, αλλά συνήθως είναι αρκετά αποτελεσματική επίσης και για πιο γενικά φυσικά προβλήματα ελαχιστοποίησης. Το κίνητρο για αυτόν τον αλγόριθμο το μελετάμε στην Ενότητα 11.5.5.

Για να ελαχιστοποιήσουμε τη συνάρτηση 51#51 ξεκινώντας από μία αρχική υπόθεση 1092#1092, αρχικοποιούμε τα 1333#1333 και 1334#1334. Στη συνέχεια επαναλαμβάνονται τα ακόλουθα βήματα μέχρι να επιτευχθεί η σύγκλιση.

  1. 1335#1335
  2. 1336#1336
  3. 1337#1337
  4. 1338#1338

Η φόρμα για το 1339#1339 που δίνεται πιο πάνω οφείλεται στους 1340#1340 και 1341#1341. Μία εναλλακτική φόρμα, που οφείλεται στους 1342#1342 και 1343#1343, είναι η


1344#1344

Είναι συνηθισμένο να επαναξεκινάμε τον αλγόριθμο μετά από 366#366 επαναλήψεις, επαναρχικοποιώντας για να χρησιμοποιήσουμε την αρνητική κλίση στο τρέχον σημείο.


27#27

Παράδειγμα 6.7   ΜΕΘΟΔΟΣ ΚΟΙΝΩΝ ΧΑΡΑΚΤΗΡΙΣΤΙΚΩΝ ΚΛΙΣΕΩΝ. Παρουσιάζουμε τη μέθοδο των κοινών χαρακτηριστικών των κλίσεων χρησιμοποιώντας την για να ελαχιστοποιήσουμε τη συνάρτηση

1289#1289

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

1329#1329

Ξεκινώντας με το 1291#1291 η αρχική κατεύθυνση αναζήτησης είναι η αρνητική κλίση,

1345#1345

Το ακριβές ελάχιστο κατά μήκους αυτής της ευθείας δίνεται από την 1346#1346, οπότε η επόμενη προσέγγιση είναι η 1295#1295 και σε αυτό το σημείο υπολογίζουμε τη νέα κλίση,

1347#1347

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

1348#1348

η οποία μας δίνει την επόμενη διεύθυνση αναζήτησης

1349#1349

Το ελάχιστο κατά μήκος αυτής της διεύθυνσης δίνεται από τη 1350#1350, η οποία δίνει την ακριβή λύση του αρχικού προβλήματος. Άρα, όπως θα περίμενε κανείς για μία τετραγωνική συνάρτηση, η μέθοδος κοινών χαρακτηριστικών των κλίσεων συγκλίνει σε 1351#1351 βήματα σε αυτή την περίπτωση.


27#27



Manolis Vavalis 2000-03-24