Optimización Con Restricciones de Igualdad

Optimización Optimización Con Restricciones de Igualdad Dr. E Uresti

ITESM

Optimización Con Restricciones de Igualdad

Profr. E. Uresti - p. 1/31

Introducción En esta lectura veremos el problema de optimizar una función de valor real sujeta a un conjunto de restricciones. El método que veremos se debe a Joseph Louis Lagrange (1736-1813) y la prueba de que define condiciones necesarias para los puntos óptimos aparece en el libro de A. Khuri (1993): Advanced Calculus with Applications in Statistics (John Wiley and Sons, New York) y la prueba de las condiciones de suficiencia aparecen en el libro R. P. Gillespie (1954): Partial Differentiation (Oliver and Boyd, Edinburgh). Veremos un par de ejemplos para clarificar los criterios de máximos y mínimos relativos.


Intro Multilicadores de Lagrange Ejemplo 1 Ejemplo 2 Ejemplo 3 Nota


El método de los Multiplicadores de Lagrange Suponga que se desea optimizar la función real valuada f (x1 , x2 , . . . , xn ) donde las variables x1 ,x2 ,. . . ,xn están sujetas a las restricciones de igualdad (m < n):


g1 (x1 , x2 , . . . , xn ) = 0 g2 (x1 , x2 , . . . , xn ) = 0 .. . gm (x1 , x2 , . . . , xn ) = 0 donde las funciones f ,g1 ,g2 ,. . . ,gm son diferenciables. f debe tener segundas derivadas continuas, mientras que las gi deben tener primeras derivadas continuas.



El primer paso consiste en determinar los puntos críticos para ello se forma la función Lagrangeana: F (x, λ) = f (x) +

m X

λj gj (x)


j=1



El primer paso consiste en determinar los puntos críticos para ello se forma la función Lagrangeana: F (x, λ) = f (x) +

m X

λj gj (x)


j=1

Los puntos estacionarios se determinan resolviendo ∇ F = 0:    ∂f Pm ∂gj ∂F + j=1 λj ∂x1 ∂x1 ∂x1  .   ..  ..   .     ∂F   ∂F + Pm λ ∂gj  ∂xn   ∂xn j=1 j ∂xn    ∇F =  =  ∂F   ∂λ  g1 1    ..  ..   .  .   ∂F ∂λm


gm



     =0      Profr. E. Uresti - p. 4/31

Es decir, los puntos máximos o mínimos se encuentran dentro del conjunto de puntos críticos que se obtienen de resolver el sistema formado por las ecuaciones:


m

X ∂gj ∂f ∂F λj = + = 0 para i = 1, 2, . . . , n ∂xi ∂xi j=1 ∂xi y junto con las m ecuaciones dadas por las restricciones: g1 (x1 , x2 , . . . , xn ) = 0 g2 (x1 , x2 , . . . , xn ) = 0 .. . gm (x1 , x2 , . . . , xn ) = 0 Optimización Con Restricciones de Igualdad


Este sistema se resuelve para las variables x1 ,x2 ,. . . ,xn y λ1 ,λ2 ,. . . , λm . Así pues el sistema consta de n + m ecuaciones en n + m incógnitas: El resultado sobre la necesidad dice: Un máximo o mínimo al problema debe satisfacer el sistema de ecuaciones antes planteado.




Habiendo ubicado los puntos estacionarios viene el problema de determinar si son máximos o mínimos locales.



Habiendo ubicado los puntos estacionarios viene el problema de determinar si son máximos o mínimos locales. Para cada punto estacionario xo y para los valores λ1 ,λ2 ,. . . ,λm correspondientes.



Habiendo ubicado los puntos estacionarios viene el problema de determinar si son máximos o mínimos locales. Para cada punto estacionario xo y para los valores λ1 ,λ2 ,. . . ,λm correspondientes. Se construye la matriz:  (1) (1) (1)  F11 F12 · · · F1n g1 g2 . . . gm (2) (2) (2)   F g g . . . g F · · · F m  22 2n  21 1 2  .  . . . . . . .  .. .. .. .. .. .. ..  ..     B1 = HF =  g1(1) g1(2) . . . g1(n) 0 0 ··· 0   (1) (2)  (n)  g2 g2  0 0 · · · 0 . . . g 2    .. .. .. .. .. ..  . . . .  . . . . . . . .  (1)

gm

(2)

gm

(n)

. . . gm


0

0

···

0


Sea ahora para i = 2, 3, . . . , n − m, Bi la matriz obtenida de B1 eliminando las primeras i − 1 filas y las primeras i − 1 columnas, y sea ∆i el determinante de Bi . xo es un mínimo local si: ■ siendo m par cuando ∆1 > 0, ∆2 > 0, . . . , ∆n−m > 0 ■

siendo m impar, cuando ∆1 < 0, ∆2 < 0, . . . , ∆n−m < 0

xo es un máximo local si: ■ siendo n par cuando ∆1 > 0, ∆2 < 0, . . . , (−1)n−m ∆n−m < 0 ■

