Lagrange-szorzó módszer

A matematikai programozás (különösen a lineáris programozás ) problémáinak megoldására használt Lagrange szorzómódszer egy módszer a függvény feltételes szélsőértékének megtalálására , ahol a megszorításokhoz képest , ahol egytől -ig változik . $f(x)$ $x\in \mathbb{R} ^{n}$ $m$ $\varphi _{i}(x)=0$ $én$ $m$

A módszer leírása

A Lagrange -függvényt a függvény és az együtthatókkal vett függvények, úgynevezett Lagrange-szorzók lineáris kombinációjaként állítjuk össze : $f$ $\varphi _{i}$ $\lambda _{i}$

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

ahol .

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

Alkossunk egyenletrendszert úgy, hogy a Lagrange-függvény parciális deriváltjait nullával egyenlővé tesszük a és függvényében . $n+m$ $L(x,\;\lambda )$ $x_{j}$ $\lambda _{i}$
Ha az eredményül kapott rendszernek van megoldása a és paraméterekre vonatkozóan , akkor a pont lehet feltételes szélsőség, vagyis az eredeti feladat megoldása. Vegye figyelembe, hogy ez a feltétel szükséges, de nem elegendő. $x'_{j}$ $\lambda '_{i}$ $x'$

Indoklás

A Lagrange-szorzó módszer alábbi indoklása nem szigorú bizonyítéka. Heurisztikus érvelést tartalmaz, amely segít megérteni a módszer geometriai jelentését.

Kétdimenziós eset

Legyen szükséges a függvény szélsőértékének megtalálása az egyenlet által megadott feltétel mellett . $f(x,\;y)$ $\psi(x,\;y)=0$

Ezt feltételezzük

1) a függvény folyamatosan differenciálható,

f

2) a függvény folyamatosan differenciálható, parciális deriváltjai egyidejűleg nem egyenlők nullával, vagyis az egyenlet sima görbét határoz meg a sík közönséges pontjaiból .

\psi

\psi(x,\;y)=0

S

(x,\;y)

3) a görbe nem megy át olyan pontokon, ahol a gradiens .

S

f

0

Rajzoljuk a síkra a függvény szintvonalait (vagyis a görbéket ). Geometriai megfontolásokból az következik, hogy a függvény feltételes szélsőpontjának pontja (esetleg pontjai) csak a görbe és valamilyen szintvonal érintkezési pontja lehet, vagyis az a pont, ahol ennek érintője és érintője . szintvonal egybeesik. Valójában, ha egy ponton a görbe keresztirányban metszi a szintvonalat (azaz valamilyen nem nulla szögben), akkor a görbe mentén a pontból haladva mindkettő eljuthat a -nál nagyobb értéknek megfelelő szintvonalhoz , és a -nál kisebb értéknek megfelelő szintvonalakra . Ezért egy ilyen pont nem lehet szélsőpont. $(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}$

Így a szélsőség szükséges feltétele a vizsgált esetben az érintők egybeesése. Ha analitikus formában szeretné megírni, vegye figyelembe, hogy ez egyenértékű a függvények gradienseinek párhuzamosságával és egy adott pontban, mivel a gradiensvektor merőleges a szintvonal érintőjére. Ez a feltétel a következő formában fejeződik ki: $f$ $\psi$

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

ahol egy nem nulla szám, ami a Lagrange-szorzó. $\lambda$

Tekintsük most a Lagrange függvényt és függvényében : $x,\;y$ $\lambda$

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

Az extrémumának szükséges feltétele a nulla gradiens . A megkülönböztetés szabályainak megfelelően úgy írják, hogy $\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{tömb}\jobbra.

A kapott rendszerben az első két egyenlet ekvivalens a lokális szélsőség (1) szükséges feltételével, a harmadik pedig az egyenlettel . Abból meg lehet találni . Sőt , mivel ellenkező esetben a függvény gradiense a pontban eltűnik , ami ellentmond a feltételezéseknek. $\psi(x,\;y)=0$ $(x_{0},\;y_{0},\;\lambda _{0})$ $\lambda _{0}\neq 0$ $f$ $(x_{0},\;y_{0})\in S$

Megjegyzés . Az így talált pontok nem feltétlenül feltételes szélsőpontok – az írott differenciálfeltétel szükséges , de nem elégséges . $(x_{0},\;y_{0})$ $f$

A fenti érvek a feltételes szélsőség egy segédfüggvény segítségével történő megtalálásával kapcsolatban a Lagrange-szorzó módszer alapját képezik, és tetszőleges számú változó és a feltételeket meghatározó egyenlet esetére általánosítják. $L$

A Lagrange-szorzók módszere alapján elegendő feltételeket kaphatunk egy olyan feltételes szélsőséghez, amely a Lagrange-függvény második deriváltjának (a legegyszerűbb esetben) elemzését igényli . $L$

Alkalmazás

A Lagrange-szorzó módszert számos területen (például a közgazdaságtanban ) felmerülő nemlineáris programozási problémák megoldására használják.
A fő módszer az audio- és videoinformáció kódolási minőségének optimalizálásának problémájának megoldására egy adott átlagos bitsebesség mellett (lásd: Torzításoptimalizálás).

Lásd még

Irodalom

Akulich I.L. 3. fejezet A nemlineáris programozás problémái // Matematikai programozás példákban és feladatokban. - M . : Felsőiskola , 1986. - 319 p. — ISBN 5-06-002663-9 . .
Zorich V. A. Matematikai elemzés. 1. rész – szerk. 2., rev. és további - M. : FAZIS, 1997.
Protasov V. Yu. Maximák és minimumok a geometriában . — M. : MTsNMO. — 56 p. - ("Matematikai oktatás" könyvtár, 31. szám).