Guia pdf

TEMA 2: ´ OPTIMIZACION SIN RESTRICCIONES
En optimizaci´n sin restricciones se minimiza una funci´n objetivo que o o depende de variables reales sin restricciones sobre los valores de esas variables. La formulaci´n matem´tica es: o a (OSR) min f (x)
x∈IR
n

donde f es una funci´n suficientemente regular. o EJEMPLO: Se intenta encontrar una curva que ajuste algunos datos experimenn tales, porejemplo medidas y1 , . . . , ym de una se˜ al tomadas en los tiempos t1 , . . . , tm . Desde los datos y el conocimiento de la aplicaci´n, se deduce que la se˜ al o n tiene un comportamiento exponencial y oscilatorio, y se elige modelarlo por la funci´n: o Φ(t, x) = x1 + x2 e−(x3 −t)
2 /x 4

+ x5 cos(x6 t)

a Los n´ meros reales xi , i = 1, . . . , 6 son los par´metros del modelo. Se u deseaseleccionarlos de manera que los valores del modelo Φ(tj , x) ajusten los datos observados yj tanto como sea posible. Para establecer el objetivo como un problema de optimizaci´n, se agrupan los par´metros xi en un o a t vector de inc´gnitas (x1 , . . . , x6 ) y se definen los residuos o rj (x) = yj − Φ(tj , x), j = 1, . . . , m

que miden la discrepancia entre el modelo y los datos observados. Laestimaci´n de x se obtendr´ resolviendo el problema: o a (MC) min f (x) = r(x)t r(x)/2 6 x∈IR

Este es un problema de m´ ınimos cuadrados no lineales, que es un caso especial de optimizaci´n sin restricciones. Si el n´ mero de medidas es o u 5 o grande (por ejemplo 10 ), la evaluaci´n de f o sus derivadas para un valor concreto del vector de par´metros x es bastante caro desde el punto de vistaa computacional.

Figura 1: Ejemplos de m´ ınimos: x1 m´ ınimo global, x2 m´ ınimo local estricto, x3 m´ ınimo local no estricto

1
1.1

Caracterizaci´n de un m´ o ınimo
¿Qu´ es una soluci´n? e o

INIMO GLOBAL si f (x∗ ) ≤ f (x) para todo x ∈ IRn . Un punto x∗ es un M´ Sin embargo el m´ ınimo global puede ser dif´ de encontrar pues nuestro ıcil conocimiento de f es usualmente local. Lamayor´ de los algoritmos calcuıa lan m´ ınimos locales que son puntos en los que sea alcanza el menor valor de f en su entorno. Formalmente: Un punto x∗ es un M´ INIMO LOCAL si existe un entorno N de x∗ tal ∗ que f (x ) ≤ f (x) para todo x ∈ N . Hay funciones con muchos m´ ınimos locales. Es generalmente dif´ enıcil contrar el m´ ınimo global para tales funciones. Un ejemplo con millones de m´ınimos locales aparece en la determinaci´n de la conformaci´n de una o o mol´cula con energ´ potencial m´ e ıa ınima.

2

1.2

¿C´mo reconocer un m´ o ınimo local?

Si la funci´n f es suficientemente regular existen modos eficientes y pr´cticos o a de identificar m´ ınimos locales. En particular si f es dos veces diferenciable ınimo local examinando su gradiente ∇f (x∗ ) y puede decirse si x∗es un m´ 2 ∗ su hessiano ∇ f (x ). En concreto: ´ • CONDICION NECESARIA DE PRIMER ORDEN: ınimo local y f es continuamente diferenciable en un Si x∗ es un m´ entorno abierto de x∗ , entonces ∇f (x∗ ) = 0. (x∗ punto estacionario) • CONDICIONES NECESARIAS DE SEGUNDO ORDEN: ınimo local y ∇2 f es continua en un entorno abierto de Si x∗ es un m´ x∗ , entonces ∇f (x∗ ) = 0 y ∇2 f (x∗ ) es semidefinidapositiva. • CONDICIONES SUFICIENTES DE SEGUNDO ORDEN: Si ∇2 f es continua en un entorno abierto de x∗ , ∇f (x∗ ) = 0 y ∇2 f (x∗ ) ınimo local estricto de f . es definida positiva, entonces x∗ es un m´ Las condiciones suficientes no son necesarias. Un ejemplo simple est´ a 4 ∗ ınimo dado por la funci´n f (x) = x para la que el punto x = 0 es un m´ o local estricto y sin embargo su hessiano es nulo (y portanto no definido positivo).

Cuando la funci´n objetivo es convexa, los m´ o ınimos locales y globales son f´ciles de caracterizar: a Cuando f es convexa, cualquier m´nimo local x∗ es un m´ ı ınimo global de f . Si adem´s f es diferenciable, entonces cualquier punto estacionario x∗ a es un m´ ınimo global de f .

3

Figura 2: Caso α = 1

EJEMPLO: f (x1 , x2 ) = x2 + x2 + αx1 x2 + x1 +...