Optimización con restricciones

En optimización matemática , la optimización con restricciones (en algunos contextos denominada optimización con restricciones ) es el proceso de optimizar una función objetivo con respecto a ciertas variables , considerando las restricciones sobre dichas variables. La función objetivo puede ser una función de costo o de energía , que se busca minimizar , o una función de recompensa o de utilidad , que se busca maximizar . Las restricciones pueden ser estrictas , que establecen condiciones para las variables que deben cumplirse, o flexibles , que penalizan ciertos valores de las variables en la función objetivo si, y en función del grado de, incumplimiento de las condiciones sobre las variables.

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

El problema de optimización con restricciones (COP) es una generalización significativa del modelo clásico de problema de satisfacción de restricciones (CSP). ^{[ 1 ]} COP es un CSP que incluye una función objetivo que debe optimizarse. Se utilizan muchos algoritmos para abordar la parte de optimización.

Forma general

Un problema general de minimización con restricciones puede escribirse de la siguiente manera: ^{[ 2 ]}

{\begin{array}{rcll}\min &~&f(\mathbf {x} )&\\\mathrm {sujeto~a} &~&g_{i}(\mathbf {x} )=c_{i}&{\text{para }}i=1,\ldots ,n\quad {\text{Restricciones de igualdad}}\\&~&h_{j}(\mathbf {x} )\geq d_{j}&{\text{para }}j=1,\ldots ,m\quad {\text{Restricciones de desigualdad}}\end{array}}

dónde $g_{i}(\mathbf {x} )=c_{i}~\mathrm {para~} i=1,\ldots ,n$ y $h_{j}(\mathbf {x} )\geq d_{j}~\mathrm {for~} j=1,\ldots ,m$ son restricciones que deben cumplirse (estas se denominan restricciones estrictas ), y $f(\mathbf {x} )$ es la función objetivo que necesita ser optimizada sujeta a las restricciones.

En algunos problemas, a menudo denominados problemas de optimización con restricciones , la función objetivo es en realidad la suma de funciones de coste, cada una de las cuales penaliza el grado (si lo hay) en que se incumple una restricción flexible (una restricción que se prefiere, pero que no es obligatorio satisfacer).

Métodos de solución

Muchos algoritmos de optimización sin restricciones pueden adaptarse al caso con restricciones, a menudo mediante el uso de un método de penalización . Sin embargo, los pasos de búsqueda que realiza el método sin restricciones pueden resultar inaceptables para el problema con restricciones, lo que lleva a una falta de convergencia. Esto se conoce como el efecto Maratos. ^{[ 3 ]}

Restricciones de igualdad

Método de sustitución

Para problemas muy simples, por ejemplo, una función de dos variables sujeta a una única restricción de igualdad, lo más práctico es aplicar el método de sustitución. ^{[ 4 ]} 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, supongamos que el objetivo es maximizar $f(x,y)=x\cdot y$ sujeto a $x+y=10$ La restricción implica $y=10-x$ , que se puede sustituir en la función objetivo para crear $p(x)=x(10-x)=10x-x^{2}$ . La condición necesaria de primer orden da ${\frac {\partial p}{\partial x}}=10-2x=0$ , que se puede resolver para $x=5$ y, en consecuencia, $y=10-5=5$ .

multiplicador de Lagrange

Si el problema con restricciones solo tiene restricciones de igualdad, se puede usar el método de los multiplicadores de Lagrange para convertirlo en un problema sin restricciones cuyo número de variables es igual al número original de variables más el número original de restricciones de igualdad. Alternativamente, si todas las restricciones son de igualdad y lineales, se pueden resolver para algunas de las variables en función de las demás, y las primeras se pueden sustituir en la función objetivo, obteniendo así un problema sin restricciones con un número menor de variables.

Restricciones de desigualdad

Con restricciones de desigualdad, el problema se puede caracterizar en términos de las condiciones de optimalidad geométrica , las condiciones de Fritz John y las condiciones de Karush-Kuhn-Tucker , bajo las cuales se pueden resolver problemas simples.

