Metoda multiplicatorului Lagrange

Metoda multiplicatorului Lagrange , folosită pentru rezolvarea problemelor de programare matematică (în special, programarea liniară ) este o metodă de găsire a extremului condiționat al funcției , unde , în raport cu constrângerile , unde variază de la unu la . $f(x)$ $x\in \mathbb{R} ^{n}$ $m$ $\varphi _{i}(x)=0$ $i$ $m$

Descrierea metodei

Compunem funcția Lagrange ca o combinație liniară a funcției și a funcțiilor luate cu coeficienți, numite multiplicatori Lagrange - : $f$ $\varphi _{i}$ $\lambda _{i}$

L(x,\;\lambda )=f(x)+\sum _{{i=1}}^{m}\lambda _{i}\varphi _{i}(x),

unde .

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

Să compunem un sistem de ecuații prin egalarea cu zero a derivatelor parțiale ale funcției Lagrange în raport cu și . $n+m$ $L(x,\;\lambda )$ $x_{j}$ $\lambda _{i}$
Dacă sistemul rezultat are o soluție în raport cu parametrii și , atunci punctul poate fi un extremum condiționat, adică o soluție a problemei inițiale. Rețineți că această condiție este necesară, dar nu suficientă. $x'_{j}$ $\lambda '_{i}$ $X'$

Motivație

Următoarea justificare a metodei multiplicatorului Lagrange nu este dovada sa riguroasă. Conține raționament euristic care ajută la înțelegerea semnificației geometrice a metodei.

Caz bidimensional

Fie necesar să se găsească extremul funcției în condiția dată de ecuația . $f(x,\;y)$ $\psi(x,\;y)=0$

Vom presupune că

1) funcția este diferențiabilă continuu,

f

2) funcția este diferențiabilă continuu, cu derivate parțiale nu egale cu zero în același timp, adică ecuația definește o curbă netedă din puncte obișnuite de pe plan .

\psi

\psi(x,\;y)=0

S

(X y)

3) curba nu trece prin punctele în care gradientul devine .

S

f

0

Să desenăm pe plan liniile de nivel ale funcției (adică curbele ). Din considerente geometrice, rezultă că punctul (eventual puncte) extremului condiționat al funcției nu poate fi decât punctul de contact al curbei și al unei linii de nivel, adică punctul în care tangenta și tangenta la aceasta. linia de nivel coincide. Într-adevăr, dacă la un moment dat curba intersectează linia de nivel transversal (adică la un unghi diferit de zero), atunci când vă deplasați de-a lungul curbei din punctul , puteți ajunge pe ambele la liniile de nivel corespunzătoare unei valori mai mari decât , iar la liniile de nivel corespunzătoare unei valori mai mici de . Prin urmare, un astfel de punct nu poate fi un punct extremum. $(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}$

Astfel, condiția necesară pentru un extremum în cazul în cauză este coincidența tangentelor. Pentru a-l scrie sub formă analitică, rețineți că este echivalent cu paralelismul gradienților funcțiilor și într-un punct dat, deoarece vectorul gradientului este perpendicular pe tangenta la linia de nivel. Această condiție este exprimată în următoarea formă: $f$ $\psi$

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

unde este un număr diferit de zero, care este multiplicatorul Lagrange. $\lambda$

Luați în considerare acum funcția Lagrange în funcție de și : $X y$ $\lambda$

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

O condiție necesară pentru extremul său este gradientul zero . În conformitate cu regulile de diferențiere, se scrie ca $\nabla L(x_{0},\;y_{0},\;\lambda _{0})=0$

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

În sistemul rezultat, primele două ecuații sunt echivalente cu condiția necesară a extremului local (1), iar a treia este echivalentă cu ecuația . Din el puteți găsi . În plus , deoarece în caz contrar gradientul funcției dispare în punctul , ceea ce contrazice ipotezele. $\psi(x,\;y)=0$ $(x_{0},\;y_{0},\;\lambda _{0})$ $\lambda _{0}\neq 0$ $f$ $(x_{0},\;y_{0})\în S$

Observație . Punctele găsite în acest fel pot să nu fie puncte extreme condiționale - condiția diferențială scrisă este necesară , dar nu suficientă . $(x_{0},\;y_{0})$ $f$

Argumentele de mai sus despre găsirea unui extremum condiționat folosind o funcție auxiliară formează baza metodei multiplicatorului Lagrange și sunt generalizate în cazul unui număr arbitrar de variabile și ecuații care specifică condițiile. $L$

Pe baza metodei multiplicatorilor Lagrange, se pot obține condiții suficiente pentru un extremum condiționat care necesită analiza (în cel mai simplu caz) a derivatelor secunde ale funcției Lagrange . $L$

Aplicație

Metoda multiplicatorului Lagrange este utilizată în rezolvarea problemelor de programare neliniară care apar în multe domenii (de exemplu, în economie ).
Metoda principală pentru rezolvarea problemei de optimizare a calității codificării informațiilor audio și video pentru un anumit debit mediu de biți (vezi Optimizarea distorsiunii).

Vezi și

Literatură

Akulich I.L. Capitolul 3. Probleme de programare neliniară // Programare matematică în exemple și probleme. - M . : Şcoala superioară , 1986. - 319 p. — ISBN 5-06-002663-9 . .
Zorich V. A. Analiză matematică. Partea 1. - ed. al 2-lea, rev. si suplimentare - M. : FAZIS, 1997.
Protasov V. Yu. Maxime și minime în geometrie . — M .: MTsNMO. — 56 p. - (Biblioteca „Educația matematică”, numărul 31).