02 ricardo coronado leija

5/11/2018 02 Ricardo Coronado Leija - slidepdf.com

http://slidepdf.com/reader/full/02-ricardo-coronado-leija 1/3

Método de DoglegOptimización Tarea 2

Ricardo Coronado Leija

Maestría en Ciencias de la Computación y Matemáticas Industriales

Centro de Investigación en Matemáticas

Guanajuato, Guanajuato

[email protected]

Abstract — Ajuste de un señal por medio de suma de Gaussianas

(Funciones de base Radial) utilizando Métodos de Región de

Confianza en Particular el Método de Dogleg por medio de una

aproximación por medio de un modelo cuadrático

I NTRODUCCION

En este trabajo se implementó el Método de Dogleg paraminimizar una función que resulta de una suma de diferenciascuadradas entre una señal y una suma de Funciones de BaseRadial Gaussianas, con el objetivo de aproximar la señal por medio de estas.

En las siguientes secciones se describe el procedimiento ylos resultados.

A. Problema

El objetivo del este trabajo es minimizar la siguientefunción:

utilizando el Método de Dogleg.

B. Metodo de Dogleg

En el método de región de confianza el primer paso es

encontrar el pk que minimice el siguiente modelo cuadrático

mk :

el Método de Dogleg realiza esto analizando varias

alternativas para el paso pk tratando de seleccionar la mejor. Elalgoritmo es el siguiente:

si k

U p ∆≥ entonces k U

U

k p

p p ∆←

sino k k

B g B p 1−←

si k

B p ∆≤ entonces

B

k p p ←

sino ( )U BU

k p p p p −+= τ

donde τ se obtiene resolviendo:

el pk obtenido de este algoritmo es el paso para ir minimizandola función y es el que será evaluado en el algoritmo de región

de confianza para ver si se aumenta o disminuye el radio de

esta región.

C. Metodo de Región de Confianza

Habiendo obtenido el tamaño del paso pk se analiza de

acuerdo a este si es prudente aumentar, disminuir o dejar igual

el tamaño del radio de la región, para ello se calcula la

relación:

y a partir del valor de esta se toma una decisión. El algoritmo

de región de confianza queda:

Dado

Para k = 0, 1, 2, 3,…..

Obtener pk que minimiza mk

Evaluar ρ k

Si ρ k < ¼

sino

si

entonces

sino

si entonces

sino

( ) ∆≤+∇+=∈

p p B p p f f pm k

T T

k k k R p n

s.a. 2

1min

g Bg g

g g p

T

T U

−=

( ) 22

∆=−+U B

U p p p τ

( ) ( )( ) ( )

k k k

k k k k

pmm

p x f x f

−

+−=

0 ρ

( ) [ )4/1,0,,0,0 0 ∈∆∈∆>∆ η

k k p4

11 =∆

+

k k k p ∆=> y4/3 ρ

( )∆∆=∆+

,2min1 k k

k k ∆=∆+ 1

η ρ >k k k k p x x +=+ 1

k k x x =+ 1



IMPLEMENTACION

Para el manejo de matrices y vectores, incluyendo las

operaciones fundamentales, se utilizaron un conjunto de

funciones creadas en la material de Algebra Lineal Numérica,

las cuales se encuentran en FuncionesALN.cpp. Para calcular

el gradiente y la hessiana se aproximaron mediante diferencias

finitas, las funciones de región de confianza y método dogleg

se encuentran en T_2.cpp, donde también está el main. D. Detalles del uso del programa

Ya que para la realizar el programa se utilizó devcpp enwindows, se creó un proyecto .dev que agrupa T_2.cpp,FuncionesALN.h y FuncionesALN.cpp. Al correr el programase muestran los valores iniciales de Bk y C k y cuando acabe deejecutarse se mostraran los valores Bk y C k calculados. Tambiénse crea un archivo puntos.r para graficar los las funcionesgaussianas y la suma de estas en el programa R.

RESULTADOS

A continuación mostramos los resultados del programautilizando los 3 diferentes conjuntos de datos de prueba dadosen la página de la ayudantía:

E. Datos 1

Para los datos de prueba 1, se obtuvieron el siguiente valor

para las constantes Bk y C k :

Iteraciones: 165

Constantes Bk Finales

Vector:

0.999718 0.994088 1.00142 1.00474 1.00004

Constantes Ck Finales

Vector:

19.9958 46.9618 77.9874 58.9383 111.999

Las gráficas de las gaussianas separadas se muestran en la

Figura 1 a), y la suma de estas se muestra en la Figura 1 b).

a) b)Figura 1: Graficas de los resultados para los datos 1

F. Datos 2

Para los datos de prueba 2, se obtuvieron el siguiente valor

para las constantes Bk y C k :

Iteraciones: 12477


Vector:

0.267168 0.0242144 0.12238 0.414581

0.171316


Vector:

78.0341 20.1243 46.9937 112.003 59.1229

Las gráfica de la suma de las funciones gaussianas se muestraen la Figura 2.

Figura 2

G. Datos 3

Para los datos de prueba 3, se obtuvieron el siguiente valor para las constantes Bk y C k :

Iteraciones: 1000


Vector:

0.969147 1.00611 1.00964 1.02026 0.996721


Vector:

78.1519 47.0681 111.897 59.2003 20.2603

Las gráficas de las gaussianas separadas se muestran en la

Figura 3 a), y la suma de estas se muestra en la Figura 3 b).

a) b)

Figura 3: Graficas de los resultados para los datos 3

CONCLUSIONES

Se pudo observar en las gráficas que las aproximaciones delas funciones radiales a las señales fueron bastante buenas, por lo que si se minimiza la función y el tiempo de ejecución fue

bueno tomando en cuenta que se trata de un problema de 10dimensiones.

[1] J. Nocedal and S. J. Wright, “Numerical Optimization”, Springer, 2006. pp.65–73.

02 ricardo coronado leija

Documents