Programación Nolineal (Non Linear Programming NLP) NLP: Conjunto de técnicas para optimizar funciones no-lineales sujetas a restricciones de igualdad o desigualdad. Tanto las funciones como las restricciones pueden ser de una o más variables Formulación general de un problema de optimización Encontrar x tal que
se minimice una función objetivo f(x) sujeto a restricciones: gi(x) = bi (i=1,…, m) gj(x) ? bj (j=m,…, k)
Donde x es un vector de n variables independientes
Características de los problemas que trataremos mayormente en el curso Funciones objetivo y restricciones continuas con sus primeras derivadas parciales también continuas (suaves) Esto garantiza que pequeños cambios en x conlleve a pequeños cambios en valores asociados
Inecuaciones estrictas no son permitidas (< ó >) solo se permiten restricciones de ? , ? e ?
El problema debe ser determinístico
Todas las variables deben ser reales, ninguna puede tomar únicamente valores enteros. (Continuous Programming)
S dominio de f y gi sea una región conectada
Tipos de Problemas No-lineales Sin restricciones Con restricciones Tamaño de los Problemas Una forma de medir la complejidad de los problemas es en función del número de variables o del número de restricciones
Pequeña Escala: hasta 5 variables y restricciones ? puede ser resuelto a mano
Escala intermedia: de 5 a 100 variables y restricciones ? Computador Personal o Servidor de Propósito General
Gran Escala: más de 100 y quizás 1000 variables y restricciones ? Mainframe para cálculo científico (cray), explotando la estructura del problema con algoritmos paralelos
Tipos de Problemas No-lineales En el curso se estudiarán la teoría y los métodos que permiten efectivamente la solución de la más amplia variedad de problemas (pequeña y mediana escala principalmente) A pesar de que un gran número de algoritmos han sido propuestos para la solución del problema general de optimización no lineal, sólo unos pocos han demostrado ser efectivos cuando se aplican a problemas de “gran – escala” No existe un método general de optimización no lineal en el sentido como es SIMPLEX para problemas lineales Ninguno es tan superior para ser clasificado como la “panacea” universal de la NLP
Criterios de Comparación de Algoritmos Número de evaluaciones de la función objetivo Confiabilidad (Éxito en alcanzar la solución) Rapidez Tiempo de Preparación del usuario (sobre parametrización) Precisión de la solución Grado de satisfacción de las restricciones Dificultad
Algoritmos Iterativos y Convergencia La mayoría de los algoritmos de NLP son iterativos
En programación lineal existe una secuencia de longitud finita para alcanzar la solución En NLP la secuencia generalmente no alcanza la solución óptima sino que converge hacia ella En problemas no lineales se determina una solución lo suficientemente cercana a la óptima Solución Óptima
Algoritmos Iterativos y Convergencia La teoría de algoritmos iterativos se divide en:
Diseño del Algoritmo Convergencia Global: Análisis de convergencia global (si eventualmente converge) Convergencia Local: Análisis de convergencia local (la razón a la cual el algoritmo converge en la Solución óptima) “Una buena teoría es mejor que miles de corridas” Esto da una idea de la manejabilidad de los problemas mediante un análisis simple lo cual es muy importante
Funciones de una variable Continuidad de una función en un número Se dice que f es continua en el número a si y solo si las siguientes 3 condiciones se satisfacen:
existe existe
Discontinuidad removible Discontinuidad Esencial
| Página siguiente |