He estado usando multiplicadores de Lagrange en problemas de optimización restringida, pero no veo cómo realmente funcionan simultáneamente para satisfacer la restricción y encontrar el menor valor posible de la función objetivo.
Respuestas
¿Demasiados anuncios?
ricree
Puntos
5055
Este tipo de problema es el que generalmente se conoce como optimización restringida. Una técnica general para resolver muchos de estos tipos de problemas se conoce como el método de los multiplicadores de Lagrange, aquí es un ejemplo de un problema utilizando multiplicadores de Lagrange, y una breve justificación de por qué la técnica de obras.
Considerar la parabaloid dada por $f(x,y) = x^2 + y^2$. El mínimo global de esta superficie se encuentra en el origen (en $x=0$, $y=0$). Si se nos da la restricción, un requisito en la relación entre el valor de $x$ y $y$ que $3x+y=6$, entonces el origen no puede ser nuestra solución (desde $3\cdot 0 + y \cdot 0 \neq 6$). Sin embargo, hay un punto más bajo en la esta función a la satisfacción de las dada la restricción.
Lo que tenemos hasta ahora:
Función objetivo: $f(x,y) = x^2 + y^2$,
sujeto a: $3x+y=6$.
A partir de aquí podemos derivar la formulación de Lagrange de nuestra limitada problema de minimización. Esta será una función $L$ de $x$, $y$, y un único multiplicador de Lagrange $\lambda$ (ya que sólo tenemos una única restricción). Será esta nueva función que podemos minimizar.
$L(x,y,\lambda) = x^2 + y^2 + \lambda(3x+y-6)$
La formulación de Lagrange incorpora nuestra función original junto con nuestra restricción(s). En el camino hacia la minimización de $L$, tenemos que minimizar la función objetivo $x^2 + y^2$, así como minimizar la contribución de la restricción, que ahora es ponderado por un factor de $\lambda$. Si la restricción se cumple, entonces la expresión $3x+y-6$ necesariamente va a ser cero, y no contribuir en nada el valor de $L$. Este es el truco de la técnica.
La minimización de la formulación de Lagrange:
Para minimizar $L$ nos basta con encontrar el valor de $x,$ y y $\lambda$ valores que hacen de su gradiente de cero. (Esto es exactamente análoga a la configuración de la primera derivada a cero en el cálculo.)
$\nabla L = 0:$
$\frac{\partial L}{\partial x} = 2x + 3 \lambda = 0$
$\frac{\partial L}{\partial y} = 2y + \lambda = 0$
$\frac{\partial L}{\parcial \lambda} = 3x + y - 6 = 0$,
En nuestro ejemplo, hemos llegado a un sistema de ecuaciones lineales simultáneas que puede (y debe) ser resuelto con el álgebra matricial. La solución será un vector de la celebración de los valores de $x,$ y y $\lambda$. El menor valor de la función objetivo, sujeta a la restricción, se encuentra en $(x,y,f(x,y))$, y el multiplicador de Lagrange no tiene una inmediata interpretación física. (Los multiplicadores tienen significado cuando aparecen en ciertos contextos, más información sobre esto aquí.)
Esto se profundiza en el Señor Bulatov la respuesta (nota: el Señor Bulatov el enlace está roto, pero deduzco que se supone enlace a Dan Klein notas de los Multiplicadores de Lagrange sin dejar Cicatrices Permanentes, que de hecho son excelentes).
De todos modos, por el bien de la simplicidad, vamos a trabajar con funciones de dos variables, es decir, queremos encontrar los puntos críticos de $f(x,y)$ donde la restricción es de $g(x,y)=c$.
Tomar cualquier punto $(a,b)$ en la $xy$-plano tales que $g(a,b)=c$. Supongamos que hay una (unidad) vector $\vec v$ tangente a $g$ en $(a,b)$ cuyo producto escalar con el vector gradiente de $f$ en $(a,b)$ era distinto de cero. Podemos tomar $\vec v$ tales que el producto escalar con $\vec v$ es positivo ya que $\nabla f(a,b)\cdot \vec v=-(\nabla f(a,b)\cdot -\vec v)$.
Ahora lo que esto significa es que la derivada parcial de $f$, con respecto a $\vec v\quad$ es positivo y que los puntos a lo largo de $\vec v\quad$ lo suficientemente cerca de $(a,b)$ mayor $f$-valor. Yo (y el Señor Bulatov) afirman que esto significa que hay puntos en los $g(x,y)=c$ cerca $(a,b)$, con más de $f$-valor, lo que significa que $f$ no es un máximo. El señor Bulatov frases el argumento bien en términos de infinitesimals, pero creo que un poco más de rigor es iluminadora.
Considere la posibilidad de una secuencia de puntos $(a_i,b_i)$ en $g(x,y)=c$ que convergen a $(a,b)$. Cada punto $(a_i,b_i)$ viene con un vector unitario $\vec u_i$ que corresponde a la dirección (es un escalar varios de) $(a,b) - (a_i,b_i)$. Debido a que $\vec v$ es un vector tangente, podemos elegir el $(a_i,b_i)$ tal que $\vec u_i$ convergen a $\vec v$ . Pero debido a que $f$ es derivable en más de una variable, sus derivadas parciales son continuas, y así tenemos que las derivadas parciales $\nabla f(a,b)\cdot \vec u_i$ convergen a $\nabla f(a,b) \cdot \vec v$, y así para todos lo suficientemente grande me la derivada parcial en el $u_i$ en una dirección positiva y por lo que $f(a_i,b_i)>f(a,b)$.
Por lo tanto, si $f(a,b)$ era a un máximo (o mínimo) de $f$ en $g(x,y)=c$, el vector gradiente de $f$ en $(a,b)$ sería tener el punto producto de cero con todos los vectores de la línea tangente a $g$ en $(a,b)$. Pero eso significa que el vector gradiente de $f$ es ortogonal a la recta tangente de $g$, lo que significa que el gradiente de $f$ debe ser paralelo (es decir, un escalar varios de) el gradiente de $g$.
A partir de aquí podemos obtener las ecuaciones de $\nabla f(x,y)=\lambda\nabla g(x,y)$ y $g(x,y)=c$, que se satisface si y sólo si $(x,y)$ es de un mínimo de $f(x,y)+\lambda (g(x,y)-c)$ positiva de $\lambda$ y un máximo negativo de $\lambda$.
pointernil
Puntos
136
Probablemente había averiguado ya, pero para la posteridad -- este documento da la intuición de que no me vea en Boyd libro, esp. La figura 3 en la página 3.
Para resolver la igualdad restringida problema para los puntos donde el gradiente de objetivo está en la misma dirección del gradiente de la función de limitación. Por qué esos puntos? Bien, supongamos que tenemos un posible punto de que un máximo del objetivo y de los gradientes de objetivo/restricción de las funciones no son colineales. Entonces usted puede tomar un infinitesimal paso en la dirección ortogonal a la gradiente de la función de limitación para aumentar el objetivo. Y porque usted se está moviendo en la dirección ortogonal a la gradiente de la función de limitación, la restricción es aún satisfecho. Por lo tanto, usted consigue un posible punto con mayor valor objetivo, la contradicción.
Dan Walker
Puntos
3466
Dos variables y una restricción a la
Si tenemos un objetivo en función de dos variables reales $f(x,y)$ sujeto a la restricción de $g(x,y)=0$ y quieres encontrar a los mínimos o máximos, siempre que la hay, entonces las tres condiciones siguientes deben ser satisfechas:
$f_{x}(x,y)=0$
$f_{y}(x,y)=0$
$g(x,y)=0$
Por lo tanto
$\lambda g(x,y)=0$,
$\lambda g_{x}(x,y)=0$,
y
$\lambda g_{y}(x,y)=0$,
donde $\lambda $ es el multiplicador de Lagrange. Así
$f_{x}(x,y)-\lambda g_{x}(x,y)=0$,
$f_{y}(x,y)-\lambda g_{y}(x,y)=0$.
para algunos $(x,y,\lambda )=(x^{\ast },y^{\ast },\lambda ^{\ast })$
Ahora nos fijamos $F(x,y,\lambda )=f(x,y)-\lambda g(x,y)$. Observar que
(Este es el punto clave de mi explicación)
$F_{x}(x,y,\lambda )=f_{x}(x,y)-\lambda g_{x}(x,y)=0$,
$F_{y}(x,y,\lambda )=f_{y}(x,y)-\lambda g_{y}(x,y)=0$
$F_{\lambda }(x,y,\lambda )=-g(x,y)=0$
Por lo tanto debemos encontrar la solución $(x^{\ast },y^{\ast },\lambda ^{\ast })$ de el siguiente sistema de 2+1 ecuaciones:
$F_{x}(x,y,\lambda )=0$
$F_{y}(x,y,\lambda )=0$
$F_{\lambda }(x,y,\lambda )=0$
Máximo o Mínimo?
Para establecer si la función $f(x,y)$ tiene un máximo o un mínimo uno debe definir las condiciones adicionales que tomar en cuenta la 2ª derivados de $f$.
$$ n variables y m $de$ las restricciones
Para una función $f$ de $$ n variables reales, sujetos a $m$ restricciones de $g_{k}$, con $1\leq k\leq m$ tenemos $m$ multiplicadores de Lagrange y debe resolver un sistema de $n+m$ ecuaciones.
