Η απλούστερη μέθοδος κλίσης. Μέθοδοι βελτιστοποίησης χωρίς περιορισμούς κλίσης

Η μέθοδος βασίζεται στην ακόλουθη επαναληπτική τροποποίηση του τύπου

x k +1 = x k + a k s(x k),

x k+1 = x k - a k Ñ f(x k), όπου

α - δεδομένος θετικός συντελεστής.

Ñ ​​​​f(x k) - κλίση αντικειμενική λειτουργίαπρώτη σειρά.

Ελαττώματα:

την ανάγκη επιλογής κατάλληλης τιμής του .

αργή σύγκλιση στο ελάχιστο σημείο λόγω της μικρότητας του f(x k) στην περιοχή του σημείου αυτού.

Μέθοδος απότομης κατάβασης

Ελεύθερος από το πρώτο μειονέκτημα της απλούστερης μεθόδου κλίσης, αφού Το a k υπολογίζεται επιλύοντας το πρόβλημα ελαχιστοποίησης Ñ f(x k) κατά την κατεύθυνση Ñ f(x k) χρησιμοποιώντας μία από τις μονοδιάστατες μεθόδους βελτιστοποίησης x k+1 = x k - a k Ñ f(x k).

Αυτή η μέθοδος μερικές φορές ονομάζεται μέθοδος Cauchy.

Ο αλγόριθμος χαρακτηρίζεται από χαμηλό ποσοστό σύγκλισης στην επίλυση πρακτικών προβλημάτων. Αυτό εξηγείται από το γεγονός ότι η μεταβολή των μεταβλητών εξαρτάται άμεσα από το μέγεθος της κλίσης, η οποία τείνει στο μηδέν κοντά στο ελάχιστο σημείο και δεν υπάρχει μηχανισμός επιτάχυνσης στις τελευταίες επαναλήψεις. Επομένως, λαμβάνοντας υπόψη τη σταθερότητα του αλγορίθμου, η μέθοδος της πιο απότομης καθόδου χρησιμοποιείται συχνά ως αρχική διαδικασία για την εύρεση λύσης (από σημεία που βρίσκονται σε σημαντικές αποστάσεις από το ελάχιστο σημείο).

Μέθοδος κατεύθυνσης συζυγούς

Το γενικό πρόβλημα του μη γραμμικού προγραμματισμού χωρίς περιορισμούς είναι το εξής: ελαχιστοποίηση f(x), x E n , όπου f(x) είναι η αντικειμενική συνάρτηση. Κατά την επίλυση αυτού του προβλήματος, χρησιμοποιούμε μεθόδους ελαχιστοποίησης που οδηγούν σε ένα ακίνητο σημείο f(x) που ορίζεται από την εξίσωση f(x *)=0. Η μέθοδος συζευγμένης κατεύθυνσης αναφέρεται σε μεθόδους απεριόριστης ελαχιστοποίησης που χρησιμοποιούν παράγωγα. Εργασία: ελαχιστοποίηση f(x), x E n , όπου f(x) είναι η αντικειμενική συνάρτηση n ανεξάρτητων μεταβλητών. Ένα σημαντικό χαρακτηριστικόείναι γρήγορη σύγκλιση λόγω του γεγονότος ότι κατά την επιλογή της κατεύθυνσης, χρησιμοποιείται η μήτρα Hessian, η οποία περιγράφει την περιοχή της τοπολογίας της επιφάνειας απόκρισης. Συγκεκριμένα, εάν η αντικειμενική συνάρτηση είναι τετραγωνική, τότε το ελάχιστο σημείο μπορεί να ληφθεί σε όχι περισσότερο από έναν αριθμό βημάτων ίσο με τη διάσταση του προβλήματος.

Για να εφαρμοστεί η μέθοδος στην πράξη, πρέπει να συμπληρωθεί με διαδικασίες ελέγχου της σύγκλισης και της γραμμικής ανεξαρτησίας του συστήματος κατεύθυνσης. Μέθοδοι δεύτερης τάξης

Η μέθοδος του Νεύτωνα

Η διαδοχική εφαρμογή του σχήματος τετραγωνικής προσέγγισης οδηγεί στην εφαρμογή της μεθόδου βελτιστοποίησης του Newton σύμφωνα με τον τύπο

x k +1 = x k - Ñ 2 f(x k -1) Ñ f(x k).

Το μειονέκτημα της μεθόδου του Newton είναι η ανεπαρκής αξιοπιστία της κατά τη βελτιστοποίηση μη τετραγωνικών αντικειμενικών συναρτήσεων. Ως εκ τούτου, συχνά τροποποιείται:

x k +1 = x k - a k Ñ 2 f(x k -1) Ñ f(x k), όπου

a k είναι μια παράμετρος που επιλέγεται έτσι ώστε f(x k+1) min.

2. Εύρεση του άκρου μιας συνάρτησης χωρίς περιορισμό

Κάποια συνάρτηση f(x) δίνεται σε ένα ανοιχτό διάστημα (a, c) της αλλαγής στο όρισμα x. Υποθέτουμε ότι το exst υπάρχει μέσα σε αυτό το διάστημα (πρέπει να ειπωθεί ότι, στη γενική περίπτωση, αυτό δεν μπορεί να δηλωθεί μαθηματικά εκ των προτέρων· ωστόσο, σε τεχνικές εφαρμογές, η παρουσία του exst πολύ συχνά μέσα σε ένα ορισμένο διάστημα μεταβολής της παραλλαγής του ορίσματος το διάστημα μπορεί να προβλεφθεί από φυσικές εκτιμήσεις).

Ορισμός exst. Η συνάρτηση f (x) που δίνεται στο διάστημα (a, c) έχει στο σημείο x * max (min), εάν αυτό το σημείο μπορεί να περιβάλλεται από ένα τέτοιο διάστημα (x * -ε, x * + ε) που περιέχεται στο διάστημα (a, c) , ότι για όλα τα σημεία του x που ανήκουν στο διάστημα (x * -ε, x * +ε), ισχύει η ακόλουθη ανισότητα:

f(x) ≤ f(x *) → για μέγ

f(x) ≥ f(x *) → για ελάχ

Αυτός ο ορισμός δεν επιβάλλει περιορισμούς στην κατηγορία των συναρτήσεων f(x), η οποία, φυσικά, είναι πολύ πολύτιμη.

Αν περιοριστούμε για τις συναρτήσεις f(x) σε μια αρκετά κοινή, αλλά ακόμα πιο στενή κατηγορία ομαλών συναρτήσεων (με τον όρο ομαλές συναρτήσεις εννοούμε συναρτήσεις που είναι συνεχείς μαζί με τις παράγωγές τους στο διάστημα αλλαγής του ορίσματος), τότε μπορούμε χρησιμοποιήστε το θεώρημα Fermat, το οποίο δίνει τις απαραίτητες προϋποθέσεις για την ύπαρξη exst.

Θεώρημα Fermat. Έστω η συνάρτηση f(x) να οριστεί σε κάποιο διάστημα (a, b) και στο σημείο "c" αυτού του διαστήματος παίρνει τη μεγαλύτερη (μικρότερη) τιμή. Αν υπάρχει δίπλευρη πεπερασμένη παράγωγος σε αυτό το σημείο, τότε η ύπαρξη exst είναι απαραίτητη.

