Tarea opti

13/4/11
 

!"#$%&"'(')(*+,)+*)-."(/(#*)+#*"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...