Método del multiplicador de Lagrange

El método del multiplicador de Lagrange , utilizado para resolver problemas de programación matemática (en particular, programación lineal ) es un método para encontrar el extremo condicional de la función , donde , en relación con las restricciones , donde varía de uno a . $f(x)$ $x\en \mathbb{R} ^{n}$ $metro$ $\varphi _{i}(x)=0$ $i$ $metro$

Descripción del método

Componemos la función de Lagrange como una combinación lineal de la función y las funciones tomadas con coeficientes, llamados multiplicadores de Lagrange - : $F$ $\varphi _{i}$ $\lambda _{i}$

L(x,\;\lambda)=f(x)+\sum_{{i=1}}^{m}\lambda_{i}\varphi_{i}(x),

donde _

\lambda =(\lambda _{1},\;\ldots,\;\lambda _{m})

Compongamos un sistema de ecuaciones igualando a cero las derivadas parciales de la función de Lagrange con respecto a y . $n+m$ $L(x,\;\lambda )$ $x_{j}$ $\lambda _{i}$
Si el sistema resultante tiene solución con respecto a los parámetros y , entonces el punto puede ser un extremo condicional, es decir, una solución al problema original. Nótese que esta condición es necesaria pero no suficiente. $x'_{j}$ $\lambda '_{i}$ $X'$

Justificación

La siguiente justificación del método del multiplicador de Lagrange no es su prueba rigurosa. Contiene razonamiento heurístico que ayuda a comprender el significado geométrico del método.

Caso bidimensional

Sea necesario encontrar el extremo de la función bajo la condición dada por la ecuación . $f(x,\;y)$ $\psi(x,\;y)=0$

Asumiremos que

1) la función es continuamente diferenciable,

F

2) la función es continuamente diferenciable, con derivadas parciales no iguales a cero al mismo tiempo, es decir, la ecuación define una curva suave a partir de puntos ordinarios en el plano .

\psi

\psi(x,\;y)=0

S

(x,\;y)

3) la curva no pasa por los puntos donde la pendiente se convierte en .

S

F

{\ estilo de visualización 0}

Dibujemos en el plano las líneas de nivel de la función (es decir, las curvas ). A partir de consideraciones geométricas, se sigue que el punto (posiblemente puntos) del extremo condicional de la función solo puede ser el punto de contacto de la curva y alguna línea de nivel, es decir, el punto en el que la tangente a y la tangente a este línea de nivel coinciden. De hecho, si en algún punto la curva se cruza transversalmente con la línea de nivel (es decir, en un ángulo distinto de cero), entonces, al moverse a lo largo de la curva desde el punto , puede llegar a ambas líneas de nivel correspondientes a un valor mayor que , ya las líneas de nivel correspondientes a un valor inferior a . Por lo tanto, tal punto no puede ser un punto extremo. $(x,\;y)$ $F$ $f(x,\;y)={\mathrm {const}}$ $F$ $S$ $S$ $(x_{0},\;y_{0})$ $S$ $f(x_0,\;y_0)=C_0$ $S$ $(x_{0},\;y_{0})$ $C_{0}$ $C_{0}$

Así, la condición necesaria para un extremo en el caso que nos ocupa es la coincidencia de las tangentes. Para escribirlo en forma analítica, nótese que es equivalente al paralelismo de los gradientes de las funciones y en un punto dado, ya que el vector gradiente es perpendicular a la tangente a la recta de nivel. Esta condición se expresa de la siguiente forma: $F$ $\psi$

\nabla f\Big|_{(x_0,\;y_0)}=\lambda \cdot \nabla\psi\Big|_{(x_0,\;y_0)},\qquad\qquad(1)

donde es un número distinto de cero, que es el multiplicador de Lagrange. $\lambda$

Considere ahora la función de Lagrange dependiendo de y : $x,\;y$ $\lambda$

L(x,\;y,\;\lambda)=f(x,\;y)-\lambda \cdot \psi(x,\;y).

Una condición necesaria para su extremo es el gradiente cero . De acuerdo con las reglas de diferenciación, se escribe como $\nabla L(x_{0},\;y_{0},\;\lambda _{0})=0$

\left\{\begin{matriz}{llcc} \dfrac{\parcial f}{\parcial x}\Big|_{(x_0,\;y_0)} & -\lambda_0 \cdot \dfrac{\parcial\psi }{\parcial x}\Grande|_{(x_0,\;y_0)} & = & 0,\\ \dfrac{\parcial f}{\parcial y}\Grande|_{(x_0,\;y_0) } & -\lambda_0 \cdot \dfrac{\parcial\psi}{\parcial y}\Big|_{(x_0,\;y_0)} & = & 0,\\ & -\psi(x_0,\;y_0 ) & = & 0. \end{matriz}\right.

En el sistema resultante, las dos primeras ecuaciones son equivalentes a la condición necesaria del extremo local (1), y la tercera es equivalente a la ecuación . Desde allí puedes encontrar . Además , ya que de lo contrario el gradiente de la función se anula en el punto , lo que contradice las suposiciones. $\psi(x,\;y)=0$ $(x_{0},\;y_{0},\;\lambda _{0})$ $\lambda _{0}\neq 0$ $F$ $(x_{0},\;y_{0})\en S$

comentario _ Los puntos encontrados de esta manera pueden no ser puntos extremos condicionales ; la condición diferencial escrita es necesaria , pero no suficiente . $(x_{0},\;y_{0})$ $F$

Los argumentos anteriores sobre encontrar un extremo condicional usando una función auxiliar forman la base del método del multiplicador de Lagrange y se generalizan al caso de un número arbitrario de variables y ecuaciones que especifican las condiciones. $L$

Con base en el método de los multiplicadores de Lagrange, se pueden obtener condiciones suficientes para un extremo condicional que requieren el análisis (en el caso más simple) de las segundas derivadas de la función de Lagrange . $L$

Aplicación

El método del multiplicador de Lagrange se utiliza para resolver problemas de programación no lineal que surgen en muchas áreas (por ejemplo, en economía ).
El método principal para resolver el problema de optimizar la calidad de la codificación de información de audio y video para una tasa de bits promedio determinada (consulte Optimización de distorsión).

Véase también

Literatura

Akulich I.L. Capítulo 3. Problemas de Programación No Lineal // Programación Matemática en Ejemplos y Problemas. - M. : Escuela superior , 1986. - 319 p. — ISBN 5-06-002663-9 . .
Zorich V. A. Análisis matemático. Parte 1. - ed. 2º, rev. y adicional - M. : FAZIS, 1997.
Protasov V. Yu. Máximos y mínimos en geometría . — M. : MTsNMO. — 56 págs. - (Biblioteca "Educación Matemática", número 31).