Σημείωση. Η αμφίπλευρη παράγωγος χαρακτηρίζεται από την ιδιότητα, με άλλα λόγια, μιλαμεσχετικά με το γεγονός ότι στο σημείο "c" η παράγωγος στο όριο είναι η ίδια όταν πλησιάζει το σημείο "c" από αριστερά και δεξιά, δηλ. f (x) - ομαλή λειτουργία.

* Στην περίπτωση min λαμβάνει χώρα, και όταν →max. Τέλος, αν στο x=x 0, τότε η χρήση της 2ης παραγώγου δεν βοηθά και πρέπει να χρησιμοποιήσετε, για παράδειγμα, τον ορισμό του exst.

Κατά την επίλυση του Προβλήματος Ι, χρησιμοποιούνται πολύ συχνά οι απαραίτητες προϋποθέσεις (δηλαδή το θεώρημα του Fermat).

Αν η εξίσωση exst έχει πραγματικές ρίζες, τότε τα σημεία που αντιστοιχούν σε αυτές τις ρίζες είναι ύποπτα για την exst (αλλά όχι απαραίτητα τα ίδια τα άκρα, γιατί έχουμε να κάνουμε με αναγκαίες, και όχι με αναγκαίες και επαρκείς συνθήκες). Έτσι, για παράδειγμα, στο σημείο καμπής λαμβάνει χώρα το X p, ωστόσο, όπως γνωρίζετε, αυτό δεν είναι άκρο.

Να σημειώσουμε επίσης ότι:

από απαραίτητες προϋποθέσειςείναι αδύνατο να πούμε ποιος τύπος ακραίου βρέθηκε max ή min: απαιτείται πρόσθετη έρευνα για να προσδιοριστεί αυτό.

είναι αδύνατο να προσδιοριστεί από τις απαραίτητες συνθήκες εάν πρόκειται για παγκόσμιο άκρο ή για τοπικό.

Επομένως, όταν εντοπίζονται σημεία ύποπτα για exst, διερευνώνται επιπλέον, για παράδειγμα, με βάση τον ορισμό του exst ή της 2ης παραγώγου.

Μέθοδος κλίσης καθόδου.

Κατεύθυνση η πιο απότομη κατάβασηαντιστοιχεί στην κατεύθυνση της μεγαλύτερης μείωσης της συνάρτησης. Είναι γνωστό ότι η κατεύθυνση της μεγαλύτερης αύξησης της συνάρτησης δύο μεταβλητών u = f(x, y) χαρακτηρίζεται από την κλίση της:

όπου e1, e2 - μοναδιαία διανύσματα(orts) προς την κατεύθυνση των αξόνων συντεταγμένων. Επομένως, η κατεύθυνση αντίθετη από τη διαβάθμιση θα υποδεικνύει την κατεύθυνση της μεγαλύτερης μείωσης στη συνάρτηση. Οι μέθοδοι που βασίζονται στην επιλογή μιας διαδρομής βελτιστοποίησης χρησιμοποιώντας μια κλίση καλούνται βαθμίδα.

Η ιδέα πίσω από τη μέθοδο gradient descent είναι η εξής. Επιλέγοντας κάποιο σημείο εκκίνησης

υπολογίζουμε τη διαβάθμιση της εξεταζόμενης συνάρτησης σε αυτήν. Κάνουμε ένα βήμα προς την αντίθετη κατεύθυνση από την κλίση:

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

Η μέθοδος κλίσης καθόδου έχει το ίδιο μειονέκτημα με τη μέθοδο συντεταγμένης καθόδου: παρουσία χαράδρων στην επιφάνεια, η σύγκλιση της μεθόδου είναι πολύ αργή.

Στην περιγραφόμενη μέθοδο, απαιτείται ο υπολογισμός της διαβάθμισης της αντικειμενικής συνάρτησης f(x) σε κάθε βήμα βελτιστοποίησης:

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

Όταν χρησιμοποιείται βαθμιδωτή κάθοδος σε προβλήματα βελτιστοποίησης, ο κύριος αριθμός υπολογισμών συνήθως πέφτει στον υπολογισμό της κλίσης της αντικειμενικής συνάρτησης σε κάθε σημείο της τροχιάς καθόδου. Ως εκ τούτου, συνιστάται να μειώσετε τον αριθμό τέτοιων σημείων χωρίς να διακυβεύεται η ίδια η λύση. Αυτό επιτυγχάνεται σε ορισμένες μεθόδους που είναι τροποποιήσεις gradient descent. Ένα από αυτά είναι η πιο απότομη μέθοδος καθόδου. Σύμφωνα με αυτή τη μέθοδο, μετά τον προσδιορισμό της κατεύθυνσης αντίθετης από την κλίση της αντικειμενικής συνάρτησης στο αρχικό σημείο, επιλύεται ένα μονοδιάστατο πρόβλημα βελτιστοποίησης ελαχιστοποιώντας τη συνάρτηση κατά μήκος αυτής της κατεύθυνσης. Δηλαδή, η συνάρτηση ελαχιστοποιείται:

Για ελαχιστοποίηση μπορεί να χρησιμοποιηθεί μία από τις μεθόδους μονοδιάστατης βελτιστοποίησης. Είναι επίσης δυνατό να κινηθείτε απλώς προς την αντίθετη κατεύθυνση από τη διαβάθμιση, ενώ δεν κάνετε ένα βήμα, αλλά πολλά βήματα μέχρι να σταματήσει η μείωση της αντικειμενικής συνάρτησης. Στο νέο σημείο που βρέθηκε, η κατεύθυνση της κάθοδος προσδιορίζεται και πάλι (χρησιμοποιώντας μια κλίση) και ένα νέο ελάχιστο σημείο της αντικειμενικής συνάρτησης κ.λπ. υπολογίζεται σε λιγότεροισημεία. Η διαφορά είναι ότι εδώ η κατεύθυνση της μονοδιάστατης βελτιστοποίησης καθορίζεται από την κλίση της αντικειμενικής συνάρτησης, ενώ η κατά συντεταγμένη κάθοδος πραγματοποιείται σε κάθε βήμα κατά μήκος μιας από τις κατευθύνσεις συντεταγμένων.

Μέθοδος απότομης καθόδου για την περίπτωση συνάρτησης δύο μεταβλητών z = f(x,y).

Πρώτον, είναι εύκολο να δείξουμε ότι η κλίση της συνάρτησης είναι κάθετη στην εφαπτομένη στη γραμμή στάθμης σε ένα δεδομένο σημείο. Επομένως, στις μεθόδους κλίσης, η κάθοδος συμβαίνει κατά μήκος της γραμμής κανονικής προς την στάθμη. Δεύτερον, στο σημείο όπου επιτυγχάνεται το ελάχιστο της αντικειμενικής συνάρτησης κατά μήκος της διεύθυνσης, η παράγωγος της συνάρτησης κατά μήκος αυτής της κατεύθυνσης εξαφανίζεται. Όμως η παράγωγος της συνάρτησης είναι μηδέν προς την κατεύθυνση της εφαπτομένης στη γραμμή στάθμης. Συνεπάγεται ότι η κλίση της αντικειμενικής συνάρτησης στο νέο σημείο είναι κάθετη προς την κατεύθυνση της μονοδιάστατης βελτιστοποίησης στο προηγούμενο βήμα, δηλ. η κάθοδος σε δύο διαδοχικά βήματα πραγματοποιείται σε αμοιβαία κάθετες κατευθύνσεις.

