Optimización global
# Optimización global

Optimización Global es una rama de la matemática aplicada y el análisis numérico que se ocupa de la optimización de una función o un conjunto de funciones de acuerdo a diferentes criterios.

Por lo general, un conjunto de cotas y restricciones más generales también se encuentra presente, siendo las variables de decisión optimizadas de acuerdo a las restricciones.

## General

Un modelo en su forma estándar es la minimización de una función real $f$ en el espacio de los parámetros ${\vec {x}}\in P$, o en el subespacio definido por las restricciones $D$. (El problema de maximizar la función $g(x)$ es equivalente a minimizar una función $f(x)=(-1)\cdot g(x)$.)

En muchos problemas de optimización no linear, la función objetivo $f$ tiene un gran número de mínimos y máximos locales, encontrar un óptimo local es una tarea sencilla, usando métodos clásicos de optimización local.En estos caso encontrar un mínimo o un máximo global es una tarea de mayor complejidad, pues los métodos analíticos no se pueden utilizar en la gran mayoría de los casos y las estrategias numéricas traen consigo un número grande de problemas.

## Aplicaciones

Algunos de los casos en los que se debe usar un enfoque de optimización global son:

* Predicción de la estructura de las proteínas (minimizar la energía/función de energía libre).
* Filogenética computacional (por ejemplo, minimizar el número de transformaciones de caracteres del árbol).
* Problema del viajante y el diseño de circuitos eléctricos (minimizar la longitud del camino).
* Ingeniería química (por ejemplo, Analizar la energía libre de Gibbs).
* Verificación de seguridad, ingeniería de seguridad (por ejemplo, de estructuras mecánicas, edificios).
* Análisis del caso peor
* Problemas matemáticos (por ejemplo, la Conjetura de Kepler).
* El punto de partida de numerosas simulaciones dinámicas moleculares que consisten en una optimización inicial de la energía del sistema a ser simulado.
* Calibración de los modelos de propagación de radio y otros modelos en la ciencia y en la ingeniería
* Ajuste de curvas como el análisis mínimo cuadrático y otras generalizaciones, como el ajuste de los datos de modelos experimentales, en la química, física, medicina, astronomía y otros.

## Métodos deterministas

Las estrategias más usadas son:

### Inner and outer approximation

En ambas estrategias, el conjunto sobre el que las funciones va a ser optimizadas es un poliedro. En la aproximación interior el poliedro es contenido en el conjunto, mientras en la aproximación exterior el poliedro contiene al conjunto.

### Cutting planes

El cutting planes es un término global para los métodos de optimización que iterativamente refinan un conjunto factible o la función objetivo añadiéndole desigualdades lineales, llamadas cortes. Estos procedimientos son muy utilizados para encontrar soluciones enteras y soluciones enteras mixtas de problemas de programación lineal, así como resolver problemas generales de optimización convexos, no necesariamente diferenciable function by means of linear inequalities, termed cuts. El uso de planos cortantes para resolver problemas de optimización lineal mixtos fue introducido por Ralph E. Gomory and Václav Chvátal.

### Branch and bound

Branch and bound es un paradigma de los algoritmos diseñados para la optimización de problemas discretos y combinatorios. Un algoritmo de ramificación y acotación consiste en la enumeración sistemática de soluciones candidatas del espacio de búsqueda.El algoritmo explora las ramas del árbol, que representan un subconjunto de las soluciones. Antes de las soluciones candidatas de la rama, la rama es revisada contra las diferentes acotaciones de la solución óptima, y descartadas si no pueden producir una mejor solución que la mejor encontrada hasta ahora.

### Interval arithmetic

Interval arithmetic es un método desarrollado por los matemáticos desde los años 50 del siglo pasado como un enfoque para añadir cotas en los errores de redondeo y la medición de errores en problemas de matemática computacional en el desarrollo de métodos numéricos que lleven a resultados confiables.La aritmética de intervalos ayuda a encontrar soluciones confiables a ecuaciones y problemas de optimización.

### Real álgebra

Real algebra es la parte del álgebra que es relevante a la geometría real algebraica y semi algebraica. En su mayoría le concierne al estudio de los campos ordenados o de los anillos ordenados, y su aplicación al estudio de polinomios positivos y la suma de los polinomios al cuadrado. Puede ser usado en la optimización convexa.

## Métodos estocásticos

Muchos algoritmos basados en Monte-Carlos existen:

### Simulated annealing

Simulated annealing (SA)' es una metaheurística probabilística para la optimización global de problemas de encontrar una buena aproximación del optimo global de una función dada en un espacio de búsqueda grande. Es a menudo usado si el espacio de búsqueda es discreto. Para ciertos problemas simulated annealing es más eficiente que la enumeración exhaustiva, poniendo que el objetivo es encontrar una solución aceptable en un espacio de tiempo pequeño más que encontrar la mejor solución posible.

### Método de muestreo directo de Monte-Carlo

En este método, simulaciones aleatorias son utilizadas para utilizar soluciones aproximadas Ejemplo: El problema del viajante es uno de los problemas de optimización más famosos, cuyo objetivo es encontrar el camino óptimo a seguir que cumpla con que se recorrió la menor distancia posible. Asumamos que en vez de minimizar la distancia total del viajero para visitar cada ciudad, queremos minimizar el tiempo necesitado para llegar a cada destino. Esto va más allá de la optimización convencional. Como resultado para determinar este nuevo camino optimal querríamos usar simulación-optimización para entender el rango de tiempos potenciales que podría tomar ir de un punto a otro y entonces optimizar nuestras decisiones de viaje para identificar el mejor camino a seguir tomando en cuenta la incertidumbre.

### Stochastic tunneling

Stochastic tunneling (STUN) es un acercamiento a la optimización global basado en el método de muestreo de Monte-Carlo de la función objetivo a ser minimizada en el cual la función es transformada no linealmente para permitir un fácil tunneling entre las regiones que contienen mínimo de función. Un tunneling más sencillo permite una exploración más rápida del espacio muestral así como una convergencia más rápida hacia buena solución.

### Parallel tempering

Parallel tempering es método de simulación dirigido a mejorar las propiedades dinámicas del método de Monte Carlo de simulación de sistemas físicos. Esencialmente, se corren N copias del sistema, inicializados de manera aleatoria a diferentes temperaturas.La idea de este método es hacer disponibles las configuraciones a altas temperaturas a las simulaciones de bajas temperaturas y viceversa. Esto resulta en un conjunto robusto el cual es posible muestrear tanto configuraciones de bajas y altas temperaturas

## Heurísticas y metaheurísticas

Otros acercamientos incluyen estrategias heurísticas para buscar en el espacio de búsqueda en una manera más inteligente, entre ellos:

* Algoritmos evolutivos(e.g., genetic algortihms y estrategias evolutivas)
* Swarm-based optimization algortihms(e.g., particle swarm optimization, multi-swarm optimization y ant colony optimization)
* Memetic algorithms, combinando estrategias de búsqueda local y global
* Reactive search optimization
* Differential evolution, un método que optimiza un problema mejorando la solución iterativamente teniendo en cuenta una medida de calidad.
* Graduated optimization, técnica que trata de resolver un problemas de optimización complejos, resolviendo primero una versión más simple del mismo y transformándolo progresivamente (mientras se optimiza) en un problema equivalente al problema de optimización original.

## Aproximaciones basadas en metodologías de superficies de respuesta

* IOSO Optimización indirecta basada en organización propia.
* Bayesian optimization, una estrategia de diseño sequencial para problemas de optimización global donde se asume la función como una caja negra usando estadística bayesiana.

## Software

1. Libres y de código abierto:

* OpenOpt

2. Comercial:

* LIONsolver
* TOMLAB for Matlab
* Optimus platform
* The NAG Numerical Library contains routines for both global and

local optimization.

* Demo global optimization software versions are available also for a

number of commercial software products.

* XTREME a single and

multiple objective optimization software for nonlinear optimization (GUI, Excel, C/C++ API and Python)

