Apuntes de programacion

LECCIÓN 2: PROGRAMACIÓN NO LINEAL 1. Caso no sujeto a restricciones. 2. Caso sujeto a restricciones de igualdad. La función de Lagrange. Interpretación de los multiplicadores de Lagrange. 3. Caso sujeto a restricciones de desigualdad. Condiciones necesarias y suficientes de optimalidad.

1. CASO NO SUJETO A RESTRICCIONES

DEFINICIÓN DEL PROBLEMA
Optimizar F(x1 , x2 ,..., xn )

con Fdefinida en D de Rn.

¿Teoremas Weierstrass y Local-Global?

MÉTODOS CLÁSICOS Condición necesaria

Teorema: Si x* es solución del problema:

Optimizar F(x) , Entonces ∇F(x*) = 0

Notas: • • • Condiciones necesarias o de primer orden Concepto de punto candidato a óptimo (crítico) Concepto de punto de silla

Ejemplo: Determinar los puntos candidatos a óptimo de la función: F(x,y) = x4 + y4 –2(x-y)2

1

Luego los puntos candidatos a óptimo son (0,0), − 2, 2 y

(

) (

2,− 2

)

2

Podemos observar que (0,0) es punto de silla, ya que es un punto candidato a óptimo que no es ni máximo no mínimo (ver curvas de nivel)

Condición Suficiente
Teorema 2: Sea x* un punto candidato a óptimo de:

Optimizar F(x)

Si F es cóncava en x* ⇒ x* es máximo local Si F es convexaen x* ⇒ x* es mínimo local Si F es ni cóncava ni convexa en x* ⇒ x* puede ser punto de silla

Lo aplicamos al ejemplo anterior:

Observamos que los dos primeros son mínimos locales y que (0,0) es un punto de silla, ya que aunque “parecía” que iba a ser un máximo local, al estudiar en el entorno hemos visto que no se conserva el signo.

Puntos de silla: 3

MÉTODOS NUMÉRICOS

IntroducciónLos algoritmos de optimización no restringida (para mínimo) 1.- Partir de un punto inicial x0. 2.- Buscar una dirección de descenso dk 3.- Elegir un paso ρk. 4.- Calcular un nuevo punto: xk + 1 = xk + ρk dk . 5.- Repetir el proceso hasta que se verifique un test de parada y verificar la optimalidad del punto obtenido. DEFINICION: Dados un punto x0 y una función f(x), un vector d es una direcciónde descenso para f(x) en x0, si existe ε > 0 de forma que: f(x0 + ρ d) < f(x0 ) ∀ρ ∈ (0, ε) TEOREMA: Si ∇f(x0 ).d < 0 entonces el vector d es una dirección de descenso para f(x) en x0.

EJEMPLO Determinar las direcciones de descenso de la función:

f@x_, y_D = x3 − 3 x2 y + 5 x;
en el punto (0,1). Solución:
4

Sea d = (a,b) el vector que estamos buscando. Calculemos:

0   ht HL (x*,λ *) h
∧

(

)

EJEMPLO Queremos ver si se verifica que siendo (-1, -1 ; 6) un punto estacionario de la función de Lagrange asociada al problema:
Maximizar x3 + y3 + 9xy sujeta : −x − y ≤ 2

podemos afirmar que (-1,-1) sea solución de dicho problema.

Observemos que no se verifican las condiciones de segundo orden ya que la función objetivo no es cóncava. En primer lugar, al ser λ*=6positivo, la restricción es activa en el punto. Por lo tanto apliquemos las condiciones de Gill-Murray al problema:
Maximizar x3 + y3 + 9xy sujeta : −x − y = 2

Las condiciones I,II y III se verifican como es obvio.

41

Comprobemos la IV:

La matriz

HL (x*, λ *) es:

∧

Al ser indefinida hemos de clasificarla restringida.

La matriz

(JI g(x*) )

t

es:

Por lo tanto:Que es definida negativa y por lo tanto (-1,-1) es un máximo local.

EJERCICIO Resolver:
Maximizar − (x − 1)2 − y 2 sujeta :
− x2 + y ≤ 0

x+y =2 x, y ≥ 0

Solución: 42

La función de Lagrange asociada:

Las condiciones de K.-T. Aplicadas a nuestro ejemplo son:
∂L ≤0 ∂x ∂L ≤0 ∂y
2

I)

II)

−x +y ≤0 x+y =2 x≥0 y≥0

x

III)

∂L =0 ∂x ∂L y =0 ∂y

IV)

λ1 ( −x2 + y) = 0V)

VI)

λ1 ≥ 0 λ2 cualquiera

Tomamos las de igualdad:

Al aplicar las condiciones V y VI nos quedamos con:

(0,2;0,−4 ),  3 , 1 ;0,−1 , (2,0;0,−2)  
2 2 

Veamos si verifican las restantes condiciones de K.-T.: Condición I)

3 1  Luego la condición I la verifica únicamente el punto  , ;0,−1  2 2  

43

Condición II) Este punto es admisible, luego es un...