32 Lagrange

 Para la figura, las curvas de nivel de la función objetivo son de tal forma que el valor de la
función objetivo mejora cuando hay un desplazamiento según las direcciones de la figura
 Si la proyección del gradiente de la función objetivo sobre el gradiente de la restricción en un
punto dado es distinto de cero, entonces, se puede seguir mejorando el valor de la función
objetivo.
 El mínimo (local) se alcanza en un punto en el que el gradiente de la función objetivo y el de
la restricción son linealmente dependientes.
33 Lagrange
Problema
Mínimizar Z  f ( x)
s.a : g ( x)  0

Lagrangeano

L ( x,  )  f ( x )   g ( x )

Condición para que el par (x*, *) se un optimo, debe cumplirse

L( x,  )
0
x

g ( x)  0
34 Ejemplo
Se requiere construir un recipiente cónico de generatriz 6 cm y capacidad máxima. ¿Cuál debe
ser el radio y la base?

Modelamiento:

Variables r: radio de la base del cono

h : altura del cono

Objetivo V= pr2h/3 (maximizar)

Restricciones r2+h2 = 62
r≥0
h≥0
35 Ejemplo
Planteamiento del problema
1
Mínimizar Z   r 2h
3
s.a : r 2  h 2  36
r, h  0

Aplicando Lagrange se convierte el problema con restricciones a uno sin restricciones.

1

L(r , h,  )   r 2 h   36  r 2  h 2
3

Condiciones necesarias de primer orden y de factibilidad
L(r , h,  ) 2
  rh  2r   0
r 3
L(r , h,  ) 1 2
  r  2h  0
h 3
r 2  h 2  36
36 Ejemplo
De estas ecuaciones resulta

2 h
 rh  2r   0   =
3 3
1 2
 r  2h  0  r 2  2h 2
3
r 2  h 2  36  0  h 2  12
h  12

Solución del problema es

2 3
h2 3 r2 6  
3

Que es un óptimo global, comprobar

37 Ejemplo
En muchos campos de la ciencia y de la tecnología se tienen resultados experimentales que
relacionan cierto par de variables x e y. La relación entre estas cantidades es desconocida, pero se
posee cierta información. En muchas ocasiones se desea encontrar la curva que minimice el error
cuadrático medio de la variable y. Si se ajusta un modelo lineal al conjunto de datos, se tendría
que encontrar la pendiente α y el término constante β que minimizan la función objetivo

n
f  ,      xi    yi 
2

i 1

 ,  sin restricciones
38 Convexidad de la Función Objetivo
Estamos interesados en la clase de funciones tales que sus mínimos locales sean también
globales.

La convexidad asegura este comportamiento

S S
x1
x1
x2
x2

No Convexa Convexa
39 Convexidad de la Función Objetivo
Función convexa. Sea f : S → , donde S es un conjunto no vacío de n. La función f se dice
que es convexa en S si para cualquier par de puntos x1 y x2, y cualquier escalar λ que cumpla 0
≤ λ ≤ 1, se tiene

f   x1  1    x2    f ( x1 )  1    f ( x2 )

Si la desigualdad se satisface estrictamente, se dice que f es estrictamente convexa.

f   x1  1    x2    f ( x1 )  1    f ( x2 )

Similarmente, una función f es cóncava si se cumple la relación con la desigualdad inversa, esto
es, si la función (−f) es convexa.
40 Ejemplos de funciones convexas

Función Función
f(X) convexa f(X) cóncova
f(X2)
f(X11f(X2) f(X11X2)

f(X1) f(X1)
f(X11f(X2)
f(X11X2)
f(X2)

X1 X11X2 X2 X X1 X11X2 X2 X

f(X)
Función
Ni convexa
Ni concova
f(X1)
f(X2)

X1 X2 X
41 Condición de Optimalidad

f´(c) = 0
Solución
f´(d)= 0
óptima
global
f´(a) < 0
S
a c d b

Las condiciónes de optimalidad de Karush, Kuhn y Tucker constituyen el resultado más

importante de programación no lineal. Deben ser satisfechas por cualquier óptimo restringido,
sea éste local o global, y para cualquier función objetivo, ya sea lineal o no lineal.

Los criterios de detención (parada) de los métodos iterativos se basan en estas condiciones.

El criterio de optimalidad de Karush-Khun-Tucker generalizan las condiciones necesarias de

óptimo para los problemas con restricciones.
42 Problema de Programación Matemática no Lineal
De manera compacta un problema de programación matemática no lineal (PMNL) puede
plantearse de la siguiente forma:
Mínimizar Z  f ( x)
sujeta a :
h( x )  0
g ( x)  0
𝑥 = 𝑥1 , … , 𝑥𝑛 𝑇 es un vector con las variables de decisión
𝑓 : ℝ𝑛 ⟶ ℝ es la función objetivo
ℎ : ℝ𝑛 ⟶ ℝ𝑙 son las restricciones de igualdad donde
h( x)   h1 ( x), hl ( x) 
T

𝑔 : ℝ𝑛 ⟶ ℝ𝑚 son las restricciones de desigualdad donde

g ( x)   g1 ( x), g m ( x) 
T

Con f(x) convexa, h(x) y g(x) funciones continuamente diferenciables en la región convexa
S = 𝑥 | ℎ 𝑥 = 0, 𝑔 𝑥 ≤ 0
43 Condición que debe cumplir un punto optimo
Mínimo global: Una función convexa f(x) tiene un mínimo global (mínimo global estricto) en el
punto x*, de S también convexo, ssi f(x*)  f(x) (f(x*) < f(x)) para todo x en S.

Mínimo local: Una función f(x) tiene un mínimo local (mínimo local estricto) en el punto x, de
S, ssi existe un número positivo e tal que f(x)  f(x) (respectivamente, f(x) < f(x)) para todo x
en S tal que 0 < ║x - x║ < e.

Diferenciabilidad: La función 𝑓 : ℝ𝑛 ⟶ ℝ es diferenciable en x si existen las derivadas parciales

𝜕𝑓
; i = 1,…,n.
𝜕𝑥𝑖

𝜕𝑓(𝑥) 𝜕𝑓(𝑥)
∇𝑓 𝑥 = ,…, es el gradiente de f en x.
𝜕𝑥1 𝜕𝑥𝑛

Diferenciabilidad continua: Una función f se dice continuamente diferenciable en x si todas las

derivadas parciales son continuas en x.
44 Condiciones Karush-Khun-Tucker
El vector 𝑥 ∈ ℝ𝑛 satisface las condiciones de Karush- Khun-Tucker para el PPMNL anterior si
existe un par de vectores 𝜆 ∈ ℝ𝑙 y 𝜆 ∈ ℝ𝑚 tales que:
l m
f  x    k hk  x     j g j  x   0 1
k 1 j 1

hk  x   0, k  1, , l 2 
g j  x   0, j  1, , m 3 
 j g j  x   0, j  1, , m 4
 j  0, j  1, , m 5
Los vectores l y m son los multiplicadores de Khun-Tucker.
(2)-(3) se llaman condiciones primales de factibilidad.
(4) es la condición de holgura complementaria.
(5) son las condiciones duales de factibilidad y requieren la no-negatividad de los multiplicadores
de las restricciones de desigualdad
45 Lagrangeano del PPMNL
Condiciones necesarias de primer orden, KKT, se escriben como

L  x,  ,    f  x    T h  x    T g  x 

L  x,  ,    0
x

L  x,  ,    0

g  x  0
T g  x  0
 0
Condiciones de segundo orden, suficiencia
Curvatura positiva en dirección de las restricciones, pT  2 L  x*  p  0 donde p son todas las
direcciones de restricción
46 Ejemplo 1
– Problema de Cobb–Douglas: El nivel de producción de un determinado producto depende
del nivel de inversión en materia prima, que se denota por x1, y de los recursos humanos
empleados, denotado por x2. La función de Cobb–Douglas determina el nivel de producción
en función de las variables x1 y x2, y se desea maximizar. El problema tiene la forma:

max f  x1 , x2   x1 x2

sujeto a : x1  ax2  C
x1  0
x2  0

  0,   0 y     1