Cómo formular problemas de optimización restringidos

Question

Para un problema de optimización restringida, pueden ser diferentes formulaciones.

Por ejemplo, considere el problema con la siguiente formulación:

$$\min_{x \in X \subseteq \mathbb{R}^n} \, f(x),$$ sujeto a $g(x) \leq 0, h(x)=0$.

1. Uno se puede mover parte de los (en)las restricciones de igualdad en la set $X$, o reducir $X$ mediante el movimiento de una parte de ella la (in)restricciones de igualdad.
2. También se puede intercambiar entre el las restricciones de igualdad y la la desigualdad de las restricciones. Por ejemplo, $h(x)=0$ puede ser reemplazado por $h(x)\leq 0, -h(x) \leq 0$.

Me preguntaba si hay algunas pautas sobre cómo formular un problema de optimización restringida en diferentes formas para diferentes propósitos, tales como para revelar mejor su estructura, para hacer que sea más fácil de resolver, para hacerlo se vuelven menos mal planteado, en algún sentido, ...

Hay algunas discusiones acerca de esto en algunos libros, de papel, enlaces, ...?

Gracias y saludos!

Answer 1

Normalmente tendrás que usar el set $X$ a representar a la caja negra de las restricciones, por ejemplo, las restricciones para que usted no tiene una analítica de la representación. Se podría consistir en la salida de un equipo de código que devuelve True si las restricciones son satisfechas y False en caso contrario. En general, si usted tiene analítico de las descripciones de las restricciones, es a su ventaja para el uso de ellos. No es la investigación en mixto de la caja negra de optimización, donde el problema tiene una mezcla de la caja negra de las limitaciones y restricciones explícitas, pero no obtener el máximo provecho de su problema en términos de eficiencia, si usted ha clasificado erróneamente limitaciones como la caja negra de las restricciones.

En cuanto a la transformación de la igualdad y en dos de las desigualdades, que hará que la mayoría de los algoritmos para el buen optimización para romper (asumiendo $h$ es suave). Es fácil ver por qué: la mayoría de los métodos es el objetivo de satisfacer las condiciones KKT (de primer orden de optimalidad). Sin embargo las condiciones KKT son necesarias para la optimalidad SI una restricción de calificación está satisfecho. Una restricción de calificación es un certificado de que la expresión analítica del conjunto factible es, en cierto sentido, no redundante en la descripción de su geometría.

Consideremos por ejemplo las limitaciones de la $x^3 \leq 1$$x^3 \geq 1$. Vemos claramente una cierta redundancia aquí. ¿Por qué no decir $x^3 = 1$? ¿Por qué no decir $x=1$???

La redundancia se manifiesta en la restricción de calificación. El más ampliamente utilizado de la restricción de la calificación de la condición es la independencia lineal de la restricción de la calificación de la condición (LICQ). Se requiere que los gradientes de las restricciones que están satisfechos como una igualdad en una solución linealmente independiente. Esto se refiere, por supuesto, todas las restricciones de igualdad, sino también de todas las desigualdades que son "activos" (es decir, $g_i(x) = 0$ en su notación). Desde $h$ fue una de las restricciones de igualdad, vamos a tener necesariamente $h(x) = 0$ a una solución, pero los gradientes de las funciones $h$ $-h$ no puede ser linealmente independientes. Tratar de resolver un problema con $x^3 \leq 1$ $x^3 \geq 1$ en uno de los NEOS y los solucionadores podrás observar problemas: http://neos-server.org/neos

Te quedarás en el mismo tipo de problemas si uno de los activos de la restricción de los gradientes se desvanece en una solución. Considere, por ejemplo, la restricción $x^2 = 0$. Cuando los problemas son generados automáticamente por algún procedimiento, es muy difícil de comprobar dichos redundancia, pero cuando el modelo de un problema a mano desde cero, es importante mirar hacia fuera para él.

Volviendo al primer tema, no es un teórico de ventaja a la descripción de cualquier conjunto factible, como acaba de $X \subseteq \mathbb{R}^n$. Es que el primer orden de optimalidad condiciones son simplemente eso $-\nabla f(x)$ debe estar en la normal de cono a$X$$x$. Y esto no depende de ninguna restricción de calificación debido a que esta es una afirmación que no sólo se refiere a la geometría del conjunto factible, no su descripción analítica.

Para obtener más información, echa un vistazo a el libro de Bazaraa, Sherali y Shetty, o "Optimización Numérica" por Nocedal y Wright (Springer).

Answer 2

De hecho, hay un listo, bien desarrollada la teoría de la exactitud para su problema de optimización

minimizar $f(x)$ bajo $g(x)\leq0,h(x)=0$,

llama Karush-Kuhn-Tucker de Optimización.

Se generaliza la técnica de los Multiplicadores de Lagrange para el problema sin desigualdades $g\leq0$, lo que usted debe entender de antemano, si no lo has hecho ya.

Answer 3

Un avión a reacción debe alcanzar un cierto punto en el espacio en el tiempo mínimo del despegue. Suponiendo que la energía total (energía cinética energía potencial combustible) es constante, el chorro quema el combustible a su velocidad constante máxima y tiene velocidad nula al despegar, formule el correspondiente problema de optimización.