Minimizar funciones unimodales 3

El lunes planteé un problema, el miércoles di una pista y hoy ha llegado la hora de dar la solución.

El problema consistía en encontrar el mínimo de una función unimodal preguntando únicamente 10 valores de dicha función en el intervalo [0, 120]. El objetivo es acotar el mínimo de la manera más precisa posible.

Una sospecha fundada

Con el procedimiento que expliqué el miércoles resulta que necesitamos 2 medidas para eliminar un tercio del intervalo. En la siguiente iteración nos queda un intervalo de tamaño 2/3 del anterior y debemos realizar otras dos medidas en él.

Dividir en tercios

Sin embargo, ya conocemos un valor de ese intervalo. Concretamente el valor de la función en el centro del mismo. Lamentablemente tal y como aplicamos el método no aprovechamos en absoluto esa información en las futuras iteraciones.

Este es el tipo de cosa que dispara todas las alarmas en la cabeza de un matemático. Debe de haber una manera inteligente de usar la información que ya tenemos del intervalo restante para ahorrarnos alguna pregunta o, lo que es lo mismo, mejorar la precisión.

Y en efecto la hay.

Una idea de Oro

Búsqueda Fibonacci

Si elegimos con cuidado el lugar en el que evaluamos la función, cuando llegue la siguiente iteración ya dispondremos de uno de los dos valores que necesitamos para eliminar uno de los subintervalos.

En la imagen de la derecha se puede observar dicho procedimiento aplicado a nuestro problema.

En cada iteración se evalúa la función en un punto. A partir de la segunda se elimina un subintervalo en cada iteración. Gracias a ello, con las mismas 10 mediciones en vez de hacer 5 iteraciones y eliminar 5 subintervalos hacemos 10 y eliminamos 9 subintervalos.

Al final obtenemos la respuesta correcta con una precisión de ± 1’4 km/h en vez de los ± 8 km/h que teníamos antes. Una mejora nada desdeñable contando con que el esfuerzo ha sido el mismo.

Pero un momento, para que todo esto cuadre y en cada iteración podamos eliminar un subintervalo proporcionalmente igual al anterior, se tiene que cumplir la siguiente relación:

Detalle de la Búsqueda Fibonacci

A/(B+C) = A’/(B’+C’) = B/C

Con A = C por simetría:

C/(B+C) = B/C

Y, de nuevo, aquí saltan todas las alarmas en la cabeza del matemático, que tiene grabada a fuego dicha ecuación. Se trata de la ecuación que define la Proporción Áurea.

Precisamente por eso se conoce a este tipo de búsqueda como Búsqueda de la Sección Áurea.

BOLAEXTRA: Existe una versión discreta que se puede utilizar, por ejemplo, en vectores que cumplan la propiedad unimodal y que se llama Búsqueda de Fibonacci. Se basa en la idea de que el cociente entre dos números de Fibonacci tiende a la Proporción Áurea y funciona más o menos igual que lo que acabo de explicar aquí arriba.

Escrito en 10/07/09 10:52 por Carlos Luna en las categorías:

Comentarios

Gravatar.com se ha roto

A riesgo de polemizar, y claramente influenciado por mi trabajo presente, he de decir que las asunciones sobre el comportamiento de funciones desconocidas son peligrosas.

Con ello no pretendo quitar mérito al método aquí expuesto, que matemáticamente es cojonudo [aparece la proporcion aúrea a la que tanto deben griegos, Da Vinci y Dan Brown], pero SÍ quiero puntualizar que la asunción de unimodalidad es arriesgada (además de cómoda).

Sé que dirás que esto no tiene nada que ver con el problema teórico planteado, pero dado que el problema tiene una clara aplicación práctica, quizá faltaría, para completar el artículo, QUÉ puede ocurrir cuando el ingeniero de turno asume unimodalidad cuando la función va por otros derroteros ;)

Eisenreich | 14/07/09 08:56 | #
Gravatar.com se ha roto

@Eisenreich: Muy sencillo, si la función NO es unimodal puedo construir un ejemplo en el que el mínimo obtenido por este método se aleje tanto como quieras (dentro del intervalo inicial) del óptimo que estás buscando.

Pero hasta un ingeniero del MIT debería reconocer que el método es elegante.

Carlos Luna | 14/07/09 09:10 | #
Gravatar.com se ha roto

Wait! Quizás este podría ser el método que estaba buscando.

Muchísimas gracias por explicarlo tan claro (aunque voy 3 años tarde en verlo).

NaaN | 18/06/12 14:07 | #

Deja un Comentario

Quizás quieras usar textile para dar formato a tu comentario.

"linktext":http://       _em_       *strong*       -strike-       ^sup^       ~sub~
bq. Blockquote       # Lista numerada       * Lista no-numerada       ==html crudo, sin textile==

(no será mostrado) (http://...)