• Author / Uploaded
• radioactive

Citation preview

REPÚBLICA BOLIVARIANA DE VENEZUELA MINISTERIO DEL PODER POPULAR PARA LA EDUCACIÓN UNIVERSITARIA INSTITUTO UNIVERSITARIO POLITÉCNICO “SANTIAGO MARIÑO” EXTENSIÓN MATURÍN

OPTIMIZACIÓN SIN RESTRICCIONES EN FUNCIONES DE VARIAS VARIABLES

Autores: Nathalie Rivas C.I: 25.581.359 Asesor: Ing. Diógenes Rodriguez

Maturín, Julio 2020

INTRODUCCIÓN En optimización sin restricciones se minimiza una función objetivo que depende de variables reales sin restricciones sobre los valores de esas variables. Los métodos sin restricciones son importantes ya que existen problemas que se pueden formular sin restricciones. Permiten introducir muchos conceptos y explorar ideas que se usarán en problemas. Muchos problemas de optimización utilizan en alguna fase algoritmos sin restricciones y algunos problemas NLP pueden reformularse a tráves de la utilización de estos métodos.

Se describen a continuación algunos de los métodos numéricos básicos utilizados en la resolución de problemas no lineales sin restricciones en varias variables. Prácticamente para todos los métodos existe una estructura fundamental. El algoritmo comienza desde un punto inicial, a continuación se determina mediante una regla una dirección de movimiento, y se sigue en esa dirección hasta llegar a un mínimo (relativo) de la función objetivo sobre esa recta. En ese nuevo punto se determina una nueva dirección utilizando la misma regla anterior y se repite el proceso. Como se puede suponer la diferencia entre los métodos radica en la regla mediante la cual se selecciona la dirección de movimiento en cada paso del algoritmo. El proceso de búsqueda del mínimo sobre la recta se llama búsqueda lineal. Una vez fijada la dirección de movimiento, el valor de la función objetivo depende solamente de una variable, que es precisamente la longitud recorrida en la dirección elegida, y sobre esta función “univariante” se pueden utilizar los algoritmos de búsqueda descritos en el tema anterior para funciones de este tipo.

Método de Ascenso y/o Descenso Acelerado En la iteración k+1, el cálculo del punto x k+1 a partir del xk, se realiza mediante la siguiente expresión: xk+1 = xk + Δxk = xk + λkśk = xk + λ*ksk Donde: Δxk = vector que va de xk a xk+1 śk = vector unitario en la dirección Δxk sk = cualquier vector en la dirección Δxk λk , λ*k = escalares El gradiente de la función objetivo f(x), en cualquier punto x, es un vector cuya dirección es la de mayor crecimiento local de f(x). Obviamente, se podría utilizar la dirección opuesta del gradiente de f(x), es decir la dirección de descenso acelerado, pues el vector opuesto al gradiente de f(x) en xk, apunta en la dirección mayor de crecimiento de f(x) y es ortogonal al contorno de f(x) en xk. La dirección de descenso acelerado (vector normalizado) se calcula mediante la expresión:

Por lo tanto, en el método de descenso acelerado, la transición de x k a xk+1 se calcula mediante la siguiente expresión:

El gradiente negativo nos dará la dirección para optimizar, pero no la magnitud del paso a tomar; por ello, son posibles varios procedimientos de descenso acelerado, dependiendo de la elección de λ. Como el método de descenso acelerado puede finalizar en cualquier tipo de punto estacionario (donde los elementos del gradiente de f(x) son cero), es necesario determinar si el punto es un mínimo local (es decir, una solución) o un punto de silla. Si es un punto de silla, es preciso emplear un método que no utilice gradientes para alejarse del punto, después de lo cual la minimización puede seguir con el método de descenso acelerado. Se pueden emplear varias reglas para finalizar la serie de iteraciones del método de descenso acelerado basadas, ya sea, en el valor de f(x), de x, de x, de λ, mientras que en el segundo se selecciona un valor fijo o variable de λ. Método de Davidon Fletcher Powell

El método de Davidon-Fletcher-Powell ha sido y sigue siendo una técnica de gradiente ampliamente utilizada. El método tiende a serrobusto; esto es, típicamente tiende a tener un buen comportamiento en una amplia variedad de problemas prácticas. La mayor desventaja de este tipo de métodos es su necesidad de almacenar la matriz A de N×N.

Este es un método cuasi-Newton, para minimizar una función f en Rn. Consiste en generar aproximaciones sucesivas de la inversa del Hessiano de la función f. Definamos: gk := ∇f(xk) Hk := aproximaciones de la inversa del Hessiano en xk dk := − Hkgk qk := gk+1 − gk

pk := xk+1 − xk En cada iteración se genera: xk + 1 = xk + αkdk con αk = arg mín α ≥ 0 f(xk+αdk). El procedimiento es el siguiente:

Paso 0: Partir con cualquier matriz H0 definida positiva y algún x0, conk= 0. Paso 1: Tomar dk = −Hkgk. Paso 2: Calcular αk = arg mín α ≥ 0 f(xk + αdk) y obtener xk + 1, pk y gk +1. Paso 3: Tomar qk = gk + 1 − gky

k = k + 1 y retornar al Paso 1.

Método de Fletcher Reeves

Este método está basado en la lógica de las direcciones conjudas y es producto del trabajo de Fletcher y Reeves. Este procedimiento genera una sucesión de direcciones de búsqueda sk que son combinaciones lineales del vector opuesto al gradiente de f(x) en el punto xk (dirección de descenso acelerado) y de s0,…,sk-1 (direcciones de búsqueda anteriores). Los coeficientes usados hacen que las direcciones de búsqueda sean conjugadas. Dichos coeficientes se calculan de tal forma que, en x k, se usará solamente el gradiente actual y el gradiente más reciente para calcular la nueva dirección de búsqueda.

En general, un conjunto de n direcciones de búsqueda linealmente independientes s0, s1 ,…., sn-1 se dicen que son conjugadas con respecto a una matriz (cuadrada) definida positiva Q si:

(si)T Qsi = 0 ; 0 ≤ i ≠ j ≤ n – 1

Un ejemplo de Q, es la matriz hessiana de la función objetivo (H). La conjugacidad es bastante análoga a la ortogonalidad; de hecho cuando H=I, la ecuación anterior se convierte en esta otra: (si)T si = 0 ; 0 ≤ i ≠ j ≤ n – 1 La transición de xk a xk+1 se realiza mediante la siguiente expresión: xk+1 = xk + ƛks Siendo sk:

Y s0 (la dirección inicial de búsqueda):

Las ecuaciones anteriores se aplican iterativamente, como en los métodos precedentes, hasta que se cumpla algún criterio de finalización. En el método de Fletcher-Reeves la selección del parámetro ƛk se realiza de la misma forma que en el método de descenso acelerado.

Este procedimiento no es tan eficiente como el método de Davido-FletcherPowell pero resulta más sencillo de utilizar. Además es mucho más eficiente que el método de ascenso-descenso acelerado. Corresponde a la versión del método del gradiente conjugado en el caso de una función f general. La iteración se define de la siguiente manera:

Método de Direcciones Conjugadas

Una de las propiedades más importantes del método de gradiente es su habilidad de generar direcciones conjugadas de una manera muy económica. Un conjunto de vectores {p0,p1,...pl} es llamado conjugado respecto a una matriz definida positiva A, si :

La importancia de las direcciones conjugadas radica en el hecho de que podemos minimizar φ(·) en n pasos por la sucesiva minimización a lo largo de direcciones individuales en un conjunto conjugado. Para verificar esto, consideremos el siguiente método de direcciones conjugadas. Dado

un

punto

inicial

x(0)∈Rny

un

conjunto

de

direcciones

{p(0),p(1),...,p(n−1)}. Consideraremos la siguiente secuencia generadora {x(k)}:

Donde α(k) es el minimizador de la función cuadrática φ(·) a lo largo de x (k)+ αp(k)dada explícitamente por:

con r(k) = ∇φ(x(k)) = Ax(k) − b Teorema:

Para cualquier x(0)∈Rn la secuencia {xk} generada por el algoritmo de direcciones conjugadas converge a la solución x* de un sistema lineal en no más de n pasos.

Para algún escalar σ(k). Pre–multiplicando la expresión por p(k)TA y utilizando la propiedad del conjugado tenemos:

Ahora estableceremos el resultado mostrando que este coeficiente coincide con la longitud de paso αk. Si x(k) es generado por la sucesión x(k+1) = x(k) + σ(k)p(k) tenemos:

Pre multiplicando esta expresión por p(k)TA y utilizando la propiedad del conjugado tenemos:

Adicionalmente:

Y por lo tanto:

Comparando ambas relaciones tenemos que α(k) = σ(k). Hay una interpretación simple de las direcciones conjugadas. Si la matriz A es diagonal los contornos de la función φ(·) son elipses cuyos ejes están alineados con los ejes coordenados. Podemos encontrar el mínimo de esta función con una búsqueda lineal a lo largo de los ejes coordenados. Cuando A no es una diagonal, sus contornos son elípticos, pero ellos no están alineados en la dirección de los ejes coordenados. La estrategia de minimizaciones sucesivas a lo largo de estas direcciones no da una solución en n iteraciones.

Ejemplo de como trabajan las direcciones conjugadas

BIBLIOGRAFÍA

•

http://delta.cs.cinvestav.mx/~ccoello/optimizacion/clase12-opt-2009.pdf

•

https://books.google.co.ve/books? id=UATsv3bgBwcC&pg=PA44&lpg=PA44&dq=metodo+de+ascenso+y+desc enso+acelerado&source=bl&ots=feZGoBH1Rz&sig=ACfU3U3H2tFppMEfT iW0KtooksyPTAlj9A&hl=es&sa=X&ved=2ahUKEwjIh9Ky283qAhUQTt8K HWwLAYAQ6AEwBXoECAkQAQ#v=onepage&q=metodo%20de %20ascenso%20y%20descenso%20acelerado&f=false

•

https://www.fio.unicen.edu.ar/usuario/cgely/q13-0/Apuntes/unidad4.pdf

•

https://lc.fie.umich.mx/~calderon/optimizacion/notas/optimizacion.pdf