Θα ρίξω μερικές από τις εμπειρίες μου :)

Μέθοδος καθόδου συντεταγμένων

Η ιδέα αυτής της μεθόδου είναι ότι η αναζήτηση πραγματοποιείται προς την κατεύθυνση της κάθοδος συντεταγμένων κατά τη νέα επανάληψη. Η κάθοδος πραγματοποιείται σταδιακά κατά μήκος κάθε συντεταγμένης. Ο αριθμός των συντεταγμένων εξαρτάται άμεσα από τον αριθμό των μεταβλητών.
Για να δείξετε πώς λειτουργεί αυτή η μέθοδος, πρέπει πρώτα να πάρετε τη συνάρτηση z = f(x1, x2,…, xn) και να επιλέξετε οποιοδήποτε σημείο M0(x10, x20,…, xn0) σε n χώρο, το οποίο εξαρτάται από τον αριθμό των χαρακτηριστικά της συνάρτησης. Επόμενο βήμα βήμακαθορίζοντας όλα τα σημεία της συνάρτησης σε μια σταθερά, εκτός από το πρώτο. Αυτό γίνεται για αναζήτηση πολυμεταβλητή βελτιστοποίησηνα μειώσει το πρόβλημα της μονοδιάστατης βελτιστοποίησης, δηλαδή την αναζήτηση για το όρισμα x1, στη λύση της αναζήτησης σε ένα συγκεκριμένο τμήμα.
Για να βρείτε την τιμή αυτής της μεταβλητής, είναι απαραίτητο να κατεβείτε κατά μήκος αυτής της συντεταγμένης στο νέο σημείο M1(x11, x21,…, xn1). Επιπλέον, η συνάρτηση διαφοροποιείται και στη συνέχεια μπορούμε να βρούμε την τιμή του νέου επόμενου σημείου χρησιμοποιώντας αυτήν την έκφραση:

Αφού βρείτε την τιμή της μεταβλητής, πρέπει να επαναλάβετε την επανάληψη διορθώνοντας όλα τα ορίσματα εκτός από το x2 και να αρχίσετε να φθίνετε νέα συντεταγμένηστο επόμενο νέο σημείο M2(x11,x21,x30…,xn0). Τώρα η τιμή του νέου σημείου θα εμφανίζεται σύμφωνα με την έκφραση:

Και πάλι, η επανάληψη με σταθεροποίηση θα επαναληφθεί μέχρι να τελειώσουν όλα τα ορίσματα από το xi στο xn. Στην τελευταία επανάληψη, θα περάσουμε διαδοχικά από όλες τις πιθανές συντεταγμένες στις οποίες ήδη βρείτε τοπικά ελάχιστα, οπότε η αντικειμενική συνάρτηση στην τελευταία συντεταγμένη θα φτάσει το συνολικό ελάχιστο. Ένα από τα πλεονεκτήματα αυτής της μεθόδου είναι ότι ανά πάσα στιγμή είναι δυνατό να διακοπεί η κάθοδος και το τελευταίο σημείο που θα βρεθεί θα είναι το ελάχιστο σημείο. Αυτό είναι χρήσιμο όταν η μέθοδος πηγαίνει σε έναν άπειρο βρόχο και η τελευταία συντεταγμένη που βρέθηκε μπορεί να θεωρηθεί το αποτέλεσμα αυτής της αναζήτησης. Ωστόσο, η ρύθμιση στόχου της αναζήτησης για το συνολικό ελάχιστο στην περιοχή ενδέχεται να μην επιτευχθεί λόγω του γεγονότος ότι διακόψαμε την αναζήτηση για το ελάχιστο (βλ. Εικόνα 1).

Εικόνα 1 - Ακύρωση καθόδου συντεταγμένων

Η μελέτη αυτής της μεθόδου έδειξε ότι κάθε ευρεθέν υπολογισμένο σημείο στο διάστημα είναι ένα παγκόσμιο ελάχιστο σημείο δεδομένη λειτουργία, και η συνάρτηση z = f(x1, x2,…, xn) είναι κυρτή και διαφοροποιήσιμη.
Από αυτό μπορούμε να συμπεράνουμε ότι η συνάρτηση z = f(x1, x2,…, xn) είναι κυρτή και διαφοροποιήσιμη στο χώρο, και κάθε οριακό σημείο που βρέθηκε στην ακολουθία M0(x10, x20,…, xn0) θα είναι ένα συνολικό ελάχιστο σημείο (βλ. Εικ. Εικόνα 2) αυτής της συνάρτησης με τη μέθοδο της συντεταγμένης κατάβασης.

Σχήμα 2 - Τοπικά ελάχιστα σημεία στον άξονα συντεταγμένων

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

Η πρόοδος της μεθόδου καθόδου συντεταγμένων γίνεται σύμφωνα με τον αλγόριθμο που περιγράφεται στο μπλοκ διάγραμμα (βλ. Εικόνα 3). Επαναλήψεις εκτέλεσης αυτής της μεθόδου:
Αρχικά, πρέπει να εισαχθούν αρκετές παράμετροι: η ακρίβεια Epsilon, η οποία πρέπει να είναι αυστηρά θετική, το σημείο εκκίνησης x1 από το οποίο θα ξεκινήσουμε να εκτελούμε τον αλγόριθμό μας και θα ορίσουμε το Lambda j;
Το επόμενο βήμα είναι να πάρουμε το πρώτο σημείο εκκίνησης x1, μετά από το οποίο λύνεται η συνηθισμένη μονοδιάστατη εξίσωση με μία μεταβλητή και ο τύπος για την εύρεση του ελάχιστου θα είναι, όπου k = 1, j=1:

Τώρα, αφού υπολογίσετε το ακραίο σημείο, πρέπει να ελέγξετε τον αριθμό των ορισμάτων στη συνάρτηση και εάν το j είναι μικρότερο από n, τότε πρέπει να επαναλάβετε το προηγούμενο βήμα και να επαναπροσδιορίσετε το όρισμα j = j + 1. Σε όλες τις άλλες περιπτώσεις, πηγαίνετε στο επόμενο βήμα.
Τώρα είναι απαραίτητο να επαναπροσδιορίσουμε τη μεταβλητή x σύμφωνα με τον τύπο x (k + 1) = y (n + 1) και να προσπαθήσουμε να εκτελέσουμε τη σύγκλιση της συνάρτησης στη δεδομένη ακρίβεια σύμφωνα με την έκφραση:

Τώρα, η εύρεση του ακραίου σημείου εξαρτάται από αυτήν την έκφραση. Εάν αυτή η έκφραση είναι αληθής, τότε ο υπολογισμός του ακραίου σημείου μειώνεται σε x*= xk + 1. Αλλά συχνά είναι απαραίτητο να εκτελούνται πρόσθετες επαναλήψεις ανάλογα με την ακρίβεια, οπότε οι τιμές των ορισμάτων θα επανακαθορίζονται y(1 ) = x(k + 1), και οι τιμές των δεικτών j =1, k = k + 1.

Εικόνα 3 - Μπλοκ διάγραμμα της μεθόδου καθόδου συντεταγμένων

Ως αποτέλεσμα, έχουμε έναν εξαιρετικό και πολυλειτουργικό αλγόριθμο βελτιστοποίησης πολλαπλών μεταβλητών που μπορεί να χωρίσει δύσκολη εργασία, σε πολλά διαδοχικά επαναληπτικά μονοδιάστατα. Ναι, αυτή η μέθοδος είναι αρκετά απλή στην εφαρμογή και έχει εύκολος ορισμόςσημεία στο χώρο, γιατί αυτή η μέθοδος εγγυάται τη σύγκλιση σε τοπικό σημείοελάχιστο. Αλλά ακόμη και με τέτοια σημαντικά πλεονεκτήματα, η μέθοδος είναι σε θέση να μπει σε ατελείωτους βρόχους λόγω του γεγονότος ότι μπορεί να πέσει σε ένα είδος χαράδρας.
Υπάρχουν ρεματιές στις οποίες υπάρχουν καταθλίψεις. Ο αλγόριθμος, έχοντας πέσει σε μια από αυτές τις γούρνες, δεν μπορεί πλέον να βγει έξω και θα βρει το ελάχιστο σημείο ήδη εκεί. Τον ίδιο τρόπο μεγάλος αριθμόςΟι διαδοχικές χρήσεις της ίδιας μεθόδου μονοδιάστατης βελτιστοποίησης μπορούν να επηρεάσουν σε μεγάλο βαθμό τις αδύναμες Υπολογιστές. Όχι μόνο η σύγκλιση σε αυτή τη συνάρτηση είναι πολύ αργή, καθώς είναι απαραίτητο να υπολογιστούν όλες οι μεταβλητές και συχνά η υψηλή καθορισμένη ακρίβεια αυξάνει τον χρόνο επίλυσης του προβλήματος κατά πολλές φορές, αλλά το κύριο μειονέκτημα αυτόν τον αλγόριθμο- περιορισμένη δυνατότητα εφαρμογής.
Διεξάγοντας μελέτη διαφόρων αλγορίθμων για την επίλυση προβλημάτων βελτιστοποίησης, θα πρέπει να σημειωθεί ότι τεράστιο ρόλοπαίζει την ποιότητα των αλγορίθμων δεδομένων. Επίσης, μην ξεχνάτε αυτά σημαντικά χαρακτηριστικά, όπως ο χρόνος και η σταθερότητα της εκτέλεσης, η ικανότητα εύρεσης καλύτερες αξίες, ελαχιστοποίηση ή μεγιστοποίηση της αντικειμενικής συνάρτησης, ευκολία υλοποίησης επίλυσης πρακτικών προβλημάτων. Η μέθοδος καθόδου συντεταγμένων είναι εύκολη στη χρήση, αλλά σε προβλήματα βελτιστοποίησης πολλαπλών μεταβλητών, τις περισσότερες φορές, χρειάζεται να εκτελέσετε σύνθετους υπολογισμούς αντί για διαμερίσματα. ολόκληρο έργογια δευτερεύουσες εργασίες.

Μέθοδος Nelder-Mead

Αξίζει να σημειωθεί η δημοτικότητα αυτού του αλγορίθμου μεταξύ των ερευνητών πολυδιάστατων μεθόδων βελτιστοποίησης. Η μέθοδος Nelder-Mead είναι μια από τις λίγες μεθόδους που βασίζεται στην έννοια του διαδοχικού μετασχηματισμού ενός παραμορφώσιμου απλού γύρω από ένα ακραίο σημείο και δεν χρησιμοποιεί τον αλγόριθμο κίνησης προς το παγκόσμιο ελάχιστο.
Αυτό το απλό είναι κανονικό και αναπαρίσταται ως πολύεδρο με ισαπέχουσες κορυφές του απλού σε Χώρος Ν-διάστασης. Σε διαφορετικούς χώρους, το simplex αντιστοιχεί σε ένα R2-ισόπλευρο τρίγωνο και στο R3 ένα κανονικό τετράεδρο.
Όπως αναφέρθηκε παραπάνω, ο αλγόριθμος είναι μια ανάπτυξη της μεθόδου Spendley, Hoekst και Himsworth, αλλά, σε αντίθεση με την τελευταία, επιτρέπει τη χρήση λανθασμένων απλοποιήσεων. Τις περισσότερες φορές, ένα simplex σημαίνει κυρτό πολύεδρομε τον αριθμό των κορυφών N+1, όπου N είναι ο αριθμός των παραμέτρων του μοντέλου στον n-διάστατο χώρο.
Για να ξεκινήσετε να χρησιμοποιείτε αυτήν τη μέθοδο, πρέπει να προσδιορίσετε τη βασική κορυφή όλων των διαθέσιμων συνόλων συντεταγμένων χρησιμοποιώντας την έκφραση:

Το πιο αξιοσημείωτο σε αυτή τη μέθοδο είναι ότι το simplex έχει την ικανότητα να εκτελεί ανεξάρτητα ορισμένες λειτουργίες:
Αντανάκλαση μέσω του κέντρου βάρους, ανάκλαση με συμπίεση ή τέντωμα.
τέντωμα?
Συμπίεση.
Η προτίμηση μεταξύ αυτών των ιδιοτήτων δίνεται στον προβληματισμό, αφού αυτή η παράμετρος είναι η πιο προαιρετική - λειτουργική. Από οποιαδήποτε επιλεγμένη κορυφή είναι δυνατό να γίνει μια αντανάκλαση σε σχέση με το κέντρο βάρους του απλού με την έκφραση:.

Όπου xc είναι το κέντρο βάρους (βλ. Εικόνα 1).

Εικόνα 1 - Αντανάκλαση μέσω του κέντρου βάρους

