Condiciones KKT

Pontificia Universidad Católica de Chile
Facultad de Ingeniería
Departamento de Ingeniería Industrial y de Sistemas

Clase 14 • Restricciones de Desigualdad
ICS 1102 • Optimización • Sección 1Profesor : Claudio Seebach
13 de septiembre de 2006

Restricciones de Desigualdad
• Consideremos el siguiente problema:
P) Min f ( x1 ,....., xn )
s.a. g j ( x1 ,....., xn ) ! b j

"j =1,.....m

x1 # 0,....., xn # 0

• Es interesante notar que cualquier problema puede escribirse bajo
este formato estándar
–
–
–
–

Restricciones ≥
Restricciones de igualdad
Variablesno-positivas
Variables sin restricción de no negatividad

Programación No Lineal

Optimización ICS1102 • Apuntes de Clases • Claudio Seebach

1

Restricciones de Desigualdad

Programación No LinealOptimización ICS1102 • Apuntes de Clases • Claudio Seebach

Restricciones de Desigualdad

Programación No Lineal

Optimización ICS1102 • Apuntes de Clases • Claudio Seebach

2Restricciones de desigualdad
• Considere el siguiente problema:
• Las condiciones de optimalidad de primer orden son:
f '( x ) ! 0
Si x = 0 " f '( x ) ! 0 #
$ " x f '( x ) = 0
Si 0 < x " f '( x ) = 0 %
x!0

• Para un caso general:

Min f ( x1 , x2 ,...xn )
s.a. xi ! 0

"i # {
1,..., n}

!f ( x )
"
#0 $
• Las condiciones serían:
!xi
$
!f ( x )
$
xi
=0 '
!xi
$
$
xi # 0
$
(Programación No Lineal
Optimización ICS1102 • Apuntes de Clases • Claudio Seebach

%i & {
1,..., n}

Condiciones de Karush-Kuhn-Tucker (KKT)
• Consideremos el siguiente problema:
P) Min f ( x)x = ( x1 ,....., xn )

s.a. g j ( x) ! b j

"j = 1,.....m

xi # 0

"i = 1,.....n

• Si agregamos variables de holgura a cada restricción, obtenemos:
P) Min f ( x)
s.a. g j ( x) + y j = bj

!j = 1,.....m

xi " 0

!i = 1,.....n

yj " 0

!j = 1,.....m

• Este problema tiene sólo restricciones de igualdad y variables nonegativas…

Programación No Lineal

Optimización...