next up previous contents
Next: Ακρίβεια των Λύσεων Up: Βελτιστοποιήση Previous: Βελτιστοποιήση   Contents

Σχέση με Μη Γραμμικά Προβλήματα

Η βελτιστοποίηση σχετίζεται με την εύρεση ριζών της συνάρτησης επειδή το μέγιστο των ομαλών συναρτήσεων αντιστοιχεί στη ρίζα των παραγώγων τους. Για παράδειγμα, αν το 1048#1048 ελαχιστοποιεί μία ομαλή συνάρτηση 1202#1202, τότε η μερική παράγωγος της 51#51 για την κάθε μεταβλητή 1203#1203 είναι μηδέν, που σημαίνει ότι το 1048#1048 είναι λύση του συστήματος εξισώσεων 1204#1204. (Θυμηθείτε ότι η κλίση της 51#51 που εκτιμάται για την τιμή 1205#1205, η οποία δηλώνεται από την 1206#1206, είναι ένα διάνυσμα συναρτήσεων του οποίου η 824#824-στή συνιστώσα συνάρτηση είναι η μερική παράγωγος της 51#51 για την τιμή 1203#1203, 1207#1207.]

Παρόλα αυτά, δεν ισχύει το αντίστροφο: μία λύση σε ένα σύστημα μη γραμμικών εξισώσεων 1204#1204, που είναι γνωστή ως στάσιμο ή κρίσιμο σημείο, μπορεί να είναι είτε ελάχιστο, είτε μέγιστο της 51#51, είτε τίποτα από τα δύο (π.χ., ένα σαγματικό σημείο). Παρόλα αυτά, πολλές μέθοδοι βελτιστοποίησης βασίζονται στην αναζήτηση ενός κρίσιμου σημείου μίας βαθμωτης συνάρτησης, η οποία είναι ένα σύστημα από εξισώσεις (γενικά μη γραμμικές). Κάθε υποψήφια λύση που βρέθηκε με μία τέτοια μέθοδο πρέπει να ελέγχεται για το αν είναι η βέλτιστη.

Μπορούμε να ελέγξουμε ένα κρίσιμο σημείο 33#33 μίας φυσικής υπαρκτής συνάρτησης 51#51 για το αν είναι βέλτιστο αν θεωρήσουμε τον Εσσιανό πίνακα 1208#1208 των δευτέρων μερικών παραγώγων της 51#51,

1209#1209

για την τιμή 33#33. Αν η 51#51 έχει συνεχείς δεύτερες μερικές παραγώγους, ο Εσσιανός πίνακας 1210#1210 είναι συμμετρικός. Για ένα κρίσιμο σημείο 33#33, όπου 1204#1204,

Υπάρχουν διάφοροι τρόποι να δοκιμάσουμε αν ένας συμμετρικός πίνακας είναι θετικά ορισμένος. Ένας από τους πιο απλούς και πιο φθηνούς είναι να δοκιμάσουμε να υπολογίσουμε την παραγοντοποίηση 883#883 του πίνακα: ο αλγόριθμος 883#883 θα πετύχει αν και μόνο αν ο πίνακας είναι θετικά ορισμένος (φυσικά, αυτή η πρόταση υποθέτει ότι διαθέτουμε μία ρουτίνα 883#883 η οποία αποτυγχάνει όταν της δώσουμε ως είσοδο έναν μη θετικά ορισμένο πίνακα). Μία άλλη καλή μέθοδος είναι να υπολογίζουμε την αδράνεια του πίνακα (δείτε την Ενότητα 4.3.10) χρησιμοποιώντας μία συμμετρική παραγοντοποίηση της μορφής 1211#1211, όπως κάναμε στην Ενότητα 2.5.2. Μία πολύ πιο ακριβή προσέγγιση είναι να υπολογίζουμε τις ιδιοτιμές του πίνακα και να ελέγχουμε αν είναι όλες θετικές.



Manolis Vavalis 2000-03-24