Quando un punto è di KKT o di Fritz-John

[JustDani95]

Ciao ragazzi, vi pongo due quesiti:
1) Si consideri il problema:
$ min1/2 (x_1^2+x_2^2), (x_1-1)^2+x_2^2<=1, x_1>=1 $

Perché il punto $(2,0)$ e $(1,0)$ sono di Karush-Kuhn-Tucker? Cioè, qual'è il procedimento generale da seguire?

Domanda analoga: quando un punto è di Fritz-John?

Vi ringrazio.

[Intermat]

Io queste cose le ho studiate un paio di anni fa...quindi sono un po' arrugginito. Ti consiglio di leggerti queste dispense, principalmente pag. 30-31 (ovvero 7-8 del pdf), mi sembrano molto chiare. In ogni caso ho provato a darci una occhiata ma guardalo con occhio molto critico! Per quanto riguarda l'esercizio, ho provato a verificare se i punti sono di KKT ma il primo non mi esce di si, sei sicuro che la domanda sia "perché $(2,0)$ sia di KKT?"
Espresso questo dubbio andrei con ordine:

a) Verificare se $(2,0)$ e $(1,0)$ sono punti di Fritz-John (FJ).

Dato il problema:
$min f(x)$
$s.t. text( ) g(x)<=0$
con $ f in C^1(RR^n)$, $ g: RR^n -> RR^m$ e $ g_i in C^1(RR^n)$ con $i=1,....,m$

Dalla definizione: Un punto $x^** ∈ R^n$ è detto punto di Fritz-John se esistono degli scalari $λ_0, λ_i$, con $i = 1, . . . , m$ (chiamati moltiplicatori di Fritz-John) tali che le seguenti condizioni sono verificate:
$nabla_xL(x^**, lambda_0, lambda)=0$
$λ^T g(x^**) = 0 $
$g(x^**) ≤ 0$
$λ_0 ≥ 0$,
$λ ≥ 0$,
$ (λ_0, λ) != 0$

Dove la $nabla_xL(x^**, lambda_0, lambda)=0$ è il gradiente della funzione lagrangiana:
$L(x, lambda_0, lambda)=λ_0 f(x) + g(x)^Tλ$
e dove l'ultimo vincolo dice che i moltiplicatori di FJ non possono essere tutti contemporaneamente pari a zero.

In questo caso, tornando al problema, avresti:

$g_1(x)=(x_1-1)^2 + x_2^2-1<=0$
$g_2(x)=1-x_1$

quindi calcolando i gradienti:

$nabla g_1^T(x)=[2(x_1-1); 2x_2]$
$nabla g_2^T(x)=[-1; 0]$

quindi i vincoli precedenti espressi nella definizione diventano:

$\{(λ_0x_1^**+ 2*λ_1(x_1^**-1)-λ_2=0 ),(λ_0*x_2^**+2λ_1x_2^**=0),(λ_1[(x_1^**-1)^2+(x_2^**)^2-1]+λ_2(1-x_1^**)=0),((x_1^**-1)^2+(x_2^**)^2-1<=0),(1-x_1^**<=0),(λ_0>=0),(λ>=0),((λ_0,λ)!=0):}$

A questo punto semplicemente devi verificare che i vincoli vengano soddisfatti, esattamente come viene richiesto dalla definizione:

a1) Se $x^**=(2,0)$ allora si avrà:
$\{(2λ_0+ 2*λ_1-λ_2=0 ),(0=0),(-λ_2=0),(0<=0),(-1<=0),(λ_0>=0),(λ>=0),((λ_0,λ)!=0):}$

quindi:

$\{(λ_0=-λ_1),(0=0),(λ_2=0),(0<=0),(-1<=0),(λ_0>=0),(λ>=0),((λ_0,λ)!=0):}$

Il che vuol dire che il punto non è di FJ poiché l'unico caso in cui sono verificati i vincoli che richiedono la non negatività dei moltiplicatori è quello in cui sono tutti zero (ma ciò è vietato dall'ultimo vincolo).

a2)Se $x^**=(1,0)$ allora si avrà:

$\{(λ_0-λ_2=0 ),(0=0),(-λ_1=0),(-1<=0),(0<=0),(λ_0>=0),(λ>=0),((λ_0,λ)!=0):}$

da cui:

$\{(λ_0=λ_2 ),(0=0),(λ_1=0),(-1<=0),(0<=0),(λ_0>=0),(λ>=0),((λ_0,λ)!=0):}$

In questo caso invece il punto è di FJ in quanto esistono dei moltiplicatori di FJ per cui i vincoli sono verificati:

$\{(λ_0=1), (λ_1=0), (λ_2=1):}$

b) Verificare se i punti $(2,0)$ e $(1,0)$ sono punti di KKT

Dalla definizione: Un punto $x^** ∈ R^n$ è detto punto di KKT se esistono degli scalari $λ_i$, con $i = 1, . . . , m$ (chiamati moltiplicatori di KKT) tali che le seguenti condizioni sono verificate:
$nabla_xL(x^**, lambda)=0$
$λ^T g(x^**) = 0 $
$g(x^**) ≤ 0$
$λ ≥ 0$

Dove la $nabla_xL(x^**, lambda)=0$ è il gradiente della funzione lagrangiana:
$L(x, lambda)=f(x) + g(x)^Tλ$

E' facile notare che ogni punto di Fritz-John con $ λ_0 != 0$ è un punto di Karush-Kuhn-Tucker. Infatti se $x^**$ è un punto di Fritz-John con $λ_0 != 0$, basta dividere la prima, la seconda e la quarta relazione della relazione precedente (di FJ) per $λ_0$ per soddifare tutte relazioni di KKT (ponendo $λ_i =λ_i/λ_0$, con $i = 1, . . . , m$).

Riscrivendo la lagrangiana per l'esercizio in questione:

$\{(x_1^**+ 2*λ_1(x_1^**-1)-λ_2=0 ),(x_2^**+2λ_1x_2^**=0),(λ_1[(x_1^**-1)^2+(x_2^**)^2-1]+λ_2(1-x_1^**)=0),((x_1^**-1)^2+(x_2^**)^2-1<=0),(1-x_1^**<=0),(λ>=0):}$

b1)Se $x^**=(2,0)$ allora si avrà:
$\{(2+ 2*λ_1-λ_2=0 ),(0=0),(-λ_2=0),(0<=0),(-1<=0),(λ_1>=0),(λ_2>=0):}$

quindi:

$\{(λ_1=-1),(0=0),(λ_2=0),(0<=0),(-1<=0),(λ_1>=0),(λ_2>=0):}$

Il che vuol dire che il punto non è di KKT poiché è presente un moltiplicatore negativo (a meno di miei errori di conto non impossibili!).

b2)Se $x^**=(1,0)$ allora si avrà:

$\{(1-λ_2=0),(0=0),(-λ_1=0),(-1<=0),(0<=0),(λ_1>=0),(λ_2>=0):}$

Quindi il punto è di KKT in quanto esiste una coppia di moltiplicatori per cui i vincoli precendti sono verificati:

$\{(λ_2=1),(0=0),(λ_1=0),(0<=0),(-1<=0),(λ_1>=0),(λ_2>=0):}$

Ad esempio:
$\{(λ_1=0), (λ_2=1):}$

Considera che ci ho messo di più a scriverlo qui che a farlo...ma decisamente...

PS: Spero di non aver scritto sfondoni...