kReese.net

Il Karush-Kuhn-Tucker (EZ) condizioni, a volte indicato come il Kuhn-Tucker condizioni, sono le condizioni che un problema di programmazione non lineare devono soddisfare per essere ottimale. Le condizioni KKT estende il metodo dei moltiplicatori di Lagrange, consentendo di vincoli di disuguaglianza, a differenza del moltiplicatori di Lagrange, che consentono solo vincoli di uguaglianza.

Consideriamo un problema di ottimizzazione non lineare:

Ridurre al minimo $f(x)$
soggetti a: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

Vi faremo $x^{*}$ rappresentare un punto di minimo relativo per il nostro problema, che soddisfa anche alcuni qualificazione vincolo. Con questo, allora si può supporre che per ogni elemento esiste un vettore $\lambda_j \left ( j = 1, \ldots, l \right )$ , dove il rappresenta il numero di vincoli di uguaglianza, e $\mu_i\left ( i = 1, \ldots, m \right )$ , dove m rappresenta il numero di vincoli di disuguaglianza. Queste costanti, $\lambda_j$ e $\mu_i$ , sono detti moltiplicatori di KKT.

Per le condizioni KKT che si terrà in un problema di programmazione lineare (PNL), poi ciascuna delle tre condizioni devono essere soddisfatte [1-4]. La fattibilità Primal ribadisce qual è il problema stati, che la disuguaglianza e vincoli di uguaglianza su $x^*$ devono essere soddisfatti affinché il problema sia ottimale:

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

La seconda condizione è conosciuta come la condizione di fattibilità doppio. In questa condizione gli stati, piuttosto verboso, che ogni elemento in $\mu_i$ deve essere maggiore di zero, e che la stazionarietà del problema deve essere uguale a 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)}$

La stazionarietà del problema è:

$\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$

Mentre gli altri due sono semplicemente condizioni che l e m devono soddisfare per per $x^*$ essere ottimale.

La terza condizione che devono essere soddisfatti è conosciuto come scarto complementare. Questa condizione dichiara semplicemente che per ogni mu e il suo vincolo di disuguaglianza rispettivi, il prodotto dei due dovrebbe portare a zero,:

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

Quando queste tre condizioni sono soddisfatte, abbiamo incontrato le condizioni KKT e la nostra soluzione, $x^*$ , è una soluzione ottimale per il problema di PNL. C'è forse più di uno x nello spazio che soddisfano le condizioni. Qualsiasi punto nello spazio di problema in cui ogni elemento dilem, tale che la tupla (x, l, m) soddisfare le condizioni di KKT sono chiamati punti di KKT. Derivazione di questi vincoli possono essere trovati in [1,2]

Vincolo delle qualifiche

Come accennato in precedenza, i punti che stiamo testando bisogno di incontrare alcuni di qualificazione in modo che il punto da considerare. Il più Qualificazione vincolo noto è il vincolo lineare di qualificazione Indipendenza (Licq), in cui si afferma semplicemente che $h_{j}(x^*)$ e $g_{i}(x^*)$ sono linearmente indipendenti tra loro al punto $x^*$ . Il Mangasarian-Fromovitz vincolo di qualifica (MFCQ) stati allo stesso modo il Licq con l'aggiunta di essere positiva lineraly indipendente $x^*$ . [5]

Ci sono però altre qualificazioni vincolo che rilassano il Licq. Il qualificatore vincolo Slater può essere utilizzato in problemi convessi. Se esiste un punto x tale che $h_{j}(x^*) =$ e $g_{i}(x^*) < 0$ per ogni i,j attivo $x^*$ , allora la condizione ardesia detiene. [5,6]

Altri tipi di qualificazioni vincolo esistono, ma questi tre sembrano essere i più comunemente usato in KKT qualificazione.

[1] Kuhn, H. e Tucker, A., “Programmazione non lineare” Atti del 2 ° Simposio di Berkeley 1951, pp. 481-492.
[2] Karush, W., “Minimi di funzioni di più variabili con disuguaglianze come vincoli collaterali”. M. Sc. Dissertazione, Univ. di Chicago, Chicago, Il, 1939.
[3] Kuhn, M. “Il Karush-Kuhn-Tucker theorema”, Internet: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, Uni CDSEM. Mannheim, 2006.
[4]McCarl, B. e Spreen, T., “Condizioni di ottimizzazione non lineare”, Ch. 12, Applied Mathematical Programming Utilizzo dei sistemi algebrici. Internet: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustaquio, R. Karas, E. e Ribeiro, A. Qualificazione vincolo per la programmazione lineare, Segnala Tech, Univ. di Paraná.
[6] Arrivare, D. e Zalinescu, C. “Sulla necessità di qualificazione delle condizioni di alcuni vincoli di programmazione convessa”, Gazzetta di analisi convessa, 11 (1), 2004. pp 95-110.

Un Computer Science e Journal insegnamento

Messaggi Recenti

Karush-Kuhn-Tucker Condizioni

Vincolo delle qualifiche