Το επόμενο βήμα είναι να υπολογιστούν τα ορίσματα της αντικειμενικής συνάρτησης σε όλες τις κορυφές του ανακλώμενου απλού. Μετά από αυτό, θα πάρουμε πλήρη ενημέρωσησχετικά με το πώς θα συμπεριφέρεται το simplex στο χώρο και επομένως πληροφορίες σχετικά με τη συμπεριφορά της συνάρτησης.
Για να αναζητήσετε το ελάχιστο ή μέγιστο σημείο της αντικειμενικής συνάρτησης χρησιμοποιώντας μεθόδους που χρησιμοποιούν απλές, πρέπει να ακολουθήσετε την ακόλουθη σειρά:
Σε κάθε βήμα, δημιουργείται ένα απλό, σε κάθε σημείο του οποίου, είναι απαραίτητο να υπολογιστούν όλες οι κορυφές του και στη συνέχεια να ταξινομηθούν τα αποτελέσματα σε αύξουσα σειρά.
Το επόμενο βήμα είναι ο προβληματισμός. Είναι απαραίτητο να κάνουμε μια προσπάθεια να λάβουμε τις τιμές του νέου simplex και με τον στοχασμό, μπορούμε να απαλλαγούμε από ανεπιθύμητες τιμές που προσπαθούν να μετακινήσουν το simplex όχι προς το παγκόσμιο ελάχιστο.
Για να λάβουμε τις τιμές του νέου simplex, από τα ληφθέντα ταξινομημένα αποτελέσματα, παίρνουμε δύο κορυφές με τις χειρότερες αξίες. Είναι πιθανό ότι δεν θα είναι δυνατή η άμεση επιλογή των κατάλληλων τιμών, τότε θα πρέπει να επιστρέψετε στο πρώτο βήμα και να συμπιέσετε το simplex στο σημείο με τις περισσότερες η μικρότερη τιμή;
Το τέλος της αναζήτησης για ένα ακραίο σημείο είναι το κέντρο βάρους, υπό την προϋπόθεση ότι η τιμή της διαφοράς μεταξύ των συναρτήσεων έχει τις μικρότερες τιμές στα σημεία του απλού.

Ο αλγόριθμος Nelder-Mead χρησιμοποιεί επίσης αυτές τις συναρτήσεις simplex σύμφωνα με τους ακόλουθους τύπους:

Η συνάρτηση ανάκλασης μέσω του κέντρου βάρους του απλού υπολογίζεται από παρακάτω έκφραση:

Αυτή η ανάκλαση πραγματοποιείται αυστηρά προς το ακραίο σημείο και μόνο μέσω του κέντρου βάρους (βλ. Εικόνα 2).

Σχήμα 2 - Η ανάκλαση του απλού γίνεται μέσω του κέντρου βάρους

Η συνάρτηση συμπίεσης μέσα στο simplex υπολογίζεται από την ακόλουθη έκφραση:

Για να πραγματοποιηθεί συμπίεση, είναι απαραίτητο να προσδιοριστεί το σημείο με τη μικρότερη τιμή (βλ. Εικόνα 3).

Εικόνα 3 - Το simplex συμπιέζεται στο μικρότερο όρισμα.

Η συνάρτηση ανάκλασης συστολής simplex υπολογίζεται από την ακόλουθη έκφραση:

Προκειμένου να πραγματοποιηθεί ανάκλαση με συμπίεση (βλ. Εικόνα 4), είναι απαραίτητο να θυμάστε το έργο δύο ξεχωριστών λειτουργιών - αυτή είναι η ανάκλαση μέσω του κέντρου βάρους και η συμπίεση του απλού στη μικρότερη τιμή.

Εικόνα 4 - Ανάκλαση με συμπίεση

Η συνάρτηση ανάκλασης απλού τεντώματος (βλ. Εικόνα 5) εμφανίζεται χρησιμοποιώντας δύο συναρτήσεις - ανάκλαση μέσω του κέντρου βάρους και διάταση μέσω της μεγαλύτερης τιμής.

Εικόνα 5 - Αντανάκλαση με τέντωμα.

Για να δείξετε τη λειτουργία της μεθόδου Nelder-Mead, είναι απαραίτητο να ανατρέξετε στο μπλοκ διάγραμμα του αλγορίθμου (βλ. Εικόνα 6).
Πρώτα απ 'όλα, όπως και στα προηγούμενα παραδείγματα, είναι απαραίτητο να ορίσετε την παράμετρο παραμόρφωσης ε, η οποία πρέπει να είναι αυστηρά Πάνω απο το μηδέν, καθώς και να ορίσετε τις απαραίτητες παραμέτρους για τον υπολογισμό των α, β και α. Αυτό θα χρειαστεί για τον υπολογισμό της συνάρτησης f(x0), καθώς και για την κατασκευή του ίδιου του simplex.

Εικόνα 6 - Το πρώτο μέρος της μεθόδου Nelder - Mead.

Μετά την κατασκευή του simplex, είναι απαραίτητο να υπολογιστούν όλες οι τιμές της αντικειμενικής συνάρτησης. Όπως περιγράφηκε παραπάνω σχετικά με την αναζήτηση ενός άκρου χρησιμοποιώντας ένα απλό, είναι απαραίτητο να υπολογιστεί η συνάρτηση απλού f(x) σε όλα τα σημεία της. Στη συνέχεια, ταξινομούμε πού θα είναι το σημείο βάσης:

Τώρα που έχει υπολογιστεί το βασικό σημείο, καθώς και όλα τα άλλα ταξινομημένα στη λίστα, ελέγχουμε τη συνθήκη προσβασιμότητας για την ακρίβεια που καθορίσαμε προηγουμένως:

Μόλις αυτή η συνθήκη γίνει αληθής, τότε θα ληφθεί υπόψη το σημείο x(0) του απλού επιθυμητό σημείοακραίο. Διαφορετικά, πηγαίνουμε στο επόμενο βήμα, όπου πρέπει να προσδιορίσουμε τη νέα τιμή του κέντρου βάρους χρησιμοποιώντας τον τύπο:

Εάν πληρούται αυτή η συνθήκη, τότε το σημείο x(0) θα είναι το ελάχιστο σημείο, διαφορετικά, πρέπει να μεταβείτε στο επόμενο βήμα στο οποίο πρέπει να αναζητήσετε το μικρότερο όρισμα συνάρτησης:

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

Εικόνα 7 - Το δεύτερο μέρος της μεθόδου Nelder - Mead.

Η τιμή που υπολογίζεται από την προηγούμενη συνάρτηση πρέπει να αντικατασταθεί στη συνθήκη fmin< f(xN). При истинном выполнении данного условия, точка x(N) будет являться минимальной из группы тех, которые хранятся в отсортированном списке и нужно вернуться к шагу, где мы рассчитывали центр тяжести, в противном случае, производим сжатие симплекса в 2 раза и возвращаемся к самому началу с новым набором точек.
Μελέτες αυτού του αλγορίθμου δείχνουν ότι οι μέθοδοι με ακανόνιστες απλοποιήσεις (βλ. Εικόνα 8) εξακολουθούν να είναι σχετικά ανεπαρκώς μελετημένες, αλλά αυτό δεν τις εμποδίζει να αντιμετωπίσουν τέλεια τις εργασίες τους.
Οι βαθύτερες δοκιμές δείχνουν ότι πειραματικά είναι δυνατό να επιλέξετε τις παραμέτρους των συναρτήσεων τάνυσης, συμπίεσης και ανάκλασης που είναι πιο κατάλληλες για το πρόβλημα, αλλά μπορείτε να χρησιμοποιήσετε τις γενικά αποδεκτές παραμέτρους αυτών των συναρτήσεων α = 1/2, β = 2, γ = 2 ή α = 1/4, β = 5/2, γ = 2. Επομένως, προτού απορρίψετε αυτήν τη μέθοδο για την επίλυση του προβλήματος, πρέπει να καταλάβετε ότι για κάθε νέα αναζήτηση για ένα ακρότατο άνευ όρων, πρέπει να παρακολουθείτε στενά το συμπεριφορά του simplex κατά τη λειτουργία του και σημ μη τυποποιημένες λύσειςμέθοδος.