siendo n impar, cuando ∆1 < 0, ∆2 > 0, . . . , (−1)n−m ∆n−m > 0



Ejemplo 1 Encuentre los valores óptimos de la función f (x, y) = x2 + 12xy + 2y 2 sujeto a 4x2 + y 2 = 25




Aquí F = x2 + 12xy + 2y 2 + λ(4 x2 + y 2 − 25) El sistema de ecuaciones es:


Fx = 0 = 2 x + 12 y + 8 λ x Fy = 0 = 12 y + 4 y + λ y g1 = 0 = 4 x2 + y 2 − 25



Aquí F = x2 + 12xy + 2y 2 + λ(4 x2 + y 2 − 25) El sistema de ecuaciones es:


Fx = 0 = 2 x + 12 y + 8 λ x Fy = 0 = 12 y + 4 y + λ y g1 = 0 = 4 x2 + y 2 − 25 De la primera ecuación despejas y (Observe que no conviene que despeje x o λ pues implica indicar una división con una expresión que dependerá de una variable y se tendría que considerar por separado el caso cuando es cero.): y = −1/6 x − 2/3 λ x Optimización Con Restricciones de Igualdad


Si sustituimos esto en las ecuaciones 2 y 3 del sistema nos queda: Fy = 0 = 34/3 x − 3 λ x − 4/3 λ2 x = 0 g = 0 = 145/36 x2 + 2/9 λ x2 + 4/9 λ2 x2 − 25 = 0


Si tomamos la nueva ecuación 1 y la factorizamos queda: −1/3 x (4 λ + 17) ∗ (λ − 2) = 0 Esto nos origina tres posibles casos: x = 0, λ = −17/4, y λ = 2 Si sustituimos el caso x = 0 en la segunda nueva ecuación nos queda: −25 = 0 Optimización Con Restricciones de Igualdad


Es decir, este caso de la primera ecuación es incompatible con la segunda. El caso λ = 2 sustituido en la segunda ecuación da: 25/4 x2 − 25 = 0


La cual da las soluciones: x = 2 y x = −2 sustituyendo λ = 2 y estos casos de x dan en y: y = −3 y y = 3 Resumiendo tenemos los puntos: P

x = −2, y = 3, λ = 2

Q

x = 2, y = −3, λ = 2



El caso λ = −17/4 sustituido en la segunda ecuación da: 100/9 x2 − 25 = 0


La cual da las soluciones: x = 3/2 y x = −3/2 sustituyendo λ = 2 y estos casos de x dan en y: y = 4 y y = −4 Resumiendo tenemos los puntos: R

x = 3/2, y = 4, λ = −17/4

S

x = −3/2, y = −4, λ = −17/4



En nuestro problema n = 2 (número de variables en f ) y m = 1 (número de restricciones), y por tanto debemos calcular ∆i desde i = 1 hasta i = n − m = 1. Es decir, que en este ejemplo basta calcular ∆1 para cada punto. La matriz B1 queda:   2 + 8λ 12 8x   B1 =  12 4 + 2λ 2 y  8x 2y 0






Para el punto P (x = −2, y = 3, λ = 2), B1 queda:   18 12 −16   B1 (P ) =  12 8 6  → ∆1 = −5000 −16 6 0 Optimización Con Restricciones de Igualdad




Para el punto P (x = −2, y = 3, λ = 2), B1 queda:   18 12 −16   B1 (P ) =  12 8 6  → ∆1 = −5000 −16 6 0 Como m = 1 es impar, P es mínimo local. Optimización Con Restricciones de Igualdad


Para el punto Q(x = 2, y = −3, λ = 2), B1 queda:   18 12 16   B1 (Q) =  12 8 −6  → ∆1 = −5000 16 −6 0




Para el punto Q(x = 2, y = −3, λ = 2), B1 queda:   18 12 16   B1 (Q) =  12 8 −6  → ∆1 = −5000 16 −6 0


Como m = 1 es impar, Q es mínimo local.



Para el punto R(x = 3/2, y = 4, λ = −17/4), B1 queda:   −32 12 12   B1 (R) =  12 −9/2 8  → ∆1 = 5000 12 8 0




Para el punto R(x = 3/2, y = 4, λ = −17/4), B1 queda:   −32 12 12   B1 (R) =  12 −9/2 8  → ∆1 = 5000 12 8 0


Como n = 2 es par, R es máximo local.



Para el punto S(x = −3/2, y = −4, λ = −17/4), B1 queda:   −32 12 −12   B1 (S) =  12 −9/2 −8  → ∆1 = 5000 −12 −8 0




Para el punto S(x = −3/2, y = −4, λ = −17/4), B1 queda:   −32 12 −12   B1 (S) =  12 −9/2 −8  → ∆1 = 5000 −12 −8 0


Como n = 2 es par, S es máximo local.



La gráfica en la figura 1 ilustra los puntos críticos de ejemplo 1 sobre la misma superficie de la función: se puede observar que tales puntos corresponden a los puntos más altos y más bajos de la superficie restringidos a la elipse.




