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}}

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}

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}

∂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}
• λeu=0{\ displaystyle \ lambda _ {i} = 0}sau .geu(X∗)=0{\ displaystyle g_ {i} (X ^ {*}) = 0}

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}

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}

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}}

Note și referințe

1. (î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
2. 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.
3. (î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.
4. Pentru mai multe detalii despre condițiile de regularitate impuse, consultați „  Condiții de optimitate (dimensiune finită)  ”.

Link extern

• Jeremy Kun, „  Dualitatea pentru SVM  ” ,12 iunie 2017(utilizarea teoremei în învățarea statistică )

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">