Εικόνα 8 - Η διαδικασία εύρεσης του ελάχιστου.

Οι στατιστικές έχουν δείξει ότι ένα από τα πιο κοινά προβλήματα στη λειτουργία αυτού του αλγορίθμου είναι ο εκφυλισμός του παραμορφώσιμου απλού. Αυτό συμβαίνει όταν κάθε φορά που πολλές κορυφές του απλού πέφτουν σε ένα χώρο, η διάσταση του οποίου δεν ικανοποιεί την εργασία.
Έτσι, η διάσταση κατά τη λειτουργία και η δεδομένη διάσταση ρίχνουν πολλές κορυφές του απλού σε μια ευθεία γραμμή, εκκινώντας τη μέθοδο σε έναν άπειρο βρόχο. Ο αλγόριθμος σε αυτήν την τροποποίηση δεν είναι ακόμη εξοπλισμένος με έναν τρόπο για να βγείτε από αυτήν την κατάσταση και να μετακινήσετε μια κορυφή στο πλάι, επομένως πρέπει να δημιουργήσετε ένα νέο simplex με νέες παραμέτρους, ώστε αυτό να μην συμβεί στο μέλλον.
Ένα άλλο χαρακτηριστικό αυτής της μεθόδου είναι ότι δεν λειτουργεί σωστά με έξι ή περισσότερες κορυφές του απλού. Ωστόσο, τροποποιώντας αυτήν τη μέθοδο, μπορείτε να απαλλαγείτε από αυτό το πρόβλημα και να μην χάσετε καν την ταχύτητα εκτέλεσης, αλλά η τιμή της εκχωρημένης μνήμης θα αυξηθεί αισθητά. Αυτή η μέθοδοςμπορεί να θεωρηθεί κυκλική αφού βασίζεται εξ ολοκλήρου σε κύκλους, γι' αυτό και γίνεται αντιληπτό λανθασμένη εργασίαστο σε μεγάλους αριθμούςκορυφές.
Ο αλγόριθμος Nelder-Mead μπορεί δικαίως να θεωρηθεί ένας από τους βέλτιστες πρακτικέςΗ εύρεση ενός ακραίου σημείου με χρήση ενός απλού και είναι ιδανικό για τη χρήση του σε διάφορα είδη μηχανικών και οικονομικών προβλημάτων. Ακόμη και παρά την κυκλικότητα, χρησιμοποιεί πολύ μικρή ποσότητα μνήμης σε σύγκριση με την ίδια μέθοδο καθόδου συντεταγμένων και για να βρεθεί το ίδιο το άκρο, απαιτείται να υπολογιστούν μόνο οι τιμές του κέντρου βάρους και της συνάρτησης. Ένας μικρός αλλά επαρκής αριθμός σύνθετων παραμέτρων κάνει αυτή τη μέθοδο να χρησιμοποιείται ευρέως σε πολύπλοκα μαθηματικά και πραγματικά προβλήματα παραγωγής.
Οι απλοί αλγόριθμοι είναι η άκρη, τους ορίζοντες των οποίων δεν θα ανοίξουμε σύντομα, αλλά ήδη τώρα απλοποιούν πολύ τη ζωή μας με το οπτικό τους στοιχείο.

ΥΣΤΕΡΟΓΡΑΦΟ. Το κείμενο είναι εξ ολοκλήρου δικό μου. Ελπίζω κάποιος αυτή η πληροφορίαθα είναι χρήσιμο.

Όπως έχουμε ήδη σημειώσει, το πρόβλημα βελτιστοποίησης είναι το πρόβλημα της εύρεσης τέτοιων τιμών των παραγόντων Χ 1 = Χ 1* , Χ 2 = Χ 2* , …, Χκ = Χκ * , για την οποία η συνάρτηση απόκρισης ( στο) φτάνει σε ακραία τιμή στο= ext (βέλτιστο).

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

Εξετάστε την ουσία της μεθόδου gradient χρησιμοποιώντας το παράδειγμα μιας συνάρτησης απόκρισης δύο παραγόντων y=φά(Χ 1 , Χ 2 ). Στο σχ. 4.3 στις καμπύλες του χώρου συντελεστών εμφανίζονται ίσες αξίεςσυναρτήσεις απόκρισης (καμπύλες επιπέδου). Σημείο με συντεταγμένες Χ 1 *, Χ 2 * αντιστοιχεί στην ακραία τιμή της συνάρτησης απόκρισης στοεσωτ.

Αν επιλέξουμε οποιοδήποτε σημείο του χώρου παραγόντων ως αρχικό ( Χ 1 0 , Χ 2 0), τότε ο συντομότερος δρόμοςστην κορυφή της συνάρτησης απόκρισης από αυτό το σημείο είναι η διαδρομή κατά μήκος της καμπύλης, η εφαπτομένη της οποίας σε κάθε σημείο συμπίπτει με την κανονική προς την καμπύλη επιπέδου, δηλ. αυτή είναι η διαδρομή προς την κατεύθυνση της κλίσης της συνάρτησης απόκρισης.

Διαβάθμιση συνεχούς συνάρτησης μονής τιμής y=φά(Χ 1 , Χ 2) είναι ένα διάνυσμα που καθορίζεται από την κατεύθυνση της κλίσης με συντεταγμένες:

όπου Εγώ,ιείναι μοναδιαία διανύσματα προς την κατεύθυνση των αξόνων συντεταγμένων Χ 1 και Χ 2. Μερικές παράγωγοι και χαρακτηρίζουν την κατεύθυνση του διανύσματος.

Αφού δεν γνωρίζουμε το είδος της εξάρτησης y=φά(Χ 1 , Χ 2), δεν μπορούμε να βρούμε τις μερικές παραγώγους και να προσδιορίσουμε την πραγματική κατεύθυνση της κλίσης.

Σύμφωνα με τη μέθοδο της κλίσης, σε κάποιο μέρος του χώρου παραγόντων, επιλέγεται το σημείο εκκίνησης (αρχικά επίπεδα). Χ 1 0 , Χείκοσι . Σε σχέση με αυτά τα αρχικά επίπεδα, κατασκευάζεται ένα συμμετρικό σχέδιο δύο επιπέδων του πειράματος. Επιπλέον, το διάστημα διακύμανσης επιλέγεται τόσο μικρό ώστε το γραμμικό μοντέλο να είναι επαρκές. Είναι γνωστό ότι οποιαδήποτε καμπύλη σε μια αρκετά μικρή περιοχή μπορεί να προσεγγιστεί με ένα γραμμικό μοντέλο.

Μετά την κατασκευή ενός συμμετρικού σχεδίου δύο επιπέδων, το πρόβλημα της παρεμβολής λύνεται, δηλ. υπό κατασκευή γραμμικό μοντέλο:

και ελέγξτε την καταλληλότητά του.

Εάν το γραμμικό μοντέλο αποδείχθηκε επαρκές για το επιλεγμένο διάστημα μεταβολής, τότε μπορεί να προσδιοριστεί η κατεύθυνση της κλίσης:

