Métodos matemáticos de optimización no restringida

Búsqueda unidimensional
Muchos métodos de optimización de problemas con restricciones (univariables y
multivariables)
involucran la resolución de un problema de optimización en una dimensión.
Los métodos analíticos imponen demasiadas restricciones a las funciones objetivos.
Además, no
siempre es posible resolver el sistema de ecuaciones analíticamente. Por este
motivo se
desarrollaron los métodos numéricos.
Existen dos tipos de métodos numéricos, a saber:
♣ Métodos directos: sólo utilizan los valores de las función objetivo.
♣ Métodos indirectos: utilizan las condiciones necesarias, las derivadas
(analíticas o
numéricas) y la función objetivo.
Los métodos indirectos requieren el cálculo de las derivadas primeras y segundas.
Sin embargo,
muchas veces obtener las derivadas es una tarea difícil, y hasta es posible que ni
siquiera se
conozca la forma analítica de la función objetivo. Esto plantea la necesidad de
contar con
métodos capaces de trabajar únicamente con los valores (experimentos) de la función
objetivo.
Estos son los métodos de búsqueda directa.
La obtención de un valor de la función objetivo significará en algunos casos
evaluar un modelo
matemático, mientras que en otros significará realizar un experimento. Sea como
sea, siempre
será conveniente llegar al óptimo realizando la menor cantidad de evaluaciones. Esa
es la misión
de los métodos de búsqueda directa, a partir de los resultados de las evaluaciones
realizadas,
sugerirán el siguiente experimento de forma tal de aumentar la velocidad de
convergencia. Es
decir, que estos métodos diseñarán un adecuado plan de experiencias.
El plan de experiencias puede ser secuencial o simultáneo. Cuando disponemos de un
equipo por
un tiempo limitado, puede ser que nos veamos obligados a realizar una serie de
experimentos
simultáneos. Estos experimentos son independientes, los experimentos realizados no
influyen
sobre la forma de realizar el siguiente. Un mejor enfoque es el plan de
experiencias secuencial.
Este método analiza los resultados obtenidos en un experimento para sugerir la
forma de realizar
el próximo.
Los métodos indirectos tienen una ventaja inherente: la convergencia es normalmente
rápida,
pero no son buenos para funciones no lineales multivariables, estos métodos dan
como resultado
un punto que puede encontrarse muy cercano al valor óptimo buscado. Los métodos
directos
tienen la ventaja de que pueden más fácilmente tratar problemas que involucran
funciones con
discontinuidades, puntos de inflexión y puntos finales, pero necesitan la
definición de un criterio
de precisión, estos métodos dan como solución al problema de optimización un
intervalo donde
puede encontrarse el valor óptimo.
Métodos numéricos para optimización de funciones de una variable
Para la aplicación de estos métodos es necesario conocer el intervalo inicial ∆0
donde esta
contenido el óptimo de la función objetivo, y asegurar la unimodalidad de la
función en el
intervalo en estudio.
Un método de optimización para una función de una sola variable podría ser
determinar una
grilla (tan fina como se quiera) de valores de x y calcular los valores de f(x) en
cada valor de la
grilla, el óptimo sería el mejor valor de f(x). Si utilizamos este procedimiento
para funciones
multimodales, el tiempo de cálculo se vuelve prohibitivo. La selección del método
de búsqueda
Procesos Químicos II
2
del óptimo es una solución de compromiso entre la complejidad del procedimiento y
el número
de evaluaciones necesarias.
1. Métodos indirectos: Newton, Quasi-Newton y Secante
Es de suponer que si además de unimodalidad y continuidad en las funciones que
queremos
optimizar, se requiere también la derivabilidad de las mismas, podremos incrementar
la
eficiencia de los algoritmos de búsqueda.
Nos referiremos en esta sección a métodos de búsqueda de óptimos en funciones
derivables.
Recordemos en primer lugar que la condición necesaria para que un punto x* sea
óptimo
local de una función derivable es que se anule su derivada en ese punto, f´(x*) =
0. Cuando
f(x) es una función de tercer grado o superior, la solución analítica de la
ecuación f´(x) = 0 se
complica. Por tanto, requerimos un método de búsqueda que se aproxime sucesivamente
al
punto estacionario de f(x).
La efectividad de estas técnicas se evalúa mediante la velocidad de convergencia
que
presentan.
♣ Convergencia lineal
0 1
*
* 1
≤ ≤ ≤ −
− +
c c
x x
x x
k
k
convergencia lenta
♣ Convergencia de orden p
0, 1
*
* 1
≤ ≥ ≥
−
− +
c c p
x x
x x
p k
k
convergencia muy rápida
Si p=2 la convergencia se dice que es cuadrática
♣ Convergencia superlineal
0
*
* 1
lim → −
− +
→∞ x x
x x
k
k
k
convergencia rápida
Método de Newton
El método de Newton requiere que la función sea dos veces derivable. Se expresa
como:
( ) ( ) k
k
k k
f x
f x
x x ' '
' 1 = − +
asegurando que para cada paso k, f(xk+1)<f(xk
), para la búsqueda de un mínimo.
Este método utiliza la condición de que f’(x)=0.
♣ Ventajas: es un proceso que converge cuadráticamente en forma local. Para una
función cuadrática converge con solo una iteración.
♣ Desventajas: se deben calcular las derivadas primeras y segundas, si las
derivadas
segundas son nulas el método converge lentamente, si existen más de un extremo el
método puede no converger en el valor deseado.
Procesos Químicos II
3
Desafortunadamente el método depende de la elección del punto de partida y de la
naturaleza
de la función. Es bastante posible que este método no converja hacia el verdadero
punto
estacionario. La figura siguiente ilustra esta dificultad. Si comenzamos en un
punto a la
derecha de x0, las aproximaciones sucesivas se alejarán del punto estacionario x*.
Método de Quasi-Newton
Este método es una solución a las limitaciones del método de Newton. En el caso en
que la
función objetivo no sea conocida o no puedan evaluarse las derivadas, estas pueden
reemplazarse por aproximaciones de diferencias finitas:
[ ( ) ( )]
[ ] ( ) () ( ) 2
1
2
2
h
f x h f x f x h
h
f x h f x h
x x k k
+ − + −
+ − −
= − +
La desventaja adicional de este método consiste en la necesidad de evaluar
funciones
adicionales en cada iteración, también es necesario conocer el valor de h (paso de
la
diferencia finita).
Método de la Secante
El método de la secante combina el método de Newton con un esquema de reducción de
intervalo para encontrar, si existe, la raíz de la ecuación f´(x)=0, en el
intervalo (a,b).
En este método la condición necesaria se resuelve mediante la siguiente expresión:
Procesos Químicos II
4
′( ) + ( − )= 0 k k f x m x x
donde m es la pendiente de la recta que une los puntos xp
y xq
, dada por:
( ) ( ) q p
q p
x x
f x f x
m −
′ − ′ =
Este método aproxima la derivada de la función a una línea recta, m aproxima la
segunda
derivada de la función.
( ) [ ] () () ( ) q p
q p
q
q
x x
f x f x
f x
x x
−
′ − ′
′ * = −
donde x * es la aproximación a x* en la iteración nº k.
Este método comienza utilizando dos puntos xp
y xq
, la elección de estos puntos debe hacerse
de tal manera que los valores de las derivadas sean de signos opuestos. Este método
es de
convergencia más lenta que el método de Newton.
2. Métodos directos: eliminación de regiones
Este tipo de métodos se centra en la búsqueda de las soluciones óptimas mediante
sucesivas
reducciones del intervalo de estudio y en la eliminación de subintervalos.
Si la función es unimodal, se puede definir un criterio para eliminar regiones
donde seguro el
óptimo no se encuentra. Para ello necesitamos evaluar la función en dos puntos y
aplicar algo
de lógica. En la figura siguiente se indica cual sería la región eliminada para los
tres casos
posibles en la búsqueda de un máximo.
Procesos Químicos II
5
Es fundamental el hecho de que la función estudiada sea unimodal, al menos dentro
del
dominio de interés. La utilidad de esta propiedad radica en el hecho de que si f(x)
es
unimodal, entonces solamente es necesario comparar f(x) en dos puntos diferentes
para
predecir en cuál de los subintervalos definidos por esos puntos no se va a
encontrar el
óptimo.
Cuando el subintervalo “sobreviviente” tenga una longitud suficientemente pequeña,
la
búsqueda termina. La gran ventaja de estos métodos de búsqueda es que solamente
requieren
evaluaciones de la función y no necesitamos ninguna hipótesis adicional acerca de
la
derivabilidad de la misma.
Búsqueda a intervalos iguales
Este método de búsqueda reduce en 1/3 la longitud del intervalo en cada iteración.
Entonces
si L0
es la longitud original del intervalo (b-a) y Lk
es la longitud luego de k iteraciones:
0
3
2 L L
k
k ⎟
⎠
⎞ ⎜
⎝
⎛ =
Método de la bisección o dicotomía
Este método elimina exactamente la mitad del intervalo en cada paso. En este caso
los puntos
de búsqueda x1 y x2 se encuentran más próximos entre sí, manteniendo la
equidistancia con
los bordes.
0
2
1 L L
k
k ⎟
⎠
⎞ ⎜
⎝
⎛ =
Método de Fibonacci
Con este método se conoce ya el rango inicial de búsqueda y en cada evaluación el
método
tiende a acorralar el punto óptimo.
El intervalo inicial de es L0 y se define ∆1 como el siguiente incremento:
n
n
F
F
L 2
1 0
− ∆ =
donde n, es el número de iteraciones que se desea realizar (en función a la
tolerancia de error
que se desea) y Fn es el número de Fibonacci para n evaluaciones, y se define así:
F0=F1=1,
Fn=Fn-1+Fn-2, n=2,3,... , la secuencia de Fibonacci es entonces
1,1,2,3,5,8,13,21,34,55…
Se tiene entonces x1 = ∆1 y x2 = L0 - ∆1
Se supone que se quiere minimizar a la función unimodal f(x). Entonces si ( ) ( ) 1
2 f x ≥ f x ,
rechazamos el intervalo 0≤x≤x1 y si ( ) ( ) 1 2 f x ≤ f x , rechazamos el intervalo
x2≤x1≤L0.
Procesos Químicos II
6
Gráficamente se tiene que, si originalmente la función es como la que se ilustra en
la figura,
en la segunda iteración se rechaza el intervalo 0≤x≤x1. En forma gráfica tenemos:
A continuación se calcula el siguiente incremento ∆2 y se define x3 como L0- ∆2
1 0 1
1
3
2 1 L L x
F
F
L
n
n ∆ = = −
−
−
En caso de que se hubiera rechazado el intervalo x2≤x1≤L0, entonces L1=x2 y x3= ∆2.
Se tiene
en la segunda evaluación lo siguiente: si ( ) ( ) 2 3 f x ≤ f x , rechazamos el
intervalo x1≤x≤x3 o si
() () 2 3 f x ≥ f x , rechazamos el intervalo x2≤x≤L0.
El proceso se repite hasta llegar al número n de iteraciones prefijadas. La
efectividad en este
caso, 1/Fn, mide la tolerancia del error en el entorno del punto óptimo. Así, por
ejemplo, si se
desea un error menor al 1%, se necesitan 11 evaluaciones de este método, puesto que
F11=144 y 1/F11 = 1/144<0.01= 1%.
Método de la Sección Aurea
En la sección Aurea se ubican dos puntos interiores de manera tal que el intervalo
eliminado
en cada iteración sea de la misma proporción que el intervalo total. Solo un nuevo
punto debe
ser calculado en cada iteración.
Consideremos la localización simétrica de dos puntos como en la figura: