kReese.net

Η Karush-Kuhn-Tucker (KKT) συνθήκες, μερικές φορές αναφέρεται ως ο Kuhn-Tucker συνθήκες, είναι οι συνθήκες που μια μη γραμμική πρόβλημα προγραμματισμού πρέπει να πληρούν για να είναι η βέλτιστη. Η KKT συνθήκες επεκτείνει τη μέθοδο της Lagrangian πολλαπλασιαστές, επιτρέποντας για περιορισμούς ανισότητας, σε αντίθεση με τους πολλαπλασιαστές Lagrange που επιτρέπει μόνο περιορισμούς ισότητας.

Ας εξετάσουμε μια μη γραμμική πρόβλημα βελτιστοποίησης:

Ελαχιστοποίηση $f(x)$
υπόκεινται σε: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

Θα αφήσουμε $x^{*}$ αντιπροσωπεύουν ένα ελάχιστο σχετικό σημείο για το πρόβλημά μας, το οποίο πληροί επίσης κάποια προσόντα περιορισμό. Με αυτό το, τότε μπορούμε να υποθέσουμε ότι για κάθε στοιχείο που υπάρχει ένα διάνυσμα $\lambda_j \left ( j = 1, \ldots, l \right )$ , όπου l αντιπροσωπεύει τον αριθμό των περιορισμών ισότητας, και $\mu_i\left ( i = 1, \ldots, m \right )$ , όπου m αντιπροσωπεύει τον αριθμό των περιορισμών ανισότητας. Αυτές οι σταθερές, $\lambda_j$ και $\mu_i$ , ονομάζονται KKT πολλαπλασιαστές.

Για την KKT συνθήκες που θα διεξαχθεί σε ένα μη γραμμικό πρόβλημα προγραμματισμού (NLP), Στη συνέχεια καθεμία από τρεις προϋποθέσεις πρέπει να πληρούνται [1-4]. Οι Primal επαναλαμβάνει σκοπιμότητας ποιο είναι το πρόβλημα των κρατών, ότι η ανισότητα και οι περιορισμοί για την ισότητα $x^*$ πρέπει να πληρούνται προκειμένου το πρόβλημα να είναι η βέλτιστη:

$\left.\begin{matrix} h\left ( x^* \right )=0\\ g\left ( x^* \right )\leq0 \end{matrix}\right\} \textrm{primal feasibility (PF)}$

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

$\left.\begin{matrix} \bigtriangledown f\left ( x^* \right ) + \sum_{i=1}^{m}\lambda_{i}\bigtriangledown h_{i}\left ( x^* \right ) + \sum_{j=1}^{l}\mu_{j}\bigtriangledown g_{j}\left ( x^* \right ) = 0\\ \lambda_i \in \mathbb{R}\\ \mu_i \geq 0 \end{matrix}\right\}\textrm{dual feasibility (DF)}$

Η στασιμότητα του προβλήματος είναι:

$\bigtriangledown f\left ( x^* \right ) + \sum_{i=1}^{m}\lambda_{i}\bigtriangledown h_{i}\left ( x^* \right ) + \sum_{j=1}^{l}\mu_{j}\bigtriangledown g_{j}\left ( x^* \right ) = 0$

Ενώ οι άλλες δύο είναι απλώς προϋποθέσεις που λ και μ πρέπει να πληρούν, προκειμένου για $x^*$ να είναι η βέλτιστη.

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

$\mu_i g_{i} \left ( x^* \right ) = 0$

Όταν αυτές οι τρεις προϋποθέσεις είναι, έχουμε με την KKT συνθήκες και τη λύση μας, $x^*$ , είναι μια βέλτιστη λύση για το πρόβλημα NLP. Υπάρχουν ίσως περισσότερες από μία x στο χώρο που πληρούν τις προϋποθέσεις. Οποιοδήποτε σημείο στο χώρο πρόβλημα όπου κάθε στοιχείο τουλκαιμ, έτσι ώστε η πλειάδα (x, λ, μ) πληροί τις προϋποθέσεις KKT ονομάζονται KKT σημεία. Υπολογισμό αυτών των περιορισμών μπορούν να βρεθούν σε [1,2]

Προσόντα Περιορισμών

Όπως αναφέρθηκε προηγουμένως, τα σημεία που έχουμε τις δοκιμές πρέπει να πληρούν ορισμένα προσόντα, προκειμένου για το σημείο που πρέπει να θεωρούνται. Το πιο γνωστό Προσόντα περιοριστικός παράγοντας είναι η Γραμμική Qualification περιορισμός Ανεξαρτησίας (LICQ), το οποίο αναφέρει απλά ότι $h_{j}(x^*)$ και $g_{i}(x^*)$ είναι γραμμικά ανεξάρτητη από τις άλλες στο σημείο $x^*$ . Η Mangasarian-Fromovitz προσόντα περιορισμός (MFCQ) αναφέρει ομοίως το LICQ με την προσθήκη της ύπαρξης θετικών-lineraly ανεξάρτητος, $x^*$ . [5]

Υπάρχουν όμως άλλα προκριματικά περιορισμός που χαλαρώνουν το LICQ. Το προκριματικό περιορισμός Slater μπορεί να χρησιμοποιηθεί σε κυρτό προβλήματα. Εάν υπάρχει ένα σημείο x τέτοιο ώστε $h_{j}(x^*) =$ και $g_{i}(x^*) < 0$ για όλα τα i,ι που δραστηριοποιούνται στην $x^*$ , τότε η κατάσταση έχει πλάκα. [5,6]

Άλλα είδη από τους προκριματικούς του περιορισμού υπάρχουν, αλλά αυτά τα τρία φαίνεται να είναι η πιο συχνά χρησιμοποιούμενη σε KKT προσόντα.

[1] Kuhn, H. και Tucker, Α., “Μη Γραμμικός Προγραμματισμός” Πρακτικά 2ου Συμποσίου Berkeley 1951, pp. 481-492.
[2] Karush, W., “Minima του Συναρτήσεις πολλών μεταβλητών με Ανισότητες ως υποχρεώσεις από την πλευρά”. M. Sc. Διατριβή, Παν. του Σικάγο, Σικάγο, Ο, 1939.
[3] Kuhn, M. “Η Karush-Kuhn-Tucker Θεώρημα”, Internet: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM Βασίλειο. Mannheim, 2006.
[4]McCarl, B. και Spreen, T., “Μη γραμμική Προϋποθέσεις Βελτιστοποίηση”, Χ.. 12, Εφαρμοσμένων Μαθηματικών Προγραμματισμός Χρήση Αλγεβρικών Συστημάτων. Internet: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustaquio, R. Karas, E. Ribeiro και, Α. Προσόντα Περιορισμών για μη γραμμικό προγραμματισμό, Τεχνική Έκθεση, Παν. του Παρανά.
[6] Άφιξη, D. και Zalinescu, C. “Σχετικά με την αναγκαιότητα ορισμένων όρων αναγνώρισης Περιορισμούς στην Κυρτός Προγραμματισμός”, Εφημερίδα της Ανάλυσης Κυρτός, 11 (1), 2004. pp 95-110.

Η Επιστήμη των Υπολογιστών και Διδασκαλία Εφημερίδα

Πρόσφατες δημοσιεύσεις

Karush-Kuhn-Tucker Προϋποθέσεις

Προσόντα Περιορισμών