Έτσι, η κατεύθυνση της κλίσης της συνάρτησης απόκρισης καθορίζεται από τις τιμές των συντελεστών παλινδρόμησης. Αυτό σημαίνει ότι θα κινηθούμε προς την κατεύθυνση της κλίσης, εάν από ένα σημείο με συντεταγμένες ( ) μεταβείτε στο σημείο με συντεταγμένες:

όπου Μ-ένας θετικός αριθμός που καθορίζει το μέγεθος του βήματος προς την κατεύθυνση της κλίσης.

Επειδή η Χ 1 0 = 0 και Χ 2 0 = 0, λοιπόν .

Καθορίζοντας την κατεύθυνση της κλίσης () και επιλέγοντας το μέγεθος του βήματος Μ, πραγματοποιούμε εμπειρία σε αρχικό επίπεδο Χ 1 0 , Χ 2 0 .

Στη συνέχεια κάνουμε ένα βήμα προς την κατεύθυνση της κλίσης, δηλ. πραγματοποιήστε το πείραμα σε σημείο με συντεταγμένες . Εάν η τιμή της συνάρτησης απόκρισης έχει αυξηθεί σε σύγκριση με την τιμή της στο αρχικό επίπεδο, κάνουμε ένα άλλο βήμα προς την κατεύθυνση της κλίσης, δηλ. πραγματοποιούμε το πείραμα σε ένα σημείο με συντεταγμένες:

Συνεχίζουμε να κινούμαστε κατά μήκος της κλίσης μέχρι να αρχίσει να μειώνεται η συνάρτηση απόκρισης. Στο σχ. 4.3 κίνηση κατά μήκος της κλίσης αντιστοιχεί σε μια ευθεία γραμμή που βγαίνει από το σημείο ( Χ 1 0 , Χείκοσι). Σταδιακά αποκλίνει από την πραγματική κατεύθυνση της κλίσης, που φαίνεται από τη διακεκομμένη γραμμή, λόγω της μη γραμμικότητας της συνάρτησης απόκρισης.

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

Κατασκευή ενός νέου γραμμικού μοντέλου , φέρει εις πέρας ανάλυση παλινδρόμησης. Αν, ταυτόχρονα, ο έλεγχος της σημασίας των παραγόντων δείξει ότι τουλάχιστον ένας συντελεστής

ficient , που σημαίνει ότι η περιοχή του άκρου της συνάρτησης απόκρισης (η περιοχή του βέλτιστου) δεν έχει ακόμη επιτευχθεί. Προσδιορίζεται μια νέα κατεύθυνση της κλίσης και αρχίζει η κίνηση προς τη βέλτιστη περιοχή.

Η βελτίωση της κατεύθυνσης της κλίσης και η κίνηση κατά μήκος της κλίσης συνεχίζονται έως ότου, στη διαδικασία επίλυσης του επόμενου προβλήματος παρεμβολής, ο έλεγχος της σημασίας των παραγόντων δείχνει ότι όλοι οι παράγοντες είναι ασήμαντοι, δηλ. όλα . Αυτό σημαίνει ότι έχει επιτευχθεί η βέλτιστη περιοχή. Επί της απόφασης αυτής πρόβλημα βελτιστοποίησηςσταματήστε και πάρτε την εμπειρία με τη μέγιστη τιμή της συνάρτησης απόκρισης ως τη βέλτιστη.

ΣΤΟ γενική εικόναη ακολουθία των ενεργειών που απαιτούνται για την επίλυση του προβλήματος βελτιστοποίησης με τη μέθοδο της κλίσης μπορεί να αναπαρασταθεί με τη μορφή ενός διαγράμματος ροής (Εικ. 4.4).

1) αρχικά επίπεδα παραγόντων ( Χι 0) θα πρέπει να επιλέγεται όσο το δυνατόν πλησιέστερα στο βέλτιστο σημείο, εάν υπάρχουν κάποιες a priori πληροφορίες για τη θέση του.

2) διαστήματα μεταβολής (Δ Χι) θα πρέπει να επιλέγεται έτσι ώστε το γραμμικό μοντέλο να είναι πιθανό να είναι επαρκές. Κάτω περίγραμμα Δ ΧιΣτην περίπτωση αυτή, είναι η ελάχιστη τιμή του διαστήματος μεταβολής στο οποίο η συνάρτηση απόκρισης παραμένει σημαντική.

3) τιμή βήματος ( t) όταν κινούνται κατά μήκος της κλίσης, επιλέγονται με τέτοιο τρόπο ώστε το μεγαλύτερο από τα προϊόντα να μην υπερβαίνει τη διαφορά μεταξύ των ανώτερων και κατώτερων επιπέδων των παραγόντων στην κανονικοποιημένη μορφή

.

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

Μέθοδος Gauss-Seidel

Η μέθοδος συνίσταται στην εναλλακτική εύρεση μερικών ακρότατων της αντικειμενικής συνάρτησης για κάθε παράγοντα. Ταυτόχρονα, σε κάθε στάδιο, σταθεροποιούνται οι (k-1) παράγοντες και μεταβάλλεται μόνο ένας i-ος παράγοντας

Διαδικασία υπολογισμού: στην τοπική περιοχή του χώρου παραγόντων, βάσει προκαταρκτικών πειραμάτων, επιλέγεται ένα σημείο που αντιστοιχεί σε καλύτερο αποτέλεσμαδιαδικασία, και από εκεί αρχίζουν να κινούνται προς το βέλτιστο. Το βήμα κίνησης για κάθε παράγοντα ορίζεται από τον ερευνητή. Πρώτα, όλοι οι παράγοντες σταθεροποιούνται στο ίδιο επίπεδο και ένας παράγοντας αλλάζει μέχρι να υπάρξει αύξηση (μείωση) στη συνάρτηση απόκρισης (Y), μετά αλλάζει ο άλλος παράγοντας ενώ οι άλλοι σταθεροποιούνται κ.λπ. επιθυμητό αποτέλεσμα(Υ). Το κύριο πράγμα είναι να επιλέξετε το σωστό βήμα για κάθε παράγοντα.

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

Αυτές οι μέθοδοι παρέχουν κίνηση στο βέλτιστο κατά μήκος μιας ευθείας γραμμής κάθετης στις γραμμές ίσης απόκρισης, δηλαδή προς την κατεύθυνση της κλίσης της συνάρτησης απόκρισης.

Οι μέθοδοι κλίσης έχουν πολλές ποικιλίες που διαφέρουν ως προς τους κανόνες επιλογής των βημάτων παραλλαγής και των βημάτων εργασίας σε κάθε στάδιο της κίνησης προς τα άκρα.

Η ουσία όλων των μεθόδων είναι η εξής: αρχικά, με βάση προκαταρκτικά πειράματα, σημείο βάσης. Στη συνέχεια, σε κάθε στάδιο, οργανώνονται δοκιμαστικά πειράματα γύρω από το επόμενο σημείο βάσης, τα αποτελέσματα των οποίων αξιολογούν τη νέα κατεύθυνση της κλίσης, μετά την οποία γίνεται ένα βήμα εργασίας προς αυτήν την κατεύθυνση.

