Optimización con restricciones

En optimización matemática , la optimización restringida (en algunos contextos llamada optimización de restricción ) es el proceso de optimizar una función objetivo con respecto a algunas variables en presencia de restricciones en esas variables. La función objetivo es o bien una función de coste o función de energía , que ha de ser minimizado , o una función de recompensa o función de utilidad , la cual es para ser maximizado . Las restricciones pueden ser restricciones estrictas , que establecen condiciones para las variables que deben cumplirse, orestricciones blandas , que tienen algunos valores de variable que se penalizan en la función objetivo si, y en función de la medida, las condiciones de las variables no se cumplen.

Relación con los problemas de satisfacción de restricciones

El problema de optimización restringida (COP) es una generalización significativa del modelo clásico de problemas de satisfacción de restricciones (CSP). ^[1] COP es un CSP que incluye una función objetivo a optimizar. Se utilizan muchos algoritmos para manejar la parte de optimización.

Forma general

Un problema general de minimización restringida se puede escribir de la siguiente manera:

${\displaystyle {\begin{array}{rcll}\min &~&f(\mathbf {x} )&\\\mathrm {subject~to} &~&g_{i}(\mathbf {x} )=c_{i}&{\text{for }}i=1,\ldots ,n\quad {\text{Equality constraints}}\\&~&h_{j}(\mathbf {x} )\geqq d_{j}&{\text{for }}j=1,\ldots ,m\quad {\text{Inequality constraints}}\end{array}}}$

donde y son las restricciones que deben cumplirse (se denominan restricciones estrictas ) y es la función objetivo que debe optimizarse sujeta a las restricciones.${\displaystyle g_{i}(\mathbf {x} )=c_{i}~\mathrm {for~} i=1,\ldots ,n}$${\displaystyle h_{j}(\mathbf {x} )\geq d_{j}~\mathrm {for~} j=1,\ldots ,m}$${\displaystyle f(\mathbf {x} )}$

En algunos problemas, a menudo llamados problemas de optimización de restricciones , la función objetivo es en realidad la suma de las funciones de costo, cada una de las cuales penaliza el grado (si lo hay) en el que se aplica una restricción blanda (una restricción que se prefiere pero no se requiere que se satisfaga). violado.

Métodos de solución

Muchos algoritmos de optimización restringida se pueden adaptar al caso no restringido, a menudo mediante el uso de un método de penalización . Sin embargo, los pasos de búsqueda tomados por el método no restringido pueden ser inaceptables para el problema restringido, lo que lleva a una falta de convergencia. Esto se conoce como efecto Maratos. ^[2]

Restricciones de igualdad

Método de sustitución

Para problemas muy simples, digamos una función de dos variables sujetas a una única restricción de igualdad, es más práctico aplicar el método de sustitución. ^[3] La idea es sustituir la restricción en la función objetivo para crear una función compuesta que incorpore el efecto de la restricción. Por ejemplo, suponga que el objetivo es maximizar sujeto a . La restricción implica , que se puede sustituir en la función objetivo para crear . El primer orden condición necesaria da , que puede ser resuelto para y, en consecuencia, .${\displaystyle f(x,y)=x\cdot y}$${\displaystyle x+y=10}$${\displaystyle y=10-x}$${\displaystyle p(x)=x(10-x)=10x-x^{2}}$${\displaystyle {\frac {\partial p}{\partial x}}=10-2x=0}$${\displaystyle x=5}$${\displaystyle y=10-5=5}$

Multiplicador de Lagrange

Si el problema restringido solo tiene restricciones de igualdad, se puede utilizar el método de los multiplicadores de Lagrange para convertirlo en un problema no restringido cuyo número de variables es el número original de variables más el número original de restricciones de igualdad. Alternativamente, si las restricciones son todas restricciones de igualdad y son lineales, pueden resolverse para algunas de las variables en términos de las otras, y la primera puede ser sustituida fuera de la función objetivo, dejando un problema sin restricciones en un número menor de variables.

Restricciones de desigualdad

