Optimización con restricciones
La presencia de restricciones reduce la región en la cual buscamos el óptimo.
Los criterios de optimalidad vistos hasta ahora no siempre se cumplen
( ) ( )22xxf −= ( ) 2x,0xf ==∇
Pero si entonces el mínimo tiene que ser en x=4 y este no es un punto estacionario ya que , por tanto no es el punto estacionario de f
4x ≥( ) 44f ' =
Problemas con restricciones de igualdad 1
( )( ) K,,1k0x,,x,xh.a.s
x,,x,xfmin
N21k
N21
KK
K
==
Método de eliminación de variables: eliminando, K variables independientes, el problema se convierte en un problema sin restricciones
La dimensión del problema se reduce de N a N-K
El problema que se obtiene se puede resolver con cualquier algoritmo de optimización sin restricciones
Problemas con restricciones de igualdad 2
Ejemplo:( )( ) 01xxxxh.a.s
xxxxfmin
3211
321
=−++==
Eliminamos x3
( ) ( )212121 xx1xxx,xfmin −−=
Pero si ( ) 0xxxxxxxh 11
22323
211 =++= −
No es posible eliminar ninguna variable explícitamente
Es necesario encontrar un método que permita manipular las restricciones
Problemas con restricciones de igualdad 3
• Método de los multiplicadores de Lagrange: Transforma el problema original a uno equivalente sin restricciones mediante los multiplicadores de Lagrange.
Minimizar f (x1, x2,..., xN)Sujeto a hk (x1, x2,..., xN) = 0 k=1,2,...,K
• Se transforma en:
Minimizar L(x,v) = f(x) -
• Solución: encontrar el mínimo de L(x,v) en función de v y ajustar v para satisfacer las restricciones. => Se obtiene un sistema deecuaciones cuya solución es el óptimo de la función original.
∑=
K
iii xhv
1)(
Problemas con restricciones de igualdad 4
• Sistema con N+K ecuaciones y N+K incógnitas (x y v):
i = 1,..., N
hk (x) = 0 k=1,... K
• Para saber si es máximo o mínimo se calcula la matriz Hessiana de L con respecto a x:
– Si HL(x;v) es definida positiva => mínimo– Si HL(x;v) es definida negativa => máximo
• Extendiendo los multiplicadores de Lagrange a restricciones de desigualdad, tenemos las condiciones de kuhn-Tucker
0=∂∂
ixL
Problema de Programación no-lineal (NLP)
Se dice que es una restricción activa en el punto si
y es inactiva si
( )( )( )( )N1
k
j
x,,xxK,,1k0xh
J,,1j0xga.sxfmin
K
K
K
===
=≥
( ) 0xg j ≥ x
( ) 0xg j = ( ) 0xg j >
0)( =xg j
0)( >xg jUn punto factible es aquél que satisface las restricciones
Una región factible es la zona donde se satisfacen las restricciones
Condiciones de Kuhn-Tucker
Encontrar los vectores que satisfaga las siguientes condiciones:
∑ ∑= =
=∇λ−∇μ−∇J
1j
K
1kkkjj 0)x(h)x(g)x(f
J,...,2,1j0
J,...,2,1j0)x(gK,...,2,1k0)x(h
J,...,2,1j0)x(g
j
jj
k
j
=≥μ
==μ==
=≥
( ) ( ) ( )K1J11N ,,x ××× λμ
Interpretación de las condiciones de KT
( )( ) K,,1k0xha.sxfmin
k K==
( )
( ) 0xh
0xh)x(f
k
kkk
=
=∇λ−∇ ∑Condiciones de KT
( ) ( ) ( )∑λ−=λk
kk xhxf;xL Función de Lagrange
( ) ( )
( ) ( ) 0xh
0xhxf)x(
kL
kkkL
==λ∇
=∇λ−∇=∇ ∑ Condiciones de Optimalidad de primer orden
Las condiciones de KT son las condiciones de optimalidad de primer orden del Problema de Lagrange
Teorema de Necesidad de Primer Orden
( )( )( )( )N1
k
j
x,,xxK,,1k0xh
J,,1j0xga.sxfmin
K
K
K
===
=≥
Sean f, g, y h funciones diferenciables, y x* una solución factible del problema.
Sea . Además y son linealmente
independientes. Si x* es una solución óptima del problema entonces existe
tales que resuelve las condiciones de KT
( ){ }0xgjI *j == ( ) Ijxg *
j ∈∀∇ ( )*k xh∇
( )**,λμ ( )*** ,,x λμ
A las condiciones de que y sean linealmente independiente en el óptimo se le llama restricción de cualificación
( ) Ijxg *j ∈∀∇ ( )*
k xh∇
Restricción de Cualificación
Para algunos problemas de programación no lineal, además las restricciones de cualificación se satisfacen cuando:
1. Todas las restricciones de desigualdad e igualdad son lineales
2. Cuando todas las restricciones de desigualdad son funciones cóncavas y las de igualdad son lineales y existe al menos una solución x factible, estrictamente dentro de la región factible de las restricciones de desigualdad.
Condición necesaria: si el punto no cumple las condiciones de KT no es óptimo, pero si las cumple puede ser óptimo o no.
Cuando la restricción de cualificación no se alcanza en el óptimo, puede que no exista solución al problema de KT
Teorema de Suficiencia de Primer Orden
( )( )( )( )N1
k
j
x,,xxK,,1k0xh
J,,1j0xga.sxfmin
K
K
K
===
=≥
Sea la función f(x) convexa, las restricciones de desigualdad gj(x) j=1,...,J
todas cóncavas, y las restricciones de igualdad hk(x) k=1,..., K son lineales.
Si existe una solución que satisface las condiciones de KT,
entonces x* es una solución óptima del problema de NLP.
( )*** ,,x λμ
Condición suficiente: si x* cumple las condiciones de KT => x*
es óptimo.
Condiciones de ensilladura o punto de inflexión
Definición:
Se dice que una función f(x,y) tiene un punto de inflexión en (x*,y*) si:
Para todas las x y y.
( ) ( ) ( )**** y,xfy,xfy,xf ≤≤
X* minimiza la función f(x,y*) para todas las x
y* maximiza la función f(x*,y) para todas las y
Problema de punto de silla de KT
( )( )
Sx
J,,1j0xga.sxfmin
j
∈
=≥ K
El problema de punto de silla o de inflexión de Kuhn-Tucker es el siguiente, encontrar un punto (x* , μ*) tal que:
( ) ( ) ( )
Sx0
,xL,xL,xL ****
∈≥μ∀
μ≤μ≤μ
Donde:
( ) ( ) ( )xgxf,xL jj
j∑μ−=μ
Teorema de Suficiencia de Optimalidad
Si es un punto de inflexión de KT, entonces x* es una solución al problema de programación no lineal
( )**,x μ
• No se necesita la suposición de convexidad de las funciones
• No se invoca la restricción de cualificación
• El teorema da la suficiencia. Pudiera existir algunos problemas de programación no lineal, para las cuales no exista un punto de inflexión, incluso aunque tenga solución óptima
Teorema de Necesidad
Sea x* el valor que minimiza la función f(x) sujeta a las restricciones
. Asumimos que S es un conjunto convexo, f(x) es una función convexa, y son funciones cóncavas en S. Asumimos también que existe un punto tal que . Entonces existe un vector de multiplicadores tales que sea un punto de ensilladura o de inflexión de la función de Lagrange
que satisface:
( ) Sx,J,,1j,0xg j ∈=≥ K
( ) 0xg j ≥Sx∈ ( ) 0xg j >
0* ≥μ ( )**,x μ
( ) ( ) ( )xgxf,xL jj
j∑μ−=μ
( ) ( ) ( )
Sx0
,xL,xL,xL ****
∈≥μ∀
μ≤μ≤μ
Teorema:
Una solución donde y es un punto de inflexión de KT si y solo si se cumplen las siguientes condiciones:
1. X* minimiza a para todas las
2.
3.
( )**,x μ 0* ≥μ Sx*∈
( )*,xL μ Sx*∈
( ) J,,1j,0xg *j K=≥
( ) J,,1j,0xgu *jj K==
Punto de inflexión de KT
( )( )( )( )N1
k
j
x,,xxK,,1k0xh
J,,1j0xga.sxfmin
K
K
K
===
=≥
∑ ∑= =
=∇λ−∇μ−∇J
1j
K
1kkkjj 0)x(h)x(g)x(f
J,...,2,1j0
J,...,2,1j0)x(gK,...,2,1k0)x(h
J,...,2,1j0)x(g
j
jj
k
j
=≥μ
==μ==
=≥
Condiciones de KTProblema de PNL
es una solución factible al PNL cuando y
x* es un mín. local del PNL cuando x* es factible y se cumple que
para todas las soluciones factibles en una pequeña vecindad
x* es un mín. local estricto cuando x* es factible y para todas las soluciones
factibles se cumple que en una pequeña vecindad
Un punto de KT del PNL es un vector que satisface las condiciones
de KT
( ) j,0xg j ∀≥ ( ) k,0xhk ∀=x
( ) ( )xfxf * ≤
*xx ≠
( )*xδ
( ) ( )xfxf * < ( )*xδ
),,x( *** λμ
Teorema de Necesidad de Segundo Orden
Consideramos el problema de PNL, y sean f, g y h, funciones dos veces
diferenciables, y sea x* factible para el problema. Sea el
conjunto de las restricciones activas en x*. También se asume que
y son linealmente independientes. Las condiciones
necesarias para que x* sea un mínimo local al problema son:
( ){ }0xgjI *j ==
( ) Ijxg *j ∈∀∇ ( )*
k xh∇
1. Existen unos multiplicadores tales que sea un pto. KT
2. Para cualquier vector se satisface que:
( )**,μλ ( )*** ,,x μλ
( )N1y ×
( )( ) K,,1k0yxh
Ij0yxg*
k
*j
K==∇
∈=∇( ) 0y,,xHy ***
LT ≥μλ
( ) ( ) ( ) ( )∑ ∑= =
λ−μ−=μλJ
1j
K
1kkkjj xhxgxf,,xL
HL es el Hessiano de la función de Lagrange respecto a x y evaluado en ()* * *, ,μ λ x
Teorema de Suficiencia de Segundo Orden
Las condiciones suficientes para que el punto x* sea un mínimo local estricto del problema PNL, donde f, g y h son doblemente diferenciables son las sgtes.
1. Existen unos multiplicadores tales que sean un pto. de KT
2. Para cualquier vector que satisface:
( )**,μλ ( )*** ,,x μλ
( ) 0y N1 ≠×
( ) ( ){ }0,0xgjIj0yxg *j
*j1
*j >μ==∈=∇
( ) ( ){ }0,0xgjIj0yxg *j
*j2
*j =μ==∈≥∇
( ) K,,1k0yxh *k K==∇
( ) 0y,,xHy ***L
T >μλ
Funciones de Penalización 1
( )( )( )
( ) ( ) Nixxx
Kkxh
JjxgasRxxf
uii
li
k
j
N
,,2,1
,,2,10
,,2,10..min
K
K
K
=≤≤
==
=≥∈
El problema original se convierte en un problema sin restricciones mediante una función de penalización
( ) ( ) ( ) ( )( )xh,xg,RxfR,xP Ω+=
R es el conjunto de los parámetros de penalización
es una función de R y las funciones de restricción. Ω
Funciones de Penalización 2
• Características de la transformación:– La solución del problema debe aproximarse a la solución del
problema de NLP:
– El problema de minimizar P(x,R) debe ser similar en dificultad a minimizar f(x)
– R(t+1) = F(R(t)) debe ser simple.
• Dos tipos de transformaciones:– Métodos barrera o forma interior: todos los puntos
generados son factibles– Métodos de forma exterior: los puntos generados son no
factibles.
*)t(Tt
xxlim =∞<→
Funciones de Penalización 3
Función parabólica Operador de bracket( ){ }2xhR=Ω ( ) 2xgR=Ω
⎭⎬⎫
⎩⎨⎧
>α≤αα
=α0si00si
Métodos de forma exterior: puntos generados son no factibles
Ejemplo con restricciones de igualdad 2
En este caso R=100
x(t)=[2.5075,2.5075]T
f(x(t))=4.477 h(x(t)) =0.015
En este caso R=10
x(t)=[2.5714, 2.5714]T
f(x(t))=4.0818; h(x(t)) =0.1428
Ejemplo con restricciones de desigualdad 1
En este caso R=1
x(t)=[3,3]T
f(x(t))=2 g(x(t)) =-1
En este caso R=10
x(t)=[2.75,2.75]T
f(x(t))=3.125 g(x(t)) = -0.5
Ejemplo con restricciones de desigualdad 2
En este caso R=100
x(t)=[2.5075,2.5075]T
f(x(t))=4.4550 g(x(t)) = -0.015
Funciones de penalización 4
• Logaritmica: • Barrera infinita:
con gj(x)<0 ∀ j∈∑∈
=ΩJj
j xg )(10 20 J )](ln[ xgR−=Ω
Ω
g(x)0
∞
Ω
g(x)0
1.0
Métodos barrera o de forma interior: los puntos generados son siempre factibles
Funciones de penalización 5
• Algoritmo:– 1.- Definir ε1, ε2, ε3 => condiciones de terminación para
la búsqueda lineal, vectorial y penalización. X0 y R0
– 2.- P(x,R) = f(x) + Ω(R, g(x), h(x))
– 3.- Encontrar xk+1 / P(xk+1, Rk) sea mínimo con Rk fijo. Terminar con ε2.
– 4.- | P(xk+1, Rk) – P (xk , Rk-1) | ≤ ε3 ? • Si => xk+1 = x* Parar• No => continuar
– 5.- Elegir Rk+1 = Rk + ΔRk y volver al paso 2.
Ejemplo con funciones barrera
R=100 x(t)=[-1.8, -1.8] f(x(t))=67 g(x(t)) =8.612
R=10 x(t)=[1.5, 1.5] f(x(t))=12.5 g(x(t)) =2.0
R=1 x(t)=[2.3, 2.3] f(x(t))=5.45 g(x(t)) =0.30
Método del Gradiente Reducido Generalizado
• Si hk(x) son no lineales pero puedes resolverse explícitamente, puede usarse el método de eliminación de variables:
h1(x) = 0 => xk= Φ(x1,...,xk-1,xk+1,...,xN)
• Esto no ocurre en la mayoría de los casos, pero se puede hacer una aproximación lineal de la restricción en torno a un punto x1
que sí cumpla la restricción:
x1 / hk(x1) = 0
Hk(x; x1) = hk (x1) + ∇hk(x1) (x – x1) k=1,..., K
• Utilizamos está aproximación para encontrar otro punto factible:
( )( ) K,,1k0x,,x,xh.a.s
x,,x,xfmin
N21k
N21
KK
K
==
Método GRG 2
x / hk(x; x1) = 0 k=1,...,K
∇hk(x1) (x – x1)=0 k=1,..., K
• Esto es un sistema de k ecuaciones con N incógnitas y normalmente k<N => no existe solución única. Se puede resolver el sistema para K variables en función de las otras N-K.
• K variables => básicas• N-K variables => no básicas
x̂x
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
∇
∇∇
=
h
hh
J
kˆ
...
ˆˆ
2
1
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
∇
∇∇
=
h
hh
C
k
...2
1
0)()ˆˆ( 11 =−+− xxCxxJ
)(ˆˆ 111 xxCJxx −−=− −
Método GRG 3
• Utilizamos la última ecuación para eliminar k variables de la función objetivo:
• La función objetivo ahora es una función sin restricciones de las N-K variables no básicas, y podemos aplicar las condiciones necesarias para que x1 sea mínimo:
)),(ˆ(),ˆ(~ 111 xxxCJxfxxf −−= −
0~=
∂∂xf )),(ˆ(~)(~ xxxfxf =
xx
xf
xf
xxf
∂∂
∂∂
+∂∂
=∂
∂ ˆˆ
~~)(~
])[(ˆ)()(~ 1111 CJxfxfxf −−∇+∇=∇ Gradiente reducido generalizado
Mínimo: 0)(~ 1 =∇ xf
Método GRG 4
• Hemos usado linealizaciones de las restricciones para expresar la función objetivo como una función de N-K variables no básicas sin restricciones => algoritmo de optimización vectorial en torno al punto de linealización.
• Algoritmo:– 1.- Calcular
– 2.- Si Parar
CJxfxfxf kkk 1)(ˆ)()(~ −∇−∇=∇
ε<∇ ||)(~|| kxf
⎪⎭
⎪⎬⎫
−=
−∇=− dCJd
fd T
1ˆ)~( Tddd ),ˆ(=Si no
– 3.- Minimizar f(xk + α d) con respecto al parámetro α => Hacer xk+1 = xk + α d. Ir al paso 1.
Método GRG 5
• La dirección d así generada es descendente, pero los puntos generados en esa dirección no tienen por qué ser factibles.
• Para resolver este problema, se calcula y se proyecta sobre la superficie definida por el conjunto de restricciones y se minimiza f(x) a lo largo de la curva resultante.
• Encontrar un que cumpla: k=1,...,K
• Si el método converge a un , si nos quedamos con el nuevo punto y seguimos el algoritmo, si no se cumple, se disminuye α y se repiten las iteraciones de Newton
d d
x̂ 0)ˆ,*( =+ xdxh tk α
Método de Newton
)x̂,d*x(h*)]x̂,d*x(J[x̂x̂ ititii α+α+−= −+ 11
x̂ )()ˆ( txfxf <
Algoritmo GRG 1
• Partir de un punto inicial x0, α = α0, ε1, ε2, ε3 >0 criterios de terminación y un parámetro de reducción; 0 < γ <1
• 1.- Elegir una partición de x, en y de forma que J sea no singular. Calcular:
• 2.- Si parar
• 3.- α = α0; a) Calcular vi = xt + α dSi |hk (vi) | ≤ ε2 k=1,...K ir a d)Si no. Continuar
x̂ x)(~ txf∇
ε<∇ ||)(~|| txf
⎪⎭
⎪⎬⎫
−=
−∇=− dCJd
fd T
1ˆ)~( Tddd ),ˆ(=Si no
Algoritmo GRG 2
b)
c) Si ir a b)
Si no: Si | hk (vi ) | ≤ ε3 k=1,..., K ir a (d)
Si no α = γα e ir a (a) => el algoritmo de Newton no converge.
d) Si f(xt ) ≤ f(vi), la dirección no es descendente, hacer α = γαe ir a (a)Si no: xt+1 = vi e ir al paso 1.
11 ||ˆˆ|| ε>−+ ii vv
ii
iiii
vv
vhvJvv
=
−=+
−+
1
11 )(*)(ˆˆ
Tratamiento de los límites 1
• 1.- Tratamiento explícito como desigualdades.• 2.- Implícito: teniendo en cuenta los límites en los pasos del
algoritmo:– 2.1.- Sólo las variables alejadas de sus límites puedes ser
variables básicas, se ordenan las variables de acuerdo con la distancia al límite más cercano:
zi(t) = min {(xiu – xi
t), (xit – xi
L)}Se ordenan las zi en orden decreciente y las k primeras
variables son las básicas.
( )( )( )
( ) ( ) Nixxx
Kkxh
JjxgasRxxf
uii
li
k
j
N
,,2,1
,,2,10
,,2,10..min
K
K
K
=≤≤
==
=≥∈
Tratamiento de los límites 2
– 2.2.- Modifica d para asegurar que los límites no son superados:
⎪⎩
⎪⎨
⎧
∇−
=
i
i
f
d
)~(
00 u
ii xx =Si y 0)~( <∇ ifLii xx =Si y 0)~( >∇ if
en otros casos
– 2.3.- En el paso 3 se deben insertar chequeos para asegurar que los límites no se exceden durante las iteraciones de Newton.Si un límite es excedido, se hace una interpolación lineal entre xt y vi para estimar el punto en esa línea que no exceda el límite.