Tarea opti
!"#$%&"'(')(*+,)+*)-."(/(#*)+#*"0(
Optimización Irrestricta
Samuel Varas Facultad de Ingeniería y Ciencias Universidad Adolfo Ibáñez
Propiedades de funciones convexas
f1, f2 ,........, fk : S → R funciones convexas
i=1
Σ αi fi (x) con αi > 0, i = 1,..., k es convexa.
k
f (x) = max { f1(x), f2(x),......, fk(x)} es convexa. Si f convexa y g : R → R convexa nodecreciente, entonces h(x) = g[f (x)] es convexa.
2 Optimización - Samuel Varas
1
13/4/11
Propiedades de funciones convexas
Si f es diferenciable en x’∈S entonces:
x’ es mínimo global de f si y sólo si ∇ f (x’)(x - x’) ≥ 0 para todo x∈S.
Al avanzar desde x’ hacia x en la dirección (x- x’) la función decrece
f
no
x’
x
∇ f (x’)
3 Optimización - Samuel VarasPropiedades de funciones convexas
La función lineal f (x) = aT x + b es convexa y cóncava a la vez
4
Optimización - Samuel Varas
2
13/4/11
Condición suficiente
f : Rn → R es de clase C2.
Sea x’ tal que ∇ f (x’)=0 Si H f (x’) es definida positiva, entonces x’ es mínimo local de f
(P) Min f(x)
s.a. x ∈Rn
5
Optimización - Samuel Varas
Teorema fundamentalde programación convexa
(P) Min f(x): Rn → R
s.a. x ∈S⊂Rn S convexo; f convexa Si x es un mínimo local ⇒ x es un mínimo global El conjunto de todos los puntos mínimos es convexo
6
Optimización - Samuel Varas
3
13/4/11
Mínimo global
(P) Min f(x)
s.a. x ∈Rn
Si f es estrictamente convexa ⇒ admite a lo más UN mínimo global.
7
Optimización - Samuel Varas!"#$%&"'(')(*+,)+*)-."(/(#*)+#*"0(
Optimización Irrestricta Métodos de descenso
Samuel Varas Facultad de Ingeniería y Ciencias Universidad Adolfo Ibáñez
4
13/4/11
Estructura general de los métodos
Inicio: sea x0 el punto inicial y k=0 el índice de la iteración. Determine la dirección de descenso dk usando algún método. Encuentre el avance correcto k tal quexk+1 = xk+ kdk entregue el descenso suficiente. Sea xk+1 = xk + kdk y k = k + 1 Si || f(xk+1)|| < detenerse, en caso contrario volver al punto 2.
9
Optimización - Samuel Varas
Interpretación
Inicio el proceso en x0, el punto inicial. Luego busco la forma como avanzar, determinando la mejor (depende de cada caso) Avanzo en dicha forma, generando el nuevo punto enfunción del anterior. Verifico las condiciones de término.
10
Optimización - Samuel Varas
5
13/4/11
Dos conceptos claves
Dirección de descenso, es decir, aquella dirección que nos permite reducir el valor de la función objetivo. Paso de avance, es decir, la cantidad en que debemos movernos en la dirección de descenso.
11
Optimización - Samuel VarasConcepto de dirección de descenso
Sea f: Rn → R diferenciable, decimos que d ∈ Rn es dirección de descenso para f en x’ si
< ∇f (x� )d >< 0
Es decir, d forma ángulo agudo con -∇f (x’).
12
Optimización - Samuel Varas
6
13/4/11
Concepto de máximo avance
Un nuevo punto de la sucesión xk+1 se define de la siguiente forma
xk+1 λk
dk
xk+1 = xk +λk dk
Tal que
f (xk+1 ) ≤ f (xk )
d k+1 xk
Donde λk corresponde al paso o avance.
13
Optimización - Samuel Varas
Aspectos no resueltos aún
Determinación de la dirección de descenso dk dado un punto xk. Determinación del paso óptimo k, dada la dirección de descenso y el punto xk. Cómo se define cada uno de éstos elementos corresponde al tipo de métodoutilizado. Veremos a continuación el método de gradiente y el de Newton, existiendo varios otros.
Optimización - Samuel Varas
14
7
13/4/11
I. Método del Gradiente o del Descenso más Pronunciado de Cauchy
Del tomo primero de su Résumé des Leçons données a l’École RoyalePolytechnique, sur le Calcul Infinitésimal (1823) hemos seleccionado la Tercera Lección...
Regístrate para leer el documento completo.