Wikipedia

Condizioni di Karush-Kuhn-Tucker: differenze tra le versioni

Naviga nella cronologia in modo interattivo
← Differenza precedenteDifferenza successiva →
Contenuto cancellato Contenuto aggiunto
VisualeWikitesto
EffeX2 (discussione | contributi)
4 112 modifiche
template voce complessa
Xqbot (discussione | contributi)
Bot
386 675 modifiche
m Bot: Modifico: zh:卡羅需－庫恩－塔克條件; modifiche estetiche
Riga 1:
{{voce complessa|Ottimizzazione|Programmazione non lineare|Metodo dei moltiplicatori di Lagrange}}
In [[matematica]], le condizioni di '''Karush–Kuhn–Tucker''' (anche conosciute come '''condizioni di Kuhn-Tucker''' o '''condizioni KKT''') sono [[Condizione_necessaria_e_sufficienteCondizione necessaria e sufficiente#Condizioni_necessarieCondizioni necessarie|condizioni necessarie]] per la soluzione di un problema di [[programmazione non lineare]] in cui i vincoli soddisfino una delle condizioni di regolarità dette [[condizioni di qualificazione dei vincoli]]. Si tratta di una generalizzazione del [[metodo dei moltiplicatori di Lagrange]], applicato a problemi in cui siano presenti anche vincoli di disuguaglianza. Tali considerazioni prendono il proprio nome da [[William Karush]], [[Harold W. Kuhn]], e [[Albert W. Tucker]] e sono derivate, come caso particolare in cui siano soddisfatte le condizioni di qualificazione dei vincoli, dalle [[condizioni di Fritz-John]]
 
Considerato il seguente problema di [[Ottimizzazione_Ottimizzazione (matematica)|ottimizzazione]] non lineare:
 
:<math> \mbox{min}\; f(x) </math>
Riga 26:
}}</ref>.
 
== Condizioni necessarie ==
 
Si suppone che <math>f : \mathbb{R}^n \rightarrow \mathbb{R}</math>, <math>g_i : \,\!\mathbb{R}^n \rightarrow \mathbb{R}</math> e <math>h_j : \,\!\mathbb{R}^n \rightarrow \mathbb{R}</math>. Inoltre si suppone che esse siano [[Funzione differenziabile|funzioni continuamente differenziabili]] nell'intorno del punto <math>x^*\!</math>. Se <math>x^*\!</math> è un punto di [[Massimo e minimo di una funzione|minimo locale]] che soddisfa le condizioni di regolarità dei vincoli, allora esistono dei moltiplicatori
Riga 36:
 
 
# <math>\nabla f(x^*) + \sum_{i=1}^m \lambda_i \nabla g_i(x^*) + \sum_{j=1}^l \mu_j \nabla h_j(x^*) = 0,</math>
# <math>g_i(x^*) \le 0, \forall i = 1, \ldots, m</math>
# <math>h_j(x^*) = 0, \forall j = 1, \ldots, l\,\!</math>
# <math>\lambda_i \ge 0\ (i = 1,\ldots,m)</math>
# <math>\lambda_i g_i (x^*) = 0\; \forall i = 1,\ldots,m.</math>
 
 
La prima condizione è la condizione di annullamento del [[gradiente]] della [[Metodo_dei_moltiplicatori_di_LagrangeMetodo dei moltiplicatori di Lagrange#Il_metodo_dei_moltiplicatori_di_LagrangeIl metodo dei moltiplicatori di Lagrange|funzione lagrangiana]] associata al problema, la seconda e la terza condizione sono i vincoli di ammissibilità del punto <math>x^*\!</math>, la quarta condizione è la condizione di non negatività del moltiplicatore associato ai vincoli di disuguaglianza, e infine l'ultima condizione viene detta 'condizione di complementarietà'.
 
== Regolarità dei vincoli ==
 
Affinché le condizioni necessarie di KKT permettano di individuare dei punti di minimo locale, deve essere soddisfatta l'ipotesi di regolarità dei vincoli. In generale si può richiedere la regolarità dell'insieme ammissibile, ma in pratica è sufficiente che <math>x^*\!</math> sia un punto di regolarità. Questa può essere dimostrata in più modi:
* ''Requisito di indipendenza lineare dei vincoli'' (LICQ): si richiede che il [[gradiente]] dei vincoli di disuguaglianza attivi in <math>x^*\!</math> (ovvero il sottoinsieme dei vincoli di disuguaglianza che in <math>x^*\!</math> sono verificati all'uguaglianza) e il [[gradiente]] dei vincoli di uguaglianza siano [[Indipendenza_lineareIndipendenza lineare|linearmente indipendenti]] in <math>x^*\!</math>;
* ''Requisito di Mangasarian-Fromowitz'' (MFCQ): la combinazione conica (combinazione lineare a coefficienti non negativi) del gradiente dei vincoli di disuguaglianza attivi in <math>x^*\!</math> e del gradiente dei vincoli di uguaglianza non esiste;
* ''Requisito di rango costante'' (CRCQ): il rango della matrice costituita dai vincoli di disuguaglianza attivi e dai vincoli di uguaglianza ha rango costante, per ogni sottoinsieme di vincoli;
* ''Slater condition'': se il problema è convesso, esiste un punto <math>x\!</math>in cui sono soddisfatti i vincoli di uguaglianza e i vincoli di disuguaglianza attivi in <math>x^*\!</math> sono strettamente minori di zero;
* ''Vincoli lineari'': se h e g sono funzioni affini, allora la condizione di regolarità è sempre verificata in <math>x^*\!</math>.
 
 
== Note ==
 
<references/>
Riga 77:
[[ru:Условия Каруша — Куна — Таккера]]
[[sv:Karush-Kuhn-Tucker-villkor]]
[[zh:卡羅需－卡庫恩－塔克條件]]
Estratto da "https://it.wikipedia.org/wiki/Condizioni_di_Karush-Kuhn-Tucker"