Η μέθοδος κλίσης (κανονική) πραγματοποιείται σύμφωνα με το ακόλουθο σχήμα:

α) επιλέξτε ένα σημείο βάσης.

β) επιλέξτε βήματα κίνησης για κάθε παράγοντα.

γ) καθορίζει τις συντεταγμένες των σημείων δοκιμής.

δ) διεξαγωγή πειραμάτων σε σημεία δοκιμής. Ως αποτέλεσμα, οι τιμές της παραμέτρου βελτιστοποίησης (Y) λαμβάνονται σε κάθε σημείο.

ε) με βάση τα αποτελέσματα των πειραμάτων, υπολογίζονται οι εκτιμήσεις των συνιστωσών του διανύσματος βαθμίδωσης στο σημείο Μ για κάθε i-ο παράγοντα:

όπου H i είναι το βήμα της κίνησης κατά μήκος του X i .

X i – συντεταγμένες του προηγούμενου σημείου εργασίας.

ζ) οι συντεταγμένες αυτού του σημείου εργασίας λαμβάνονται ως νέο σημείο βάσης, γύρω από το οποίο διεξάγονται πειράματα σε δοκιμαστικά σημεία. Η κλίση υπολογίζεται και ούτω καθεξής, μέχρι να επιτευχθεί η επιθυμητή παράμετρος βελτιστοποίησης (Y). Διόρθωση της κατεύθυνσης κίνησης γίνεται μετά από κάθε βήμα.

Πλεονεκτήματα της μεθόδου: απλότητα, μεγαλύτερη ταχύτητα κίνησης στο βέλτιστο.

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

α) Μέθοδος απότομης ανάβασης (Box-Wilson).

β) Λήψη αποφάσεων μετά από απότομη ανάβαση.

σε) Μέθοδος Simplexβελτιστοποίηση.

δ) Πλεονεκτήματα και μειονεκτήματα των μεθόδων.

5.7.3 Μέθοδος απότομης ανάβασης (Box-Wilson)

Αυτή η μέθοδος είναι μια σύνθεση τα καλύτερα χαρακτηριστικάοι μέθοδοι κλίσης, η μέθοδος Gauss-Seidel και οι μέθοδοι PFE και DFE - ως μέσο απόκτησης ενός μαθηματικού μοντέλου της διαδικασίας. Η επίλυση του προβλήματος βελτιστοποίησης με αυτή τη μέθοδο εκτελείται έτσι ώστε η κίνηση βήματος να πραγματοποιείται προς την κατεύθυνση της ταχύτερης αύξησης (μείωσης) της παραμέτρου βελτιστοποίησης. Η διόρθωση της κατεύθυνσης της κίνησης (σε αντίθεση με τις μεθόδους κλίσης) γίνεται όχι μετά από κάθε βήμα, αλλά με την επίτευξη ενός συγκεκριμένου άκρου της αντικειμενικής συνάρτησης. Περαιτέρω, στα σημεία ενός μερικού άκρου, δημιουργείται ένα νέο παραγοντικό πείραμα, ένα νέο μαθηματικό μοντέλοκαι πάλι η απότομη ανάβαση επαναλαμβάνεται μέχρι να επιτευχθεί το παγκόσμιο βέλτιστο. Η κίνηση κατά μήκος της κλίσης ξεκινά από το σημείο μηδέν (το κέντρο του σχεδίου).

Η μέθοδος απότομης ανάβασης περιλαμβάνει κίνηση προς το βέλτιστο κατά μήκος μιας κλίσης.

Όπου i,j,k είναι μοναδιαία διανύσματα προς την κατεύθυνση των αντίστοιχων αξόνων συντεταγμένων.

Διαδικασία υπολογισμού.

Τα αρχικά δεδομένα είναι ένα μαθηματικό μοντέλο της διαδικασίας που λαμβάνεται με οποιαδήποτε μέθοδο (PFE, DFE, κ.λπ.).

Οι υπολογισμοί γίνονται με την ακόλουθη σειρά:

α) είναι καλύτερο να μεταφράσετε την εξίσωση παλινδρόμησης σε φυσική μορφή χρησιμοποιώντας τους τύπους κωδικοποίησης μεταβλητών:

όπου Χ i-κωδικοποιημένη τιμή της μεταβλητής x i ;

X i - φυσική τιμή της μεταβλητής x i ;

X i C - το κεντρικό επίπεδο του παράγοντα στη φυσική του μορφή.

l i - το διάστημα μεταβολής του παράγοντα x i σε φυσική μορφή.

β) να υπολογίσετε τα βήματα της κίνησης στο βέλτιστο για κάθε παράγοντα.

Για να γίνει αυτό, υπολογίστε τα γινόμενα των συντελεστών της εξίσωσης παλινδρόμησης σε φυσική μορφή με τα αντίστοιχα διαστήματα διακύμανσης

B i *.l I ,

Στη συνέχεια, από τα προϊόντα που προκύπτουν, επιλέγεται το μέγιστο modulo και ο συντελεστής που αντιστοιχεί σε αυτό το γινόμενο λαμβάνεται ως βασικός παράγοντας (B a l a). Για τον βασικό παράγοντα, θα πρέπει να ορίσετε το βήμα κίνησης, το οποίο συνιστάται να ρυθμιστεί μικρότερο ή ίσο με το διάστημαδιακύμανση του συντελεστή βάσης

Το πρόσημο του βήματος κίνησης l a ’ πρέπει να ταιριάζει με το πρόσημο του συντελεστή της εξίσωσης παλινδρόμησης που αντιστοιχεί στον βασικό παράγοντα (Β α). Η τιμή των βημάτων για άλλους παράγοντες υπολογίζεται σε αναλογία με τη βάση σύμφωνα με τον τύπο:

Τα πρόσημα των βημάτων κίνησης πρέπει επίσης να ταιριάζουν με τα πρόσημα των αντίστοιχων συντελεστών της εξίσωσης παλινδρόμησης.

γ) η συνάρτηση απόκρισης υπολογίζεται στο κέντρο του σχεδίου, δηλαδή με τις τιμές των παραγόντων ίσες με το κεντρικό επίπεδο των παραγόντων, αφού η κίνηση προς το βέλτιστο ξεκινά από το κέντρο του σχεδίου.

Στη συνέχεια, υπολογίζεται η παράμετρος βελτιστοποίησης, αυξάνοντας τις τιμές των παραγόντων κατά την τιμή του αντίστοιχου βήματος κίνησης, εάν θέλετε να λάβετε το Y max. Διαφορετικά, εάν είναι απαραίτητο να ληφθεί το Y min, οι τιμές των παραγόντων μειώνονται κατά την τιμή του βήματος κίνησης.

Η διαδικασία επαναλαμβάνεται, αυξάνοντας διαδοχικά τον αριθμό των βημάτων μέχρι να επιτευχθεί η επιθυμητή τιμή της παραμέτρου βελτιστοποίησης (Y). Καθένας από τους παράγοντες μετά σολτα βήματα θα έχουν σημασία:

Εάν Y®max X i \u003d X i c + gl i ` ’

εάν Y® min . X i \u003d X i c -gl i `.(5.36)