Repitamos los cálculos utilizando ahora la calculadora TI. En la figura 2 se ilustra el borrado de las variables utilizadas (x, y, nos faltó incluir a la variable t, que funcionará como λ1 ,como t no tenía asignado valor no tuvimos problema); en la variable f está la función a optimizar; en g está la restricción; y en la variable f b la función F = f + λ g.


Figura 2: Inicio del problema 1



En la figura 3 se obtiene el cálculo de Fx (variables f bx), Fy (variable f by) y el planteamiento del sistema para determinar los puntos críticos.

Figura 3: Sistema para obtener los puntos críticos del ejemplo 1



En la figura 4 se obtienen las soluciones al sistema y su conversión a una forma más conveniente. En la matriz representada por p: los valores de x están en la primer columna, los de y en la segunda, y en la tercera los de t (λ). También aparece el cálculo de la matriz hessiana de F (variable h). Nuevamente, utilizaremos la variable i para ahorrarnos la escritura de comandos en el cálculo de ∆1 en cada punto crítico representado en cada renglón de p.

Figura 4: Puntos críticos y B1 del ejemplo 1



En la figura 5 se obtienen los determinantes ∆1 para cada uno de los puntos críticos encontrados. Recuerde que al ser m = 1 (impar): x es mínimo local si ∆1 < 0 y siendo n = 2 (par): x es máximo local si ∆1 > 0. Por tanto, el primero y el segundo renglón de p representan mínimos locales, mientras que el cuarto y el quinto representan máximos locales. Los cálculos coinciden los realizados anteriormente

Figura 5: Cálculo de ∆1 en los puntos críticos del ejemplo 1



Ejemplo 2 Encuentre los máximos y los mínimos de la función


f (x, y, z) = x2 y + 3 z − 6 y + 3 x sujeta a las condiciones g1 (x, y, z) = y − x2 − 1 = 0 y g2 (x, y, z) = x − y + z − 1 = 0



En la figura 6 se preparan los cálculos: se limpian las variables usadas en las expresiones (t1 hará el papel de λ1 y t2 hará el papel de λ2 ); se captura la función f , las restricciones g1 y g2 ; y el cálculo de las parciales.

Figura 6: Preparación del ejemplo 2



En la figura 7 se obtiene la hessiana de F (guardada en h) y la obtención de los puntos críticos y convenientemente codificados en la matriz p. Obervamos que sólo determina tres puntos críticos P (x = 1, y = 2, z = 2, λ1 = 2, λ2 = −3) (renglón 1 de p), Q(x = 0, y = 1, z = 2, λ1 = 3, λ2 = −3) (renglón 2 de p), y R(x = −1, y = 2, z = 4, λ1 = 2, λ2 = −3) (renglón 3 de p). Se utilizó Maple para validar este resultado y hubo concordancia.


Figura 7: Hessiana y puntos críticos del ejemplo 2



Como n = 3 y m = 2, sólo debemos determinar hasta ∆n−m = ∆1 en los puntos críticos. Recordemos que al ser m par, x es un mínimo local si ∆1 > 0. Mientras que al ser n impar, x es un máximo local si ∆1 < 0. En la figura 8 se obtiene el determinante ∆1 en cada uno de los puntos críticos. Por tanto, P y R son mínimos locales y Q es máximo local

Figura 8: ∆1 en los puntos críticos del ejemplo 2



Ejemplo 3 Determine los valores máximos y mínimos relativos de f (x, y, z) = 3 + 4 x − x2 − y 2 − 24 z sujeta a


g(x, y, z) = −6 + x − y − 3 z = 0



En la figura 9 se preparan los cálculos: se limpian las variables usadas en las expresiones (t hará el papel de λ); se captura la función f , la restricción g; y el cálculo de las parciales.

Figura 9: Preparación del ejemplo 3



En la figura 10 se obtiene la hessiana de F , también llamada B1 , y se guarda en h. Como en este ejemplo se debe calcular hasta ∆n−m = ∆2 determinamos la segunda submatriz principal primera de h, también llamada B2 , y la guardamos en la variable h1.

Figura 10: Hf y segunda submatriz primera de Hf para el ejemplo 3



En la figura 11 se obtiene el único punto crítico de F el cual corresponde a P (x = −2, y = 4, z = −4, t = −8). Al ser sólo uno el punto crítico es más conveniente hacer la sustituión directa de las variables en B1 y en B2 . Note que la sustitución no es necesaria pues ni B1 ni B2 tienen variables. Así que la sustitución las dejará igual. Los determinantes que se obtienen son ∆1 = −36 y ∆2 = 18. Al ser n impar el criterio indica que el punto P es un máximo local.

Figura 11: Obtención del único punto crítico y ∆1 y ∆2 en el ejemplo 3



Nota importante Los ejemplos anteriores fueron adecuadamente fabricados de forma tal que los sistemas de ecuaciones para la obtención de los puntos críticos resultaran relativamente fáciles de resolver. En general, tales sistemas de ecuaciones resultan imposibles de resolver en forma exacta. Y en tales casos se utiliza un método numérico.




Optimización Con Restricciones de Igualdad

Recommend Documents