redtu xgdsfg

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 lafunció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* esmáximo local
Si F es convexa en 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ón
Los 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ónf(x), un vector d es una dirección de 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 estamosbuscando. Calculemos:

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

IV)
Re st.

(

)

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 lafunción objetivo no es cóncava.
En primer lugar, al ser λ*=6 positivo, 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:

I)

IV)

∂L
≤0
∂x
∂L
≤0
∂y

λ1 ( −x2 + y) =0

2

II)

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

V)

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

III)

VI)

Tomamos las de igualdad:

∂L
=0
∂x
∂L...