Programación lineal

Si la función objetivo y todas las restricciones estrictas son lineales, y algunas de estas restricciones son desigualdades, entonces el problema es de programación lineal . Este problema puede resolverse mediante el método simplex , que generalmente funciona en tiempo polinomial para el tamaño del problema, aunque no está garantizado, o mediante métodos de punto interior, que sí garantizan un tiempo polinomial.

Programación no lineal

Si la función objetivo o algunas de las restricciones son no 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 de programación cuadrática . Es un tipo de programación no lineal. Aún puede resolverse en tiempo polinomial mediante el método del elipsoide si la función objetivo es convexa ; de lo contrario, el problema puede ser NP-difícil .

Condiciones KKT

Al permitir restricciones de desigualdad, el método KKT para la programación no lineal generaliza el método de los multiplicadores de Lagrange. Puede aplicarse bajo condiciones de diferenciabilidad y convexidad.

Ramificar y enlazar

La optimización con restricciones se puede resolver mediante algoritmos de ramificación y acotación . Estos algoritmos de retroceso almacenan el costo de la mejor solución encontrada durante la ejecución y lo utilizan para evitar parte de la búsqueda. Más precisamente, cuando el algoritmo encuentra una solución parcial que no se puede extender para formar una solución con un costo menor que el costo almacenado, retrocede en lugar de intentar extender dicha solución.

Suponiendo que se busca minimizar el costo, la eficiencia de estos algoritmos depende de cómo se evalúa 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 un costo estimado menor tiene más probabilidades de ser inferior al costo de la mejor solución encontrada hasta el momento.

Por otro lado, este costo estimado no puede ser inferior al costo efectivo que se puede obtener al extender la solución, ya que de lo contrario el algoritmo podría retroceder mientras exista una solución mejor que la mejor encontrada hasta el momento. En consecuencia, el algoritmo requiere un límite superior para 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, denominada método de Hansen, utiliza métodos de intervalo . ^{[ 5 ]} Implementa inherentemente restricciones rectangulares.

Funciones de acotación de primera elección

Una forma de evaluar este límite superior para una solución parcial es considerar cada restricción flexible por separado. Para cada restricción flexible, 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 flexibles no pueden asumir un valor mayor. Es exacto porque los valores máximos de las restricciones flexibles pueden derivarse de diferentes evaluaciones: una restricción flexible puede ser máxima para $x=a$ mientras que otra restricción es máxima para $x=b$ .

Búsqueda de muñecas rusas

Este método ^{[ 6 ]} ejecuta un algoritmo de ramificación y acotación en $n$ problemas, donde $n$ es el número de variables. Cada uno de estos problemas es el subproblema que se obtiene al descartar una secuencia de variables. $x_{1},\ldots ,x_{i}$ del problema original, junto con las restricciones que los contienen. Después del problema sobre variables $x_{i+1},\ldots ,x_{n}$ una vez resuelto, su costo óptimo puede utilizarse como límite superior al resolver los demás problemas.

En particular, la estimación de costos de una solución que tenga $x_{i+1},\ldots ,x_{n}$ Las variables no asignadas se suman al costo derivado de las variables evaluadas. En la práctica, esto equivale a ignorar las variables evaluadas y resolver el problema con las no asignadas, con la salvedad de que este último problema ya está resuelto. Más precisamente, el costo de las restricciones flexibles que contienen variables tanto asignadas como no asignadas se estima como se indicó anteriormente (o mediante otro método arbitrario); el costo de las restricciones flexibles que contienen solo variables no asignadas se estima utilizando la solución óptima del problema correspondiente, que ya se conoce.

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, la búsqueda de muñecas rusas resuelve subproblemas para llegar al problema completo. Sin embargo, mientras que la programación dinámica combina directamente los resultados obtenidos en los subproblemas para obtener el resultado del problema completo, la búsqueda de muñecas rusas solo los utiliza como límites durante su proceso de búsqueda.

eliminación de cubos

