Optimización no lineal

Tarea 3
Prof. Adriana Lara López

Instrucciones
Entregue un reporte con las soluciones de las preguntas y actividades indica-
das a continuación. La entrega del reporte de la tarea se debe hacer de manera
electrónica directamente en la plataforma Moodle. Se debe subir un solo archivo
en formato PDF. No se recibirán documentos en otros formatos (i.e., tendrán
calificación automática de cero). El archivo que se sube a Moodle puede actua-
lizarse/reemplazarse cuantas veces se desee, mientras no llegue la fecha lı́mite;
por esto se sugiere no esperar hasta el último momento para subir versiones
preeliminares (Moodle podrı́a no estar disponible durante el fin de semana). No
olvide incluir correctamente en su reporte referencias a fuentes confiables (i.e.,
no wikipedia). Sea claro y conciso con sus respuestas. Use interlineado sencillo e
incluya un ı́ndice de su reporte. De preferencia procese el documento con LaTeX
(no es obligatorio).

1. Teorı́a
1.1. División de intervalos por la mitad
(15 puntos) Hacer cinco iteraciones a mano1 del método de división de inter-
valos por la mitad, visto en clase, para acotar el mı́nimo del siguiente problema:
Minimizar
f (x) = 4x2 + 1/x4
dentro del intervalo [0.7, 2.5]. Reportar los cálculos de cada etapa y los resulta-
dos numéricos (a, b, L, xm , f (xm ), etc). Indique cuál serı́a una aproximación del
óptimo y estime la precisión.

1.2. Método de la sección dorada

(15 puntos) Hacer 5 iteraciones a mano aplicando el método de la sección
dorada al problema de la sección anterior. Escriba el procedimiento y los re-
1 A mano quiere decir sin hacer un programa iterativo que lo resuelva, sino como lo harı́amos

en clase, con lápiz, papel y si acaso una calculadora simple.

1
sultados. Compare los resultados de ambos métodos en cuanto a precisión del
intervalo y número de evaluaciones de la función objetivo.

1.3. Comparación teórica

(20 puntos) Para los métodos división de intervalos por la mitad y sección
dorada, deducir las fórmulas para determinar el número de iteraciones n que
cada algoritmo requiere para acotar el óptimo en un intervalo de longitud menor
o igual que . Considere como L a la longitud inicial del intervalo. Escriba
claramente su razonamiento para obtener cada una de las fórmulas.

2. Programación
2.1. Comparación numérica de algunos métodos de acota-
miento del óptimo
1. (15 puntos) Programar en Octave/Matlab el método de búsqueda exhaus-
tiva, el método de división de intervalos por la mitad y el método de la
sección dorada, que vimos en clase, para acotar el óptimo del siguiente
problema (sobre el intervalo [3, 5]):

Minimizar
sin(x)
f (x) = .
1 + x2
El intervalo inicial, y la precisión del intervalo final deben darse como
parámetros de entrada. El intervalo final será el parámetro de salida. Debe
incluirse una copia del código fuente (comentado) en el reporte de la tarea
(ver sección 4).
2. (15 puntos) Ejecutar sus programas del inciso anterior, y reportar los
resultados con una precisión de 0.05. El reporte debe incluir la salida de
cada programa, o una parte de ella que muestre que el programa hace las
iteraciones correctamente (p.ej. los valores de L o cómo se va reduciendo
el intervalo). En particular, debe reportarse el valor óptimo encontrado
(x∗ y f (x∗ )) como el punto medio del intervalo final.
3. (15 puntos) Ejecutar los programas anteriores para los siguientes valores
de intervalos: [3,5], [3.5,5.5], [4,6], [-8,-6], [-8.5,-6.5], [-7,-9],[-2,0],[-1.5,0.5],[-
1.3,0.7],[1,6]. Hacer una tabla, con la cantidad de veces que se calculó (i)
la función objetivo, y (ii) el número de iteraciones en cada caso (i.e. (a)
búsqueda exhaustiva, (b) div. de intervalos por la mitad, y (c) sección
dorada) usando cada intervalo. Considere un tamaño de 10−12 para el
intervalo final. Presentar en su reporte dicha tabla con los valores promedio
y la desviación estándar sobre los 10 valores (de número de iteraciones y
llamadas a la función objetivo) en cada caso. Presentar en su reporte dicha
tabla con los valores promedio y la desviación estándar sobre los 10 valores

2
 en cada caso. Ejemplo: escribir en X el número de evaluaciones de f para
cada caso:

sec. dor. Búsq.Exh. interv x mitad

Intervalo 1 × × ×
... × × ×
Intervalo n × × ×
promedio × × ×
desv.stand. × × ×

4. (5 puntos) Escriba sus conclusiones para toda esta sección. Verifique si los
experimentos son consistentes con las fórmulas que obtuvo en la sección
1.3.

3. NOTA acerca de los programas

Todos los programas deberán subirse a la plataforma Moodle no después de
la fecha lı́mite de entrega de la misma tarea. Deberán entregarse dentro de un
directorio comprimido con extensión zip, gzip, tar o tar.gz.. Todos los pro-
gramas deben venir comentados y deben poder ejecutarse sin problemas. Debe
incluirse la parte principal del código fuente (comentado) en el lugar correspon-
diente dentro del reporte de la tarea. Pueden entregarse programas de ejemplo
que se dieron en clase o modificaciones de éstos.