Arquitectura Avanzadas Y Comerciales

Método de optimización sin restricciones

En sentido general, se llama optimización al proceso de encontrar la mejor solución a un determinado problema. En un sentido más restringido, en este tema se entiende por optimización el proceso encontrar los valores mínimos de una función de n variables f(x) en un dominio que puede ser Rn.Un gran número de problemas de Ingeniería se pueden formular de esta forma. Función objetivo, variables de diseño, restricciones.

La función f(x) a optimizar se suele denominar función objetivo. Es muy importante la formulación matemática de esta función, así como el cálculo de sus derivadas de primer y segundo orden. Las variables de las que depende la función objetivo se llaman variables de diseño y se agrupan en un vector x∈RnCon frecuencia las variables de diseño deben satisfacer ciertas restricciones, de igualdad o desigualdad. En este tema se supondrá que no hay restricciones.

Método del gradiante conjugado

En matemática, el método del gradiente conjugado es un algoritmo para resolver numéricamente los sistemas de ecuaciones lineales cuyas matrices son simétricas y definidas positivas. Es un método iterativo, así que se puede aplicar a los sistemas dispersos que son demasiado grandes para ser tratados por métodos directos como la descomposición de Cholesky. Tales sistemas surgen frecuentemente cuando se resuelve numéricamente las ecuaciones en derivadas parciales.

El método del gradiente conjugado se puede utilizar también para resolver los problemas de optimización sin restricciones como la minimización de la energía.

El método del gradiente biconjugado proporciona una generalización para matrices no simétricas. Varios métodos del gradiente conjugado no lineales buscan los mínimos de las ecuaciones no lineales

Descripción del método

Supongamos que queremos resolver el siguiente sistema de ecuaciones lineales

Ax = b

Donde la n-por-n matriz A es simétrica (i.e., AT = A), definida positiva (i.e., xTAx > 0 para todos los vectores no cero x en Rn), y real.

Denotamos la única solución de este sistema por x*.

El método de gradiente conjugado como un método exacto

Decimos que dos vectores no cero u y v son conjugados (con respecto a A) si

Ya que A simétrica y definida positiva, el lado izquierdo define un producto interior

Así, dos vectores son conjugados si son ortogonales con respecto a este producto interior. La conjugación es una relación simétrica: si u es conjugado a v, entonces v es conjugado a u. Nótese que esta noción de conjugación no se relaciona con la de conjugación compleja.

Supongamos que {pk} es una secuencia de n direcciones mutuamente conjugadas. Entonces los pk forman una base de Rn, por lo tanto podemos extender la solución x* de Ax = b en esta base:

Los coeficientes se dan por

Este resultado es quizás muy transparente si se considera el producto interior definido anteriormente.

Esto da el siguiente método para resolver la ecuación Ax = b. Primero encontramos una secuencia de n direcciones conjugadas y luego computamos los coeficientes αk.

Método de Davidon – Fletcher – PoweEl

Método de Davidon-Fletcher-Powell ha sido y sigue siendo una técnica degradiente ampliamente utilizada. El método tiende a ser robusto; 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 NxN. Una de las dificultades practicas comunes de estos métodos es la tendencia de A (K+1) a estar mal condicionada, lo que causa una mayor dependencia a un procedimiento de Re inicialización.

Método de optimización con restricciones, el problema de optimización no lineal con restricciones Lagranje

En los problemas de optimización, el método de los multiplicadores de Lagrange, llamados así en honor a Joseph Louis Lagrange, es un procedimiento para encontrar los máximos y mínimos de funciones de varias variables sujetas a restricciones. Este método reduce el problema restringido con n variables a uno sin restricciones de n + k variables, donde k es igual al número de restricciones, y cuyas ecuaciones pueden ser resueltas más fácilmente. Estas nuevas variables escalares desconocidas, una para cada restricción, son llamadas multiplicadores de Lagrange. El método dice que los puntos donde la función tiene un extremo condicionado con k restricciones, están entre los puntos estacionarios de una nueva función sin restricciones construida como una combinación lineal de la función y las funciones implicadas en las restricciones, cuyos coeficientes son los multiplicadores.

La demostración usa derivadas parciales y la regla de la cadena para funciones de varias variables. Se trata de extraer una función implícita de las restricciones, y encontrar las condiciones para que las derivadas parciales con respecto a las variables independientes de la función sean iguales a cero.

Sea f (x) una función definida en un conjunto abierto n-dimensional {x ∈ Rn}. Se definen s restricciones gk (x) = 0, k=1,..., s, y se observa (si las restricciones son satisfechas) que:

Se procede a buscar un extremo para h

lo que es equivalente a

DIRECCIONES FACTIBLES

Métodos de Direcciones Factibles

Sea (P):

(P) m´ın f(x)

s.a x ∈ S

Un vector d es llamado dirección factible en x ∈ S si:

∃ UN δ > 0 tal que (x + λd) ∈ S, ∀ λ ∈ (0, δ).

Además se dice que es de mejoramiento si:

∃ un δ > 0 tal que f(x + λd) < f(x) y (x + λd) ∈ S, ∀ λ ∈ (0, δ).

¿Qué hace el método?

En cada iteración genera una dirección factible de mejoramiento y luego optimiza a lo largo de

Esa dirección.

Lema

Consideremos un problema de la forma:

(P) m´ın f(x)

s.a Ax ≤ b

Ex = e

Sea x una solución factible y, A1x = b1 y A2x < b2. Luego un vector d es una dirección factible

En x si y solo si A1d ≤ 0 ∧ Ed = 0.

Si _f(x) d < 0, es una dirección de mejoramiento.

CONDICION KA- KUHN-TUCKER

En

...