KUHN-TUCKER
Min f (x) sujeto a gi (x) <= 0 1<=i<=m
g1
xo
Restricciones activas
En el punto xo
D=CONO DE DIRECCIONES FACTIBLES
g2
CONO G0 A PARTIR DE LOS
GRADIENTES DE LAS RESTRICCIONES
CONO DE DIRECCIONES g2
QUE FORMAN UN ÁNGULO
SUPERIOR A 90 CON CADA
UNA DE LAS RESTRICCIONES
g1
G0 incluido en D
G0={d: gi ‘ * d<0}
•xo regular {gi: i activa} debe ser LI
CONO DESCENSO
Fc={d: d’*f<0}
f
Xo mínimo local si la intersección
de G0 y F0 es vacía
g2
g1
f
LAGRANGIANO
L(x)=f(x)+m1 g1(x) +.....+ mm gm(x)
L(xo)= f(xo)+m1 g1(xo) +.....+ mm gm(xo)
Sea H el hessiano del Lagrangiano
Condiciones de Kuhn Tucker
Si en xo el problema tiene un mínimo local
y xo es un punto regular para el conjunto de
las restricciones activas entonces existe un
vector de multiplicadores m que cumple:
 f(xo)+m1 g1(xo) +.....+ mm gm(xo)=0
 mk gk(xo)=0 1<=k<=m
 mk>=0
Condiciones suficientes
• Se cumplen las condiciones de K-T
• Sea Tan={d: d’* gk(xo)=0 para toda k con gk activa}
: el plano tangente en xo
• Sea M={d: d’* gk(xo)=0 para toda k con gk activa y
mk>0} (Tan contenido en M)
• Se considera una aplicación lineal P, de M en M tal
que para cada yeM se determina Hy y se le proyecta
sobre M , si la matriz asociada a esta transformación
es definida positiva entonces xo es un mínimo local.
¿cómo se determina esta matriz?
• Sea E la matriz de una base ortonormal
en M, todo yeM se expresa y=Ez, al
aplicar H se tiene HEz y para
proyectarlo sobre M basta con
multiplicar por E’ es decir P=E’HE
• Luego se calculan los valores propios
de P y se observa si son positivos.
Complemento ortonormal de
un conjunto, A, de vectores
function B=ortocomp(A)
[n,m]=size(A);
w=n-m;
[Q,R]=qr(A);
B=Q(:,w:n)
return
Determinación de los valores propios de
la proyección sobre M
L hesiano del lagrangiano en xo
G gradiente de las restricciones activas con multiplicador positivo
function [V,D]= proylh(L,G)
M=ortocomp(G)
LM=M'*L*M
[V,D]=eig(LM)
return
D matriz diagonal de los valores propios
ejemplo
Min x1x2+x2x3+x1x3 sujeto a 3-x1-x2-x3<=0 xi>0
Solución de K-T
x1=x2=x3=1 m=2
H=[0 1 1;1 0 1;1 1 0] que es indefinida
¿Cuál es su proyección sobre M?
Descargar

KUHN-TUCKER