optimizacion lineal sin restricciones

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 datosexperimenn
tales, por ejemplo 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
2 /x

Φ(t, x) = x1 + x2 e−(x3 −t)

4

+ x5 cos(x6 t)

a
Los n´ meros reales xi , i = 1, . . . , 6 son lospar´metros del modelo. Se
u
desea seleccionarlos 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 discrepanciaentre el modelo y los datos observados. La estimaci´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 delvector de par´metros x es bastante caro desde el punto de vista
a
computacional.

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

1

Caracterizaci´n de un m´
o
ınimo

1.1

¿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 serdif´ de encontrar pues nuestro
ıcil
conocimiento de f es usualmente local. La mayor´ 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. Enparticular 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 localy ∇2 f es continua en un entorno abierto de
Si x∗ es un m´
x∗ , entonces ∇f (x∗ ) = 0 y ∇2 f (x∗ ) es semidefinida positiva.
• 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 por tanto 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...