Multiplicadores de Lagrange con restricciones de desigualdad: minimizar $f$ en la región $0 \leq x,y \leq 1$

Question

No tengo mucha experiencia con la optimización restringida, pero espero que me puedan ayudar. Mi problema actual implica una función más compleja, pero las restricciones son similares a las siguientes. Sólo para poder ver cómo aplicar los multiplicadores de Lagrange a mi problema, quiero ver una función más simple.

Supongamos que quiero minimizar la función

$$ f(x,y) = a + bx + cy $$ con sujeción a las restricciones $$ 0 \le x, y \le 1. $$

Si entiendo bien la técnica de los multiplicadores de Lagrange, debería crear 4 funciones de restricción: $x = 0$ , $x = 1$ , $y = 0$ y $y = 1$ . Esto llevaría a minimizar la función $$ a + bx + cy - \lambda_1 x + \lambda_2 (x-1) - \lambda_3y + \lambda_4(y-1) $$ con respecto a $x,y,\lambda_1, \lambda_2,\lambda_3$ y $\lambda_4$ .

¿Parece esto correcto? Si no es así, ¿en qué me he equivocado? Su ayuda es muy apreciada.

Answer 1

Eso podría funcionar, pero tiene muchas más variables que las ecuaciones. En su lugar, recomiendo pensar de la siguiente manera:

La región $ 0 \leq x, y \leq 1$ es un cuadrado. Y lo que es más importante, es una región compacta. Así que sabemos que nuestra función tomará un máximo y un mínimo en algún lugar. Por tanto, alcanzará sus extremos en el interior o en el límite.

Para comprobar el interior, realice la prueba habitual de máximo/mínimo: tome el gradiente y póngalo a cero. Utilice la "prueba de la segunda derivada" multivariable o simplemente compare los puntos para comprobar los máximos y los mínimos. Ahora, debería comprobar los límites. Esto significa que podrías hacer el método regular de los multiplicadores de Lagrange 4 veces, una con cada restricción $$\begin {align} y &= 0; \quad x = 0 \\ y &= 0; \quad x = 1 \\ y &= 1; \quad x = 0 \\ y &= 1; \quad x = 1 \end{align}$$ Quiero enfatizar que yo haría estas restricciones por separado en lugar de hacerlo juntos. Cada uno de ellos es muy trivial de resolver - pero sólo se presta atención a las soluciones dentro de su región de interés. Hay un lugar más que debes comprobar, y son las esquinas (aquí, el límite de la frontera: es como si tratáramos nuestro dominio como 4 líneas separadas, a su vez cerradas y acotadas).

Por último, se comparan estas tres áreas: el interior, los límites de las líneas y los límites de las esquinas. Como la región es compacta, hay se ser un máximo absoluto y un mínimo absoluto (quizás múltiple). Esa parece ser la forma más fácil de hacerlo, sobre todo porque todas las ecuaciones en este caso son muy simples de resolver (todas lineales).

Debo señalar que no es necesario utilizar multiplicadores de Lagrange si no se quiere. Podrías interpretar las líneas como caminos, y maximizar/minimizar la curva a lo largo de cada uno de los caminos (lo que no requiere Lagrange, sino una parametrización). Entonces usted todavía comparar el interior y el límite. Pero esto no me parece tan divertido, y no vale la pena en este caso.

Answer 2

Lo que usted llama "restricciones" es en realidad la definición del conjunto compacto $Q$ sobre la cual la función $f$ tiene que ser maximizado. Para encontrar este máximo hay que establecer una lista de puntos candidatos $P_k\in Q$ utilizando la "estratificación" de $Q$ en colectores abiertos de dimensiones $2$ , $1$ y $0$ . La razón es la siguiente: Establecer una derivada (o $\nabla f$ ) a $0$ sólo encontrará puntos estacionarios en el interior de algún dominio de "dimensión completa".

En su ejemplo, el conjunto $Q$ se estratifica de la siguiente manera: Consta de un $2$ -dimensionado interior abierto $Q^\circ$ de cuatro $1$ -segmentos fronterizos de dimensiones $E_i$ (¡sin puntos finales!) y de cuatro vértices $V_i$ .

Los posibles candidatos en $Q^\circ$ se ponen de manifiesto resolviendo la ecuación $\nabla f(x,y)=0$ es decir, el sistema $f_x(x,y)=0$ , $f_y(x,y)=0$ y retener las soluciones que se encuentran en $Q^\circ$ .

Para los posibles candidatos en un borde $E_i$ hay dos métodos: O bien se puede producir una representación paramétrica $t\mapsto\bigl(x(t),y(t)\bigr)$ de $E_i$ (que en su ejemplo ciertamente puede) y luego calcular los "puntos condicionalmente estacionarios" de $f$ en $E_i$ observando el retroceso $\phi(t):=f\bigl(x(t),y(t)\bigr)$ . Esto significa que se resuelve la ecuación $\phi'(t)=0$ obtener algo de $t_k$ y añadir los puntos $\bigl(x(t_k),y(t_k)\bigr)$ a la lista, si pertenecen a $Q$ . Si su borde $E_i$ viene dada por una restricción $G(x,y)=0$ que no se puede resolver para $x$ o $y$ entonces hay que recurrir a los multiplicadores de Lagrange. (Omito los detalles).

Finalmente hay que añadir los vértices $V_i$ a su lista de candidatos.

Supongamos que ahora tiene una lista finita de candidatos $L=\{P_1, P_2,\ldots, P_r\}\subset Q$ . Entonces $$\max_{(x,y)\in Q} f(x,y)\ =\ \max\{f(P_1),f(P_2),\ldots, f(P_r)\}\ .$$

Lamento que las cosas sean tan engorrosas, incluso para un dominio tan simple como un cuadrado. Pero es fácil cocinar un ejemplo en el que por olvidar un vértice o un punto condicionalmente estacionario en una arista se pierde el máximo de $f$ en $Q$ .

Answer 3

La respuesta de mixedmath es correcta; aquí hay algo más sobre tu pregunta "¿en qué me he equivocado?". Has intentado imponer las cuatro restricciones a la vez, aunque no sean todas compatibles. Recuerda que la solución mediante multiplicadores de Lagrange no sólo implica añadir múltiplos de las restricciones a la función objetivo, sino también determinar tanto las variables originales como los multiplicadores poniendo todas las derivadas a cero (donde las derivadas con respecto a los multiplicadores son las restricciones). Si se incluyen restricciones incompatibles (como $x=0$ y $x=1$ ), el sistema de ecuaciones resultante no tiene soluciones. En este caso, dado que las restricciones sólo difieren en las constantes aditivas, se puede ignorar esto y establecer las derivadas de la función con respecto a $x$ y $y$ a cero e imponiendo las restricciones un par a la vez; entonces sólo tendrías un ligero exceso de multiplicadores pero seguirías obteniendo los valores correctos de $x$ y $y$ ; pero si tus restricciones difieren de tal manera que sus derivadas con respecto a las variables difieren (es decir, por algo más que una constante aditiva), eso ya no funcionará y las restricciones se mezclarán inextricablemente si las impones todas a la vez.