Definiciones• Optimo local (mínimo local)
Un punto x*∈F se denomina un mínimo local del problema de optimización si existe un entorno de x* tal que para cualquier otro punto x ∈ F del entorno:
J(x*) ≤ J(x)
J(x)
xx*
Pueden existir varios óptimos localesJ(x)
xx1* x2*
Si se verifica la desigualdad estricta el óptimo es propio
J(x)
xx*
Mínimos impropios
Definiciones
• Optimo globalUn punto x* se denomina un mínimo global del problema de optimización si para cualquier punto x del conjunto factible F:
J(x*) ≤ J(x)xx*
Optimo global
J(x)
x
Problema no acotado
Si no existe ningún valor de x* ∈F tal que J(x*) ≤ J(x) el problema es no acotado y no existe mínimo
Definiciones• Continuidad
x
Continua en x0
x0
)x(J)x(Jlimexiste)x(J
existe)x(Jlim
0xx
0
xx
0
0
=→
→
xx0
discontinua en x0
Derivada no definida
Es importante para muchos algoritmos trabajar con funciones continuas y con derivadas continuas
Definiciones• Funciones MonótonasUna función f(x) es monótona creciente (o decreciente) si para cualesquiera dos puntos x1 y x2, donde x1 ≤ x2 se cumple que
( ) ( )21 xfxf ≤ Monótona creciente
( ) ( )21 xfxf ≥ Monótona decreciente
• Funciones UnimodalesUna función es unimodal si es monótona a ambos lados del mínimo.
Definiciones• Conjunto factible
El conjunto S donde buscar la solución
En un problema de programación escalar: R o el intervalo [a,b]
En un problema de programación vectorial: R^n
En un problema de programación con restricciones: el conjunto de puntos que cumplen las resticciones.
0)x(g0)x(h
)x(Jmin
j
i
x
≤=
Definen la región de busqueda o conjunto factible F
J(x)
x2
x1
F
Definiciones
1h
• Factibilidad.
0)x(g0)x(h
)x(Jmin
j
i
x
≤=
Definen la región de busqueda o conjunto factible F
x2
x1
J1J2
J3F
Si no hay ningún punto x que satisfaga todas las restricciones, o sea si el conjunto factible F es vacío, el problema es no‐factible y no existe solución
Definiciones• Convexidad.
x1
x2
J1J2
J3F
La forma de la región de búsqueda es importante para los algoritmos de optimización
FF convexo
Un conjunto F es convexo si el segmento que une dos puntos cualquiera del mismo esta totalmente contenido en F
F no‐convexo
F
Definiciones
• Conjunto convexoF es convexo si y solo si:
Fx)1(xx]1,0[,Fx,x
21
21
∈γ−+γ=∈γ∀∈∀
F
Región convexa y cerrada
La intersección de dos conjuntos convexos es convexa
Definiciones
• Función convexa
La función J(x) es convexa en un conjunto convexo F si no toma valores superiores a los de una interpolación lineal
J(x)
xx1 x2
)x(J)1()x(J)x)1(x(J]1,0[,Fx,x
2121
21
γ−+γ≤γ−+γ∈γ∀∈∀
Si se cumple con < es estrictamente convexa
Definiciones
• Convexidad de funciones (de una variable)
20
2
202
02
00
0
202
02
00
0
dx)x(JdH
...)xx(dx
)x(Jd21))xx(
dx)x(dJ)x(J()x(J
...)xx(dx
)x(Jd21)xx(
dx)x(dJ)x(J)x(J
=
+−=−+−
+−+−+=
Si H es continua y positiva semidefinida la función J(x) es convexa en un entorno de x0
J(x)
x0x
J(x0)+J’(x0)(x‐x0)
Definiciones
• Convexidad.
xx1 x2
J(x) J(x)
xx1 x2
Si J(x) es convexa, ‐J(x) es concava
Una función lineal es convexa y concava
J(x)
x
Definiciones• Teorema
Una función continua J(x) tiene un mínimo global en cualquier conjunto F cerrado y acotado
J(x)
x2
x1
F
Definiciones
• Si una función es unimodal en su conjunto factible, entonces un mínimo local es automáticamente un mínimo global
• Toda función convexa es unimodal
Optimización sin restriccionesLos métodos sin restricciones son importantes porque:
Hay problemas que se pueden formular sin restricciones
Permiten introducir muchos conceptos y explorar ideas que se usarán en problemas NLP
Muchos problemas de optimización utilizan en alguna fase algoritmos sin restricciones
Algunos problemas NLP pueden reformularse como problemas sin restricciones
nx
Rx
)x(Jmin
∈
Criterios de optimalidad.
• Ante un problema de optimización debemos resolver dos problemas:
– ¿Cómo se determina que un punto x* es óptimo?– Si x* no es el óptimo, ¿cómo se puede encontrar la solución óptima?
( )bxaas
xf≤≤..
max Forma general de un Problema de optimizaciónescalar
Condiciones de necesidad y suficiencia• Condición necesaria para que dado un punto este sea
óptimo:
0dxdf
=
Es un punto estacionario
( )002
2≤≥
dxfd
• Condición suficiente: Supongamos que en el punto x* la primera derivada es 0, y la primera derivada de orden superior que no sea 0 la denotamos por n:– Si n es impar, entonces x* es un punto de inflexión– Si n es par, entonces x* es un óptimo local, además:
• Si la derivada es positiva, entonces x* es un mínimo local• Si la derivada es negativa, entonces x* es un máximo local
Métodos de soluciónMétodos de Solución
Métodos analíticos Métodos numéricos
Método minimax, Fibonacci, Sección
dorada
Método de Powell
Métodos de eliminación
Métodos que no requieren derivadas
Métodos que requieren derivadas
Método de Newton‐Raphson
Métodos analíticos
• Método exhaustivo
– Evaluar df/dx = 0 y calcular los puntos estacionarios
– Seleccionar todos los puntos estacionarios que pertenezcan al intervalo [a,b], junto con a y b.
– Encontrar el valor máximo de f(x)
Métodos numéricos (I)
• Métodos de eliminación (reducción de intervalos).– Suponemos que J(x) es unimodal en el conjunto factible [a,b]
– Generar una sucesión de intervalos [x1 , x2], [x3, x4],.... dentro de cada uno de los cuales esta el óptimo y de longitud cada vez menor hasta llegar a la precisión requerida:
– 2 pasos:• Encontrar el intervalo inicial donde esta el óptimo
• Reducir la longitud del intervalo inicial hasta la precisión requerida
J(x)
x3x1 x2x4
Métodos de eliminación (I)
• Si J(x) es unimodal en [a,b] , para dos puntos x1 < x2 del conjunto factible se cumple la propiedad de eliminación:
– Si J(x1) > J(x2) => x* ∈ (x1, b) => x* > x1– Si J(x1) < J(x2) => x* ∈ (a, x2) => x* < x2– Si J(x1) = J(x2) => x* ∈ (x1, x2) => x1 < x* < x2
J(x)
x1x* x2J(x)
x1 x2x*
J(x)
x1 x2x*
Métodos de eliminación (II)
• 1.‐ Encontrar el intervalo inicial– Seleccionar x0 y Δ y aplicar la propiedad de
eliminación para x0+ Δ y x0 ‐ Δ.
‐ Conocido un semi‐intervalo inicial p.e. [x0, ∞) donde esta x*, para localizar un intervalo inicial se puede generar una secuencia de valores:
xk+1
J(x)
x0 x1 .... xk
δ+=
δ+=
δ+=δ+=
−1k0k
203
02
01
2xx....
2xx
2xxxx Hasta que:
J(xk‐1) > J(xk) ≤ J(xk+1)
El intervalo inicial es [xk‐1 , xk+1]
Compromiso precisión / nº de iteraciones
δ Es positivo o negativo según el semiintervalo
Métodos de eliminación (III)
• 2.‐ Reducir el intervalo inicial hasta la precisión deseada:Si en el paso k el intervalo en el que se encuentra el óptimo es
[αk , βk], se puede reducir su longitud Lk = βk ‐ αk evaluando la función J(x) en dos puntos γ1 < γ2 internos al intervalo aplicando la propiedad de eliminación:
J(x)
αk βkγ1 γ2
],[],[)(J)(J],[],[)(J)(J],[],[)(J)(J
211k1k21
2k1k1k21
k11k1k21
γγ=βα⇒γ=γγα=βα⇒γ<γβγ=βα⇒γ>γ
++
++
++¿Como elegir los dos puntos internos?
Métodos de eliminación (IV)• Método ε‐minimax:
– Criterio: minimizar la longitud del mayor de los intervalos posibles: Min max { γ2 ‐ αk, βk ‐ γ1, γ2 ‐ γ1}
– Si γ2 = γ1 + ε => Min max{γ1 + ε ‐ αk, βk ‐ γ1}
– γ1 + ε ‐ αk = βk ‐ γ1
J(x)
αk βkγ1 γ2
ε
γ1
γ1 + ε ‐ αk
αk ‐ ε
βk ‐ γ1
βk
22
22kk
2
kk1
ε+
α+β=γ
ε−
α+β=γ Simétricos
respecto al centro del intervalo
Métodos de eliminación (V)
• Método ε‐minimax:J(x)
αk βkγ1 γ2
ε
2L
22
22L
kkk
kkk
k21k
ε+=
ε+
α−β=
=α−ε
+α+β
=α−γ=+
‐ La reducción del intervalo en un paso es:
ε debe escogerse tan pequeño como se pueda para reducir la longitud del intervalo. La reducción en N pasos es:
N0
N
N0
N 2L
2)12(LL ≈ε−+
=
γ2 ‐ αk = βk ‐ γ1
Métodos de eliminación (VI)• Método de Fibonacci:J(x)
αk βkγ1 γ2
ε
αk βkγ1 γ2
ε
αk+1γ βk+1
‐ En el método ε‐minimax se precisan dos evaluaciones de J(x) en cada iteración. El método de Fibonacci aprovecha una de las evaluaciones anteriores
‐ Se selecciona ε de forma que en cada iteración γ1 coincida con el γ2de la iteración anterior o al revés.
‐ Las longitudes de los intervalos son: lk+1 = (lk + ε)/2
Métodos de eliminación (VII)• Método de Fibonacci:
– Para conseguir eso hay que seguir el siguiente procedimiento:• li‐1 = 2 li ‐ ε• li‐2 = li‐1 + li = 3 li ‐ ε• li‐3= li‐2 + li‐1 = 5 li ‐ 2 ε• .....• li‐k = li‐k‐2 + li‐k‐1 = Fk+1 li ‐ Fk‐1 ε
– Donde Fk corresponden a los coeficientes de la secuencia de Fibonacci:
• F0 = F1 = 1• Fk = Fk‐1 + F k‐2• En N pasos se llega a un intervalo: lN = (l0 + FN‐1 ε)/ FN+1
Métodos de eliminación (VIII)
• Método de Fibonacci:– Algoritmo:
• Seleccionar la precisión deseada Δ y ε• Generar la sucesión de Fibonacci Fi hasta que li < Δ• Aplicar N veces el método ε‐minimax teniendo en cuenta el aprovechamiento de uno de los γi del paso anterior
Métodos de eliminación (IX)• Método de la sección dorada:
– Se prescinde del cálculo de la sucesión de Fibonacci aproximando la longitud de cada intervalo por el límite para ε → 0 e i →∞
• ε → 0 l0 = Fi+1 li ; l1 = Fi li => l1 = (Fi / Fi+1) l0• i→∞ lim (Fi / Fi+1) = 1 / γ = 0.618• En N pasos: lN = (0.618)N l0
Algoritmo:
• Seleccionar la precisión deseada: Δ
• Calcular i tal que li < Δ
• Aplicar i veces el método ε‐minimax teniendo en cuenta el aprovechamiento de uno de los γ i
Comparación
• Precisión de los métodos con 4 iteraciones y l0= 0.82
– Método ε‐mimimax : lN = l0 / 2N
• l4= 0.82/ 16 = 0.098 , N ev = 8
– Método de Fibonacci: ln = (l0 + FN‐1 ε) / FN+1• L4 = (0.82 + 2*0.02 )/ 8 = 0.11, Ne.v. = 5
– Método de la sección dorada: lN = (0.618)N l0• L4 = (0.818)4 * 0.82 =0.12, N.ev. =5
Métodos numéricos (II)
• Métodos de aproximación por un polinomio:– J(x) debe ser unimodal y continua– Cerca del mínimo J(x) se puede aproximar por una función de 2º orden: Q(x) = a + bx + cx2
– Dados 3 puntos cerca del mínimo se aproxima J(x) por un polinomio de 2º grado que pase por esos puntos:
q(x) = a0 + a1 (x‐x1) + a2 (x‐x1)(x‐x2)
– El mínimo del polinomio puede obtenerse fácilmente
dq(x) / dt = a1+ a2 (x‐x2) + a2 (x‐x1) = 0
x* = (x1 + x2 )/2 ‐ a1/ ( 2a2)
Métodos de aproximación por un polinomio• Método de Powell:1.‐ Elegir la estimación inicial x1 y el tamaño del paso 2.‐ Calcular x2 = x1 + Δ. Evaluar f(x1) y f(x2)3.‐ Si f(x1) > f(x2) entonces x3 = x1 + 2Δ
Si f(x1) ≤ f(x2) entonces x3 = x1 ‐ Δ4.‐ Evaluar f(x3) y determinar: Fmin = min { f(x1), f(x2), f(x3)}
xmin = punto xi correspondiente a Fmin
5.‐ Utilizar los puntos x1, x2, x3 para calcular x* utilizando la fórmula de estimación cuadrática
6.‐ Chequear la terminación: a) Es Fmin ‐ f(x*) suficientemente pequeño ?b) Es xmin ‐ x* suficientemente pequeño ?
Si se satisface terminar. De lo contrario ir a 7.7. ‐Guardar el mejor punto (xmin ó x* ), y los dos puntos que lo rodean, se reorganizan o renombran. Ir al paso 4.
Métodos numéricos (III)
• Métodos que requieren derivadas:– La función debe ser unimodal, continua y diferenciable– Si f(x) es unimodal, continua y diferenciable en [a,b], para un punto cualquiera x’ del conjunto factible se cumple:
• Si df / dx < 0 → x* ∈ (x’, b) → x* > x’• Si df / dx > 0 → x* ∈ (a, x’) → x* < x’• Si df / dx = 0 → x* ∈ (x1, x2) → x* = x’
– Métodos de eliminación:• Determinar el intervalo de incertidumbre donde está el mínimo
• Ir reduciendo el intervalo de incertidumbre hasta estimar x* con una precisión deseada, por ejemplo : ⎢∇f(x*) ⎢≈ 0
Métodos que requieren derivadas
• Método de la secante:– Estimar el siguiente punto x’ tal que ∇J(x’) ≈ 0
– Se aproxima la derivada por la secante ( la recta que pasa por los dos puntos extremos del intervalo):
x’ = b ‐ [J´(b) (b ‐ a) / (J´(b) ‐ J´(a))]
– Se aplica la propiedad de la derivada, aplicando el procedimiento hasta obtener x’ tal que ⎢∇J(x’) ⎢< ε
J`(b)
J`(a)
b
a
J`(x)
x
x’
Secante
Métodos que requieren derivadas• Método de Newton‐Raphson:
– Este método requiere que la función sea doblemente diferenciable
– Comienza con un punto x1 que es una estimación inicial (o una aproximación al punto estacionario).
– Se construye una aproximación lineal de la función J’(x) en el punto x1 y el punto donde la aproximación se haga cero se toma como la siguiente aproximación
( ) ( ) ( )( ) 0;~ '''' =−+= kkkk xxxJxJxxJ
( )( )k
kkk xJ
xJxx ''
'
1 −=+
Método de Newton‐RaphsonJ’(x)
xk+1xk
x
Objetivo
J’(x)
xk+1xk
x
xk+2
Diremos que la solución converge a un valor x* cuando la secuencia de valores xk generados por el algoritmo verifican
1c0
xxcxx *k
*1k
<<
−≤−+ A partir de un k. De modo que los puntos xk están cada vez mas próximos a x*
Inconvenientes: Si x0 esta muy alejado de x* puede no converger, o converger a otro valor