Minimizar funciones unimodales 2

El lunes planteé un problema y hoy ha llegado la hora de dar una pista.

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.

Primera aproximación

Es evidente que con una única pregunta no podemos hacer prácticamente nada. Sea cual sea el valor obtenido no sabremos a que lado está el mínimo M.

Con 2 preguntas ya podemos descartar 1 de las 3 regiones en las que queda dividido el intervalo. En la siguiente imagen puede verse claramente cual.

Dividir en tercios

Si medimos f(40) y f(80) y obtenemos, por ejemplo, 6 y 3’5 respectivamente entonces está claro que el mínimo M no puede estar en el subintervalo [0, 40] ya que en ese caso tendríamos más de un mínimo relativo y eso contradice la hipótesis de que nuestra función es unimodal.

Así pues, con 2 mediciones podemos descartar un tercio del intervalo. Aplicando 5 veces este mismo procedimiento podemos reducir el intervalo [0, 120] a un intervalo (2/3)^5 veces menor.

Es decir, podemos encontrar M con un error de ± 8 Km/h.

No está mal pero… ¿Podemos hacerlo mejor?

BOLAEXTRA: Después de esta pista queda claro que es importante elegir bien dónde evaluamos la función. En este caso por cada dos evaluaciones de la función eliminamos un tercio del intervalo restante. Sin embargo da la impresión de que se pueden escoger un poco mejor los puntos donde se evalúa la función. ¿Cómo? El viernes lo veremos.

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

Comentarios

Gravatar.com se ha roto

No acabo de entender el ejemplo.

Según tu mismo has expuesto, según se deduce del primer dibujo el mínimo SÍ puede estar entre 0 y 40 no?

En todo caso, te has planteado que haya otros factores igualmente determinantes que ocasionan una multimodalidad de la función ?

Eisenreich | 10/07/09 08:39 | #
Gravatar.com se ha roto

@Eisenreich: Según el primer dibujo (que está en rojo para que los ingenieros del MIT lo interpreten como erróneo) la función sería unimodal con un máximo o multimodal con, al menos, dos mínimos. Y cómo la hipótesis inicial es que la función es unimodal con un único mínimo debemos obviar esa opción y eliminar ese subintervalo.

Si la función es multimodal no podemos aplicar este método. Pero cómo el título de estos posts es minimización de funciones unimodales suponía que eso ya estaba claro…

Carlos Luna | 10/07/09 09:25 | #

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://...)