Con restricciones de desigualdad, el problema puede caracterizarse en términos de las condiciones de optimización geométrica , las condiciones de Fritz John y las condiciones de Karush-Kuhn-Tucker , bajo las cuales los problemas simples pueden resolverse.

Programación lineal

Si la función objetivo y todas las restricciones estrictas son lineales y algunas restricciones estrictas son desigualdades, entonces el problema es un problema de programación lineal . Esto puede resolverse mediante el método simplex , que generalmente funciona en tiempo polinomial en el tamaño del problema pero no está garantizado, o mediante métodos de puntos interiores que están garantizados para trabajar en tiempo polinomial.

Programación no lineal

Si la función objetivo o algunas de las restricciones no son lineales y algunas restricciones son desigualdades, entonces el problema es un problema de programación no lineal .

Programación cuadrática

Si todas las restricciones estrictas son lineales y algunas son desigualdades, pero la función objetivo es cuadrática, el problema es un problema de programación cuadrática . Es un tipo de programación no lineal. Todavía se puede resolver en tiempo polinomial mediante el método elipsoide si la función objetivo es convexa ; de lo contrario, el problema puede ser NP difícil .

Condiciones del KKT

Al permitir restricciones de desigualdad, el enfoque KKT de la programación no lineal generaliza el método de los multiplicadores de Lagrange. Se puede aplicar bajo diferenciabilidad y convexidad.

Ramificar y encuadernar

La optimización de restricciones se puede resolver mediante algoritmos de bifurcación y enlace . Estos son algoritmos de retroceso que almacenan el costo de la mejor solución encontrada durante la ejecución y lo usan para evitar parte de la búsqueda. Más precisamente, siempre que el algoritmo encuentra una solución parcial que no puede extenderse para formar una solución de mejor costo que el mejor costo almacenado, el algoritmo retrocede, en lugar de intentar extender esta solución.

Suponiendo que se minimice el costo, la eficiencia de estos algoritmos depende de cómo se evalúe el costo que se puede obtener al extender una solución parcial. De hecho, si el algoritmo puede retroceder desde una solución parcial, se omite parte de la búsqueda. Cuanto menor sea el costo estimado, mejor será el algoritmo, ya que es más probable que un costo estimado menor sea menor que el mejor costo de solución encontrado hasta ahora.

Por otro lado, este costo estimado no puede ser menor que el costo efectivo que se puede obtener extendiendo la solución, ya que de lo contrario el algoritmo podría dar marcha atrás mientras existe una solución mejor que la mejor encontrada hasta ahora. Como resultado, el algoritmo requiere un límite superior en el costo que se puede obtener al extender una solución parcial, y este límite superior debe ser lo más pequeño posible.

Una variación de este enfoque llamada método de Hansen utiliza métodos de intervalo . ^[4] Implementa inherentemente restricciones rectangulares.

Funciones de delimitación de primera elección

Una forma de evaluar este límite superior para una solución parcial es considerar cada restricción blanda por separado. Para cada restricción blanda, se asume el valor máximo posible para cualquier asignación a las variables no asignadas. La suma de estos valores es un límite superior porque las restricciones suaves no pueden asumir un valor más alto. Es exacto porque los valores máximos de restricciones suaves pueden derivar de diferentes evaluaciones: una restricción suave puede ser máxima para mientras que otra restricción es máxima para .${\displaystyle x=a}$${\displaystyle x=b}$

Búsqueda de muñecas rusas

Este método ^[5] ejecuta un algoritmo de bifurcación y vinculación en problemas, donde es el número de variables. Cada uno de estos problemas es el subproblema que se obtiene al eliminar una secuencia de variables del problema original, junto con las restricciones que las contienen. Una vez que se resuelve el problema de las variables , su costo óptimo se puede utilizar como límite superior mientras se resuelven los otros problemas,${\displaystyle n}$${\displaystyle n}$${\displaystyle x_{1},\ldots ,x_{i}}$${\displaystyle x_{i+1},\ldots ,x_{n}}$

