Condizioni di Karush-Kuhn-Tucker: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: Elimino {{Voce complessa}} |
m Bot: Fix tag <math> |
||
Riga 5:
:<math> \mbox{min}\; f(x) </math>
::<math> g_i(x) \le 0 </math>
::<math> h_j(x) = 0
in cui <math>f(x)
Le condizioni necessarie per questo generico problema di ottimizzazione vincolata furono inizialmente pubblicate, nella sua Master thesis, da [[William Karush]]<ref>{{cite paper
Riga 27:
== 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>\mu_j\ (j = 1,\ldots,l)</math> e <math>\lambda_i\ (i = 1,\ldots,m)</math> tali che
Riga 33:
# <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>\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 Lagrange#Il 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^*
== 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^*
* ''Requisito di indipendenza lineare dei vincoli'' (LICQ): si richiede che il [[gradiente]] dei vincoli di disuguaglianza attivi (cioè stringenti) in <math>x^*
* ''Requisito di Mangasarian-Fromowitz'' (MFCQ): la combinazione conica (combinazione lineare a coefficienti non negativi) del gradiente dei vincoli di disuguaglianza attivi in <math>x^*
* ''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
* ''Vincoli lineari'': se h e g sono funzioni affini, allora la condizione di regolarità è sempre verificata in <math>x^*
== Note ==
| |||