1

Capítulo 1
Programación no lineal
Nociones básicas
2 Problema de optimización sin restricciones
¿Qué valor debiera tomar la variable de decisión x para que f (x) sea un máximo en 𝑥1 ≤ 𝑥 ≤ 𝑥2 ?

F = f ( x)

𝑓(𝑥)
𝑓(𝑥 ∗ )

𝑥1 𝑥∗ 𝑥2 𝑥

f(x) es máximo para x = x*

3 Maximización y Minimización

f ( x* ) f (x)
*

x* x
*

-f ( x )
-f ( x* )
*

Si x = x* maximiza f(x), entonces también minimiza –f(x)

 Maximizar f(x) es lo mismo que minimizar –f(x)

 Los problemas de minimización y de maximización son intercambiables
 Dependiendo del problema el óptimo es un máximo o mínimo
4 Minimización
Mínimo local:
Una función f (x) tiene un mínimo local en el punto x*, de S, ssi existe un número positivo 𝜀 tal que
f (x*) ≤ f (x) para todo x ∈ S a una distancia de x* menor que 𝜀, es decir, x ∈ S y 0 < ǀx – x*ǀ < 𝜀.

Mínimo global:
Una función f (x) tiene un mínimo global en el punto x*, de S, ssi f (x*) ≤ f (x) para todo x en S.

Si f (x*) < f (x) para todo x en S, x ≠ x*. Entonces se dice que x* es un punto mínimo global estricto de
f en S
5 Condición necesaria de optimalidad

f (x)
f ( x* )
*
df df
0 0
dx dx

𝑥1 x* 𝑥2 x

Si x = x* maximiza f(x), entonces:

df
f ( x )  f ( x ) para x  x *   0 para x  x *
dx
df
f ( x )  f ( x ) para x  x *   0 para x  x *
dx
6 Condición necesaria de optimalidad

f (x) df
=0
f ( x* ) dx
*

x* x

Si x = x* maximiza f(x) entonces

7 Ejemplo

f (x)

𝑑𝑓
¿Para qué valores de x se obtiene =0?
𝑑𝑥

En otras palabras, ¿para qué valores de x se satisface la condición necesaria de optimalidad ?

8 Ejemplo

f (x)

A B C D
x

 A y D son máximos
 B es un mínimo
 C es un punto de inflexión
9 ¿Cómo se distingue un Máximo de un Mínimo?

f (x)

A B C D
x

𝑑2𝑓
 Para x = A y x = D, se tiene <0
𝑑𝑥 2

 ¡La función objetivo es cóncava en un máximo!

10 ¿Cómo se distingue un Máximo de un Mínimo?

f (x)

A B C D
x

𝑑2𝑓
 Para x = B se tiene >0
𝑑𝑥 2

 La función objetivo es convexa en un mínimo

11 ¿Cómo se distingue un Máximo de un Mínimo?

f (x)

A B C D
x

𝑑2𝑓
 Para x = C se tiene =0
𝑑𝑥 2

 La función objetivo es plana en un punto de inflexión

12 Condiciones necesaria y suficiente de optimalidad

 Condición Necesaria: df
=0
dx

 Condiciones Suficientes:

d2 f
Para un máximo:
2
0
dx

d2 f
Para un mínimo:
2
0
dx
13 Condiciones Necesarias y Suficientes de Optimalidad
¿Podemos decir todo esto sólo mirando la función objetivo?

 Sí, pero para casos simples, en una dimensión cuando sabemos la forma de la función objetivo.

 Para casos complejos, multidimensionales (es decir con muchas variables de decisión) no podemos
visualizar la forma de la función objetivo.

 Debemos confiar entonces en técnicas matemáticas.

14 Conjunto Factible, restricciones
 Los valores que las variables de decisión pueden tomar son por lo general limitados

 Ejemplos:

– Las dimensiones físicas de un transformador debe ser positiva

– La potencia activa de salida de un generador debe estar limitada a un cierto rango ([Link] 200
MW a 500 MW)

– La potencia reactiva de salida de un generador podría estar limitada a un cierto rango ([Link] -100
MVAr a 150 MVAr)
15 Conjunto Factible

f (x)

A B C D
xmin xmax x
Conjunto Factible

 Los valores de la función objetivo fuera del conjunto factible no importan

16 Soluciones Interiores y de Borde

f ( x)

A B C D
xmin xmax x

 A y D son máximos locales, interiores

 B es mínimo local, interior

 Xmín es mínimo de borde No satisfacen las condiciones

 Xmáx es máximo de borde de optimalidad!
17 Caso en dos Dimensiones

f ( x1 , x2 )

x1* x1
x2* f ( x1* , x2* ) es un mínimo
x2
18 Condiciones Necesarias de Optimalidad

f ( x1 , x2 )
f ( x1 , x2 )
=0
x1 x* , x*
1 2

f ( x1 , x2 )
=0
x2 x* , x*
1 2

x1* x1
x2*
x2
19 Caso Multidimensional
En un valor máximo o mínimo de 𝑓(𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛 ) debemos tener:

f
=0
x1
f
=0
x2

f
=0
xn

 Un punto donde se cumplen estas condiciones se denomina punto estacionario.

20 Condiciones Suficientes para Optimalidad

f ( x1 , x2 )

x1

Mínimo Máximo
x2
21 Condiciones Suficientes para la Optimalidad

f ( x1 , x2 )
Punto de silla

x1

x2
22 Condiciones Suficientes para la Optimalidad
 Cálculo de la matriz Hessiana en el punto estacionario:

 2 f 2 f 2 f 
 
 x 1
2
x1x2 x1xn 
 2 f 2 f 2 f 
 
 x2x1 x22 x2xn 
 
 
 2 f 2 f 2 f 
 
 xn x1 xn x2 xn2 
23 Condiciones Suficientes para la Optimalidad
Calcular los eigenvalores de la matriz Hessiana en el punto estacionario

 Si todos los eigenvalores son mayores o iguales al cero:

– La matriz H(x*) es definida positiva
– F(x) es convexa en X*
– El punto estacionario es mínimo

 Si todos los eigenvalores son menores o iguales al cero:

– La matriz H(x*) es definida negativa
– F(x) es concova en X*
– El punto estacionario es un máximo

 Si hay eigenvalores positivos y otros negativo:

– El punto estacionario es un punto de silla
24 Curvas de Contornos

f ( x1 , x2 )

x1

C1 C2

x2
25 Curvas de Contornos
 Las curvas de contorno son el lugar geométrico de todos los puntos que dan el mismo valor a la
función objetivo

X2

Mínimo o Máximo

X1
26 Ejemplo 1

Minimizar C = x12 + 4 x22 − 2 x1 x2

 Condiciones necesarias de optimalidad

C 
= 2 x1 − 2 x2 = 0 
x1   x1 = 0 punto estacionario
  
C
= −2 x1 + 8 x2 = 0   x2 = 0
x2 
27 Ejemplo 1
Condiciones suficiente de optimalidad

  2C  2C 
 
 x1 x1x2   2 −2 
2
Matriz Hessiana
= 
  2C C2   −2 8 
 
 x2x1 x22 

Debe ser positiva definida, es decir, todos los eigenvalores deben ser positivos

 −2 2
=0   2 − 10 + 12 = 0   = 5  13  0
2  −8

El punto estacionario es un mínimo

28 Ejemplo 1

X2

X1

Mínimo: C = 0
29 Ejemplo 2

Minimizar C = − x12 + 3x22 + 2 x1 x2

 Condiciones necesarias de optimalidad

C 
= −2 x1 + 2 x2 = 0 
x1   x1 = 0
   punto estacionario
C
= 2 x1 + 6 x2 = 0   x2 = 0
x2 
30 Ejemplo 2
Condiciones suficiente de optimalidad

  2C  2C 
 
 x1 x1x2   −2 2 
2
Matriz Hessiana
= 
  2C C2   2 6
 
 x2x1 x22 

Debe ser positiva definida, es decir, todos los eigenvalores deben ser positivos

+2 −2  = 2+2 3  0
=0   2 − 4 − 8 = 0 
−2  −6  = 2−2 3  0

El punto estacionario es un punto de silla

31 Ejemplo 2

X2
C=0

C=9

C=4

C=1

C=-9 C=-4 C=-1 C=-1 C=-4 C=-9

X1

C=1

C=4

C=9
C=0
32 Ejemplo 3
 Se requiere construir un recipiente cónico de generatriz 6 cm y capacidad máxima. ¿Cuál debe ser
el radio y la base?

Variables r : radio de la base del cono

h : altura del cono
Objetivo V= pr2h/3 (máximizar)
Restricciones r2+h2 = 62
r>0
h>0
33 Ejemplo 4
Convirtiendo el problema con restricciones a uno sin restricciones

1
V =  r 2h
3
62 = r 2 + h 2

r 2 = 62 − h 2

1
3
( ) 1
V =  62 − h 2 h = 12 h −  h3
3

Es decir, debemos maximizar el volumen del cono en términos de la altura h

34 Problema 3
 Condición necesaria (primer orden)

dV
=0  12 −  h 2 = 0  h = 12
dh

 Condición suficiente (segundo orden)

d 2V
dh 2
= −2 h 
d 2V
dh 2
= −2 ( )
12  0
h = 12

 Con esto observamos que V es cóncava para ℎ = 12

 Luego V en ℎ = 12 es máximo.

 Solución: h = 12 r=2 6
35 Problema
– 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