Termeni Karush-Kuhn-Tucker
În matematică , condițiile lui Karush- Kuhn - Tucker sau anterior condițiile lui Kuhn-Tucker permit rezolvarea problemelor de optimizare sub constrângeri neliniare de inegalități.
Sau , o funcție numită funcție obiectivă și funcție , numită constrângeri . Se presupune că și les sunt din clasa C 1 .
f:Rnu→R{\ displaystyle f: \ mathbb {R} ^ {n} \ to \ mathbb {R}}
geu:Rnu→R{\ displaystyle g_ {i}: \ mathbb {R} ^ {n} \ to \ mathbb {R}}
1≤eu≤m{\ displaystyle 1 \ leq i \ leq m}
f{\ displaystyle f}
geu{\ displaystyle g_ {i}}![g_ {i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ce36142a0a1c6660e82bdf3ef3f1551317efe0c)
Problema care trebuie rezolvată este următoarea:
Aflați cine maximizează sub constrângeri pentru orice .
X∗∈Rnu{\ displaystyle X ^ {*} \ in \ mathbb {R} ^ {n}}
f{\ displaystyle f}
geu(X∗)≥0{\ displaystyle g_ {i} (X ^ {*}) \ geq 0}
eu{\ displaystyle i}
Teorema
Dacă admite un maxim sub constrângeri pentru toți , atunci există îndeplinirea următoarelor condiții, numite condiții Kuhn-Tucker. Apoi spunem că este multiplicatorul Lagrange asociat cu constrângerea-a.
f{\ displaystyle f}
X∗{\ displaystyle X ^ {*}}
geu(X∗)≥0{\ displaystyle g_ {i} (X ^ {*}) \ geq 0}
eu{\ displaystyle i}
(λeu)1≤eu≤m∈Rm{\ displaystyle (\ lambda _ {i}) _ {1 \ leq i \ leq m} \ in \ mathbb {R} ^ {m}}
λeu{\ displaystyle \ lambda _ {i}}
eu{\ displaystyle i}![eu](https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20)
Condiții de primă comandă
X∗{\ displaystyle X ^ {*}}
este un punct critic al , The Lagrangianului a problemei. Cu alte cuvinte ,, unde este gradientul , sau din nou, scriind derivatele parțiale,
Lλ:X⟼f(X)+∑eu=1mλeugeu(X){\ displaystyle L _ {\ lambda}: X \ longmapsto f (X) + \ sum _ {i = 1} ^ {m} \ lambda _ {i} g_ {i} (X)}
∇Lλ(X∗)=0{\ displaystyle \ nabla L _ {\ lambda} (X ^ {*}) = 0}
∇{\ displaystyle \ nabla}![\ nabla](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3d0e93b78c50237f9ea83d027e4ebbdaef354b2)
∂f∂Xk(X∗)+∑eu=1mλeu∂geu∂Xk(X∗)=0, 1≤k≤nu{\ displaystyle {\ frac {\ partial f} {\ partial x_ {k}}} (X ^ {*}) + \ sum _ {i = 1} ^ {m} \ lambda _ {i} {\ frac { \ partial g_ {i}} {\ partial x_ {k}}} (X ^ {*}) = 0, \ 1 \ leq k \ leq n}
Condiții suplimentare de lansare
Pentru orice ,
eu{\ displaystyle i}
1≤eu≤m{\ displaystyle 1 \ leq i \ leq m}
- λeu≥0{\ displaystyle \ lambda _ {i} \ geq 0}
![{\ displaystyle \ lambda _ {i} \ geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9eb29859cc5545bc3c19b0fc9d14e23fce79367)
-
λeu=0{\ displaystyle \ lambda _ {i} = 0}
sau .geu(X∗)=0{\ displaystyle g_ {i} (X ^ {*}) = 0}![{\ displaystyle g_ {i} (X ^ {*}) = 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ae90ada26945fdc68cc7bdb74b6d20674f541be)
Se poate , de asemenea , scrie mai compact, care pentru toți , .
eu{\ displaystyle i}
min[λeu,geu(X∗)]=0{\ displaystyle \ min [\ lambda _ {i}, g_ {i} (X ^ {*})] = 0}![{\ displaystyle \ min [\ lambda _ {i}, g_ {i} (X ^ {*})] = 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4990b48286af491753cee61c95107cdc7514fffb)
Observații
Condițiile suplimentare de eliberare implică faptul că dacă , atunci . Cu alte cuvinte: dacă constrângerea-a nu este saturată , atunci multiplicatorul Lagrange asociat este zero.
geu(X∗)>0{\ displaystyle g_ {i} (X ^ {*})> 0}
λeu=0{\ displaystyle \ lambda _ {i} = 0}
eu{\ displaystyle i}![eu](https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20)
Dovada acestui rezultat se bazează în esență pe lema lui Farkas .
Reciproc
Această teoremă oferă a priori doar condițiile necesare. Cu toate acestea, în anumite condiții, acestea sunt și condiții suficiente. Acesta este în special cazul dacă și funcțiile sunt concav .
f{\ displaystyle f}
geu{\ displaystyle g_ {i}}![g_ {i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ce36142a0a1c6660e82bdf3ef3f1551317efe0c)
Note și referințe
-
(în) W. Karush, Minimele funcțiilor mai multor variabile cu inegalități au constrângeri laterale , Depart. de matematică, Univ. din Chicago, Chicago, Illinois,1939
-
William Karush a fost primul care a declarat acest rezultat în 1939. Dar opera sa a fost redescoperită cu mult timp după publicarea lui Kuhn și Tucker.
-
(în) HW Kuhn și AW Tucker, „Programare neliniară” , în Proceedings of 2nd Berkeley Symposium , Berkeley, University of California Press,1951( Math Reviews 47303 , citiți online ) , p. 481-492.
-
Pentru mai multe detalii despre condițiile de regularitate impuse, consultați „ Condiții de optimitate (dimensiune finită) ”.
Link extern
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">