En particular, al costo que se deriva de las variables evaluadas se suma la estimación del costo de una solución que tiene como variables no asignadas. Prácticamente, esto corresponde a ignorar las variables evaluadas y resolver el problema en las no asignadas, excepto que este último problema ya está resuelto. Más precisamente, el costo de las restricciones blandas que contienen variables asignadas y no asignadas se estima como se indicó anteriormente (o utilizando otro método arbitrario); en cambio, el costo de las restricciones blandas que contienen solo variables no asignadas se estima utilizando la solución óptima del problema correspondiente, que ya se conoce en este momento.${\displaystyle x_{i+1},\ldots ,x_{n}}$

Existe una similitud entre el método de búsqueda de muñecas rusas y la programación dinámica . Al igual que la programación dinámica, Russian Doll Search resuelve subproblemas para resolver todo el problema. Pero, mientras que la Programación dinámica combina directamente los resultados obtenidos en los subproblemas para obtener el resultado de todo el problema, Russian Doll Search solo los usa como límites durante su búsqueda.

Eliminación de cubo

El algoritmo de eliminación de cubos se puede adaptar para optimizar las restricciones. De hecho, una variable dada puede eliminarse del problema reemplazando todas las restricciones suaves que la contienen por una nueva restricción suave. El costo de esta nueva restricción se calcula asumiendo un valor máximo para cada valor de la variable eliminada. Formalmente, si es la variable que se eliminará, si las restricciones suaves la contienen y son sus variables , excepto que la nueva restricción suave se define mediante:${\displaystyle x}$${\displaystyle C_{1},\ldots ,C_{n}}$${\displaystyle y_{1},\ldots ,y_{m}}$${\displaystyle x}$

${\displaystyle C(y_{1}=a_{1},\ldots ,y_{n}=a_{n})=\max _{a}\sum _{i}C_{i}(x=a,y_{1}=a_{1},\ldots ,y_{n}=a_{n}).}$

La eliminación de cubos funciona con un orden (arbitrario) de las variables. A cada variable se le asocia un conjunto de restricciones; el cubo de una variable contiene todas las restricciones que tienen la variable más alta en el orden. La eliminación del cubo procede de la última variable a la primera. Para cada variable, todas las restricciones del depósito se reemplazan como se indicó anteriormente para eliminar la variable. Luego, la restricción resultante se coloca en el contenedor apropiado.

Ver también

• Mínimos cuadrados restringidos
• Optimización de restricciones distribuidas
• Problemas de satisfacción de restricciones (CSP)
• Programación de restricciones
• Programación de enteros
• Método de penalización
• Superiorizacion

Referencias

1. Rossi, Francesca; van Beek, Peter; Walsh, Toby (1 de enero de 2006), Rossi, Francesca; van Beek, Peter; Walsh, Toby (eds.), "Chapter 1 - Introduction" , Foundations of Artificial Intelligence , Handbook of Constraint Programming, Elsevier, 2 , págs. 3-12, doi : 10.1016 / s1574-6526 (06) 80005-2 , recuperado 2019-10-04
2. Wenyu Sun; Ya-Xiang Yua (2010). Teoría y métodos de optimización: programación no lineal , Springer, ISBN 978-1441937650 . pag. 541 
3. Prosser, Mike (1993). "Optimización restringida por sustitución". Matemáticas básicas para economistas . Nueva York: Routledge. págs. 338–346. ISBN 0-415-08424-5.
4. Líder, Jeffery J. (2004). Análisis numérico y computación científica . Addison Wesley. ISBN 0-201-73499-0.
5. Verfaillie, Gérard, Michel Lemaître y Thomas Schiex. " Búsqueda de muñecas rusas para resolver problemas de optimización de restricciones ". AAAI / IAAI, vol. 1. 1996.

Lectura adicional

• Bertsekas, Dimitri P. (1982). Optimización restringida y métodos de multiplicador de Lagrange . Nueva York: Academic Press. ISBN 0-12-093480-9.
• Dechter, Rina (2003). Procesamiento de restricciones . Morgan Kaufmann. ISBN 1-55860-890-7.