El algoritmo de eliminación de cubetas se puede adaptar para la optimización de restricciones. Una variable dada se puede eliminar del problema reemplazando todas las restricciones flexibles que la contienen con una nueva restricción flexible. El costo de esta nueva restricción se calcula asumiendo un valor máximo para cada valor de la variable eliminada. Formalmente, si $x$ es la variable que se va a eliminar, $C_{1},\ldots ,C_{n}$ son las restricciones suaves que lo contienen, y $y_{1},\ldots ,y_{m}$ son sus variables excepto $x$ La nueva restricción flexible se define mediante:

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 por cubetas funciona con un ordenamiento (arbitrario) de las variables. A cada variable se le asocia una cubeta de restricciones; la cubeta de una variable contiene todas las restricciones que tienen a dicha variable en primer lugar en el orden. La eliminación por cubetas procede desde la última variable hasta la primera. Para cada variable, todas las restricciones de la cubeta se reemplazan como se describió anteriormente para eliminar la variable. La restricción resultante se coloca entonces en la cubeta correspondiente.

Véase también

Referencias

↑ Rossi, Francesca; van Beek, Peter; Walsh, Toby (2006-01-01), Rossi, Francesca; van Beek, Peter; Walsh, Toby (eds.), "Capítulo 1 – Introducción" , Fundamentos de la Inteligencia Artificial , Manual de Programación con Restricciones, vol. 2, Elsevier, pp. 3–12 , doi : 10.1016/s1574-6526(06)80005-2 , consultado el 4 de octubre de 2019
↑ Martins, JRRA; Ning, A. (2021). Optimización del diseño de ingeniería . Cambridge University Press. ISBN 978-1108833417.
↑ Wenyu Sun; Ya-Xiang Yuan (2010). Teoría y métodos de optimización: programación no lineal , Springer, ISBN 978-1441937650pág. 541
↑ 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.
↑ Leader, Jeffery J. (2004). Análisis numérico y computación científica . Addison Wesley. ISBN 0-201-73499-0.
↑ Verfaillie, Gérard, Michel Lemaître y Thomas Schiex. " Búsqueda de muñecas rusas para la resolución de problemas de optimización con restricciones ". AAAI/IAAI, Vol. 1. 1996.

Lecturas adicionales

Bertsekas, Dimitri P. (1982). Optimización con restricciones y métodos de multiplicadores de Lagrange . Nueva York: Academic Press. ISBN 0-12-093480-9.
Dechter, Rina (2003). Procesamiento de restricciones . Morgan Kaufmann. ISBN 1-55860-890-7.
Madsen, K.; Nielsen, HB; Tingleff, O. (marzo de 2004). Optimización con restricciones (PDF) (Informe técnico) (2.ª ed.). IMM/DTU. 4213. Recuperado el 6 de septiembre de 2025 .

[1] Rossi, Francesca; van Beek, Peter; Walsh, Toby (2006-01-01), Rossi, Francesca; van Beek, Peter; Walsh, Toby (eds.), "Capítulo 1 – Introducción" , Fundamentos de la Inteligencia Artificial , Manual de Programación con Restricciones, vol. 2, Elsevier, pp. 3–12 , doi : 10.1016/s1574-6526(06)80005-2 , consultado el 4 de octubre de 2019

[edo2021-2] Martins, JRRA; Ning, A. (2021). Optimización del diseño de ingeniería . Cambridge University Press. ISBN 978-1108833417.

[3] Wenyu Sun; Ya-Xiang Yuan (2010). Teoría y métodos de optimización: programación no lineal , Springer, ISBN 978-1441937650pág. 541

[4] 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.

[5] Leader, Jeffery J. (2004). Análisis numérico y computación científica . Addison Wesley. ISBN 0-201-73499-0.

[6] Verfaillie, Gérard, Michel Lemaître y Thomas Schiex. " Búsqueda de muñecas rusas para la resolución de problemas de optimización con restricciones ". AAAI/IAAI, Vol. 1. 1996.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]