PDF de programación - Teoría sobre la programación no lineal

15.053 Jueves, 25 de abril
Teoría sobre la programación no lineal
Programación separable

Entregas: material de clase

Dificultades de los modelos PNL

PL:

PNL:

1

2

Análisis gráfico de la programación no lineal
en dos dimensiones: un ejemplo

Minimizar

(

x

−

2

14

)

+

(

y

−

2

)
15

sujeto a (x - 8)2 + (y - 9)2 ≤ 49

2

x ≥
x ≤ 13
x + y ≤ 24

3

0

2 4 6 8 10 12141618

¿Dónde está la solución óptima?

y

18
16
14
12
10

8
6
4
2
0

Nota: la solución
óptima no está en
una esquina.
Está donde el
isocontorno toca
la región factible.

x

4

Otro ejemplo:

y

18
16
14
12
10

8
6
4
2
0

0

2

4

6

8

10 12 14 16 18

Minimizar
(x-8)2 + (y-8)2

Entonces el min
global no restringi-
do también es
factible.

La solución óptima
no se encuentra en
el límite de la
región factible.

x

5

Óptima Local frente a Global
Definición: sea x una solución factible, entonces
– x es un max global si f(x) ≥ f(y) para cada y factible.
– x es un max local si f(x) ≥ f(y) para cada y factible.

suficientemente cerca de x (p.ej., x j-ε ≤ yj ≤ xj+ ε para
todo j y algún pequeño ε).

z

z = f(x)

B

A

C

max f(x)
s. a. 0 ≤ x ≤ 1

x
Pueden existir varias soluciones óptimas locales.

1

0

6

¿Cuándo una solución local óptima
lo es también globalmente?

Estamos minimizando. La función

objetiva es convexa. La región factible
es convexa.

Convexidad y puntos extremos
P

Decimos que un conjunto S es convexo, si
por cada dos puntos x e y en S, y por cada
número real λ en [0,1], λx + (1-λ)y ε S.

1
4

1
2

1
0

8

6

4

2

x

y

La región factible de un
programa lineal es convexa.

Decimos que un elemento w ε S es un
punto extremo (vértice, esquina), si w
no es el punto medio de cualquier
segmento dentro de S.

7

2

4

6

8

10

12

14

W

8

Reconocer regiones factibles convexas
Si todas las restricciones son lineales,
entonces la región factible es convexa.
La intersección de regiones convexas

es convexa.

Si para todo x e y factible, el punto
medio de x e y es factible, entonces
la región es convexa (excepto en
ejemplos que sean nada realistas).

9

¿Cuáles son convexas?

A

B

C

D

B ∪ C

B ∩ C

B ⊕ C

10

Funciones convexas

Funciones Convexas: f(λ y + (1- λ)z) ≤ λ f(y) + (1- λ)f(z)
por cada y y z y para 0≤ λ ≤1.
p.ej., f((y+z)/2) ≤ f(y)/2 + f(z)/2
Decimos convexidad “estricta” si el signo
es “<” para 0< λ <1.

f(x)

La unión mediante líneas de cualquier
punto está por encima de la curva

x

y

x

(y+z)/2

x

z

x

11

Funciones cóncavas

Funciones cóncavas: f(λ y + (1- λ)z) ≥ λ f(y) + (1- λ)f(z)
por cada y y z y para 0≤ λ ≤1.
p.ej., f((y+z)/2) ≥ f(y)/2 + f(z)/2

Decimos convexidad “estricta” si el signo
es “>” para 0< λ <1.

f(x)

x

x

z

La unión mediante líneas de cualquier
punto está por debajo de la curva

(y+z)/2

x

y

x

12

Clasificar como cóncava o convexa o como
ambas o ninguna.

todo funciones lineales
algunas funciones cuadráticas

¿Qué funciones son convexas?
f(x) = 4x + 7
f(x) = 4x2 – 13
f(x) = ex
f(x) = 1/x para x > 0
f(x) = |x|
f(x) = - ln(x) para x > 0
Condición suficiente: f”(x) > 0 para todo x.

13

14

¿Qué funciones son convexas?
Si f(x) es convexa, y g(x) es convexa.

Entonces también lo es

h(x) = a f(x) + b g(x) para a>0, b>0.

Si y = f(x) es convexa, entonces

{(x,y) : f(x) ≤ y} es un conjunto convexo

15

¿Cuáles son regiones factibles convexas?

(x, y) : y ≤ x2 + 2

(x, y) : y ≥ x2 + 2

(x,y) : y = x2 + 2

y = 2 + x^2

y

7
6
5
4
3
2
1
0

-2

-1.6

-1.2

-0.8

-0.4

0.4

0.8

1.2

1.6

2

0

x

17

Máximo (mínimo) local

Un máximo local de una función cóncava en una región

factible convexa es también un máximo global.

Un mínimo local de una función convexa en una región

factible convexa es también un mínimo global.

La convexidad o concavidad estricta implica que

el óptimo global es único.

Dado esto, podemos resolver con exactitud:

– Problemas de maximización con una función objetiva

cóncava y restricciones lineales.

– Problemas de minimización con una función objetiva

convexa y restricciones lineales.

16

Más sobre optimidad local
Las técnicas de minimización de optimización

no lineal suelen hallar un óptimo local.

Esto es útil cuando una solución óptima

local es una solución óptima global.

No lo es en muchas ocasiones.

Conclusión: si resuelve un programa no lineal,

intente averiguar qué tal son las soluciones
óptimas locales.

18

Resolución de PNL con Excel Solver

Hallar una óptima local para una sola
variable PNL
Resolver PNLs con una variable :

max f(θ)
s.a. a ≤ θ ≤ b
La solución óptima es
un punto frontera o
satisface f ′ (θ∗) = 0 y f ″(θ∗) < 0.

f(θ)

f(θ)

f(θ)

a

θ *

b

θ

19

a

θ *

b

θ

a
θ *

b

θ

20

Resolución de una PNL con una sola variable
Si f(θ) es cóncava (o unimoda l) y diferenciable

max f(θ)
s.a. a ≤θ≤b

:

Búsqueda bisección (o Bolzano):
Paso 1. Comenzar por la región de incertidumbre de θ
como [a,b]. Evaluar f ′ (θ) en el punto medio θΜ =(a+b)/2.
Paso 2.. Si f ′ (θΜ) > 0, elimine el intervalo hasta θΜ.
Si f ′ (θΜ) < 0, elimine el intervalo más allá de θΜ.
Paso 3. Evaluar f ′ (θ) en el punto medio del nuevo intervalo
Volver al paso 2 hasta que el intervalo de incertidumbre
sea suficientemente pequeño.

Funciones unimodales
Una función de una única variable f es
unimodal si existe a lo sumo un máximo
local (o a lo sumo un mínimo local).

21

22

Otras técnicas de búsqueda
En lugar de derivadas (que tal vez requieran mucha
capacidad de computación), use dos evaluaciones
de funciones para determinar el intervalo actualizado.

Búsqueda de Fibonacci:
Paso 1. Región de incertidumbre para θ como intervalo
[a,b]. Evalúe f(θ 1) y f(θ 2) para 2 puntos simétricos θ1<θ2.

Paso 2. Si f(θ 1) ≤ f( θ2), elimine el intervalo hasta θ1.

Si f(θ 1) > f(θ 2), elimine el intervalo a partir de θ2.

Paso 3. Seleccione un segundo punto simétrico al que
ya está en el nuevo intervalo, llame a estos puntos θ1 y
θ2 de modo que θ1<θ2 y evalúe f(θ 1) y f(θ 2). Vuelva al
paso 2 hasta que el intervalo sea lo bastante pequeño.

23

Sobre la búsqueda de Fibonacci
1, 1, 2, 3, 5, 8, 13, 21, 34
En la iteración 1, la longitud del intervalo de
búsqueda es el número fibonacci k de orden
para cierto k.
En la iteración j, la longitud del intervalo de
búsqueda es el número fibonacci k-j+1.
La técnica converge en la solución óptima
cuando la función es unimodal.

24

Hallar un máximo local con la búsqueda
de Fibonacci
Longitud del intervalo
de búsqueda

342113853

La búsqueda halla un máximo local, pero
no necesariamente un máximo global.

0

13

18

21

16 19

26

Dónde estará el máximo

34

25

0

13

18

21

16 19

26

34

26

La búsqueda halla un máximo local, pero
no necesariamente un máximo global.

0

13

18

21

16 19

26

34

27

Número de evaluaciones de función
en la búsqueda de Fibonacci
Cada punto se elige simétricamente, la longitud l k de los

intervalos de búsqueda sucesivos es: l k = lk+1 + lk+2 .

Resolviendo con estas longitudas dada un longitud final
de intervalo 1, ln = 1, da los nº Fibonacci: 1, 2, 3, 5, 8, 13,
21, 34,…

Por tanto, si el intervalo inicial tiene longitud 34, se
necesitan 8 cálculos de función para reducirlo a 1.

Comentario: si la función es convexa o unimodal, la

búsqueda de fibonacci converge en el max global.

28

Programación separable
Tiene la siguiente forma:
Max

n

f x
(
j

j

)

∑

=
1

j

n

∑

g x
(
ij

≤ ∀ =

0

,

i

)

,
1

,…

m

j

j

=
1

s.a.
Cada variable xj aparece separada, una en
cada función gij y una en cada función fj en el
objetivo.

Cada función no lineal es de una variable única

29

Ejemplos de programacíon
separable

x
1
−

f x x
(

,

1

f x x
(

,

1

=

=

)

)

2

2

(

x
1
x
5
1

30

+

f x x x
(
,

,
123

=
)ln

−
3
x
1
x
5
1

+

)

x

2

(

35

−

−

x

2

)

2

x
2
1

−

3

x

2
2

e
18

−

x

2

+

4

x

2

−

sen

x

2

−

−

x
3

x e
3

+

7

−
x
4
1

30

Aproximación de una función no lineal
con una función lineal por tramos
Aspecto 1. Elegir la aproximación.
Aspecto 2. ¿Cuándo es la aproximación lineal

por tramos un programa lineal disfrazado?

Aproximación de una función
no lineal de 1 variable

y = x^3/3 + 2x - 5

y

15

10

5

0
-3
-5

-10

-15

-20

-25

-2 ,6

-2 ,2

-1 ,8

-1 ,4 -1

-0 ,6

-0 .2 0. 2 0.6

1 1, 4 1, 8 2, 2 2,6

3

31

x

32

Aproximación de una función no
lineal de 1 variable: el método λ

y = x^3/3 + 2x - 5

y

15

10

5

0
-3
-5

-10

-15

-20

-25

-2 ,6

-2 ,2

-1 ,8

-1 ,4 -1

-0 ,6

-0 ,2 0. 2 0.6

1 1, 4 1, 8 2, 2 2,6

3

x

Elija
diferentes
valores of x
para aprox.
el eje x

Aproxime
utilizando
segmentos
rectilíneos

33

y

15

10

5

y = x^3/3 + 2x - 5

Más sobre el λ método
a1 = -3, f(a1) = -20
a2 = -1 f(a2) = -7 1/3
Suponga que para –3 ≤ x ≤ -1,
decimos que x tiene λ1 (-3) + λ2 (-1)
donde λ1 + λ2 = 1 y λ1, λ2 ≥ 0
-0 .2 0. 2 0.6
Entonces aproximamos f(x)
como λ1 (-20) + λ2 (-7 1/3)

1 1. 4 1. 8 2. 2 2.6

-2 , 6

-2 .2

- 1 ,8

- 1 ,4 -1

-0 .6

3

0
-3
-5

-10

-15

-20

-25

x

34

Más sobre el método λ
a2 = -1 f(a2) = -7 1/3
a3 = 1 f(a3) = -2 2/3

y = x^3/3 + 2x - 5

Supongamos que para -1 ≤ x ≤ 1,
decimos que x tiene λ2 (-3) + λ3 (-1)
donde λ2 + λ3 = 1 y λ2, λ3 ≥ 0

y

15

10

5

0
-3
-5

-10

-15

-20

-25

-2.6

-2.2

-1.8

-1.4 -1

-0.6

-0.2 0.2 0.6

¿Cómo
aproximamos f( ) en
este intervalo?

1 1.4 1.8 2.2 2.6

3

¿Y si –3 ≤ x ≤ 1?

x

35

Casi el método λ
Problema original:
min x3/3 + 2x – 5 + más términos
s.a. -3