Karush – Kuhn – Tuckerovy podmínky - Karush–Kuhn–Tucker conditions

v matematická optimalizace, Podmínky Karush – Kuhn – Tucker (KKT), také známý jako Podmínky Kuhn – Tucker, jsou první derivační testy (někdy se tomu říká první objednávka nezbytné podmínky ) pro řešení v nelineární programování být optimální, za předpokladu, že některé podmínky pravidelnosti jsou spokojeni.

Přístup KKT k nelineárnímu programování umožňuje omezení nerovnosti a zobecňuje metodu Lagrangeovy multiplikátory, což umožňuje pouze omezení rovnosti. Podobně jako Lagrangeův přístup je problém s omezenou maximalizací (minimalizací) přepsán jako Lagrangeova funkce, jejíž optimální bod je sedlový bod, tj. globální maximum (minimum) nad doménou proměnných volby a globální minimum (maximum) nad multiplikátory, a proto se Karush – Kuhn – Tuckerova věta někdy označuje jako věta o sedlovém bodě.^[1]

Podmínky KKT byly původně pojmenovány po Harold W. Kuhn a Albert W. Tucker, který poprvé zveřejnil podmínky v roce 1951.^[2] Později vědci zjistili, že podmínky nezbytné pro tento problém byly uvedeny v William Karush ve své diplomové práci v roce 1939.^[3][4]

Nelineární optimalizační problém

Zvažte následující nelineární problém s minimalizací nebo maximalizací:

Optimalizovat ${ displaystyle f ( mathbf {x})}$

podléhá

${ displaystyle g_ {i} ( mathbf {x}) leq 0,}$

${ displaystyle h_ {j} ( mathbf {x}) = 0.}$

kde ${ displaystyle mathbf {x} in mathbf {X}}$ je optimalizační proměnná vybraná z a konvexní podmnožina z ${ displaystyle mathbb {R} ^ {n}}$, ${ displaystyle f}$ je objektivní nebo nástroj funkce, ${ displaystyle g_ {i} (i = 1, ldots, m)}$ jsou nerovnosti omezení funkce a ${ displaystyle h_ {j} (j = 1, ldots, ell)}$ jsou rovnost omezení funkce. Počty nerovností a rovností jsou označeny ${ displaystyle m}$ a ${ displaystyle ell}$ resp. Odpovídající problému optimalizace omezení lze vytvořit Lagrangeovu funkci

${ displaystyle L ( mathbf {x}, mathbf { mu}, mathbf { lambda}) = f ( mathbf {x}) + mathbf { mu} ^ { top} mathbf {g } ( mathbf {x}) + mathbf { lambda} ^ { top} mathbf {h} ( mathbf {x})}$

kde ${ displaystyle mathbf {g} ( mathbf {x}) = left (g_ {1} ( mathbf {x}), ldots, g_ {m} ( mathbf {x}) right) ^ { horní }}$, ${ displaystyle mathbf {h} ( mathbf {x}) = left (h_ {1} ( mathbf {x}), ldots, h _ { ell} ( mathbf {x}) right) ^ {horní }}$. The Karush – Kuhn – Tuckerova věta pak uvádí následující.

Teorém. Li ${ displaystyle ( mathbf {x} ^ { ast}, mathbf { mu} ^ { ast})}$ je sedlový bod z ${ displaystyle L ( mathbf {x}, mathbf { mu})}$ v ${ displaystyle mathbf {x} in mathbf {X}}$, ${ displaystyle mathbf { mu} geq mathbf {0}}$, pak ${ displaystyle mathbf {x} ^ { ast}}$ je optimální vektor pro výše uvedený problém s optimalizací. Předpokládejme to ${ displaystyle f ( mathbf {x})}$ a ${ displaystyle g_ {i} ( mathbf {x})}$, ${ displaystyle i = 1, ldots, m}$, jsou konvexní v ${ displaystyle mathbf {x}}$ a že existuje ${ displaystyle mathbf {x} _ {0} in mathbf {X}}$ takhle ${ displaystyle mathbf {g} ( mathbf {x} _ {0}) <0}$. Pak s optimálním vektorem ${ displaystyle mathbf {x} ^ { ast}}$ pro výše uvedený optimalizační problém je přidružen nezáporný vektor ${ displaystyle mathbf { mu} ^ { ast}}$ takhle ${ displaystyle L ( mathbf {x} ^ { ast}, mathbf { mu} ^ { ast})}$ je sedlovým bodem ${ displaystyle L ( mathbf {x}, mathbf { mu})}$.^[5]

Protože myšlenkou tohoto přístupu je najít a podpůrná nadrovina na proveditelné sadě ${ displaystyle mathbf { Gamma} = left { mathbf {x} in mathbf {X}: g_ {i} ( mathbf {x}) leq 0, i = 1, ldots, m že jo}}$, důkaz věty Karush – Kuhn – Tucker využívá věta o oddělení hyperplánů.^[6]

Systém rovnic a nerovnic odpovídajících podmínkám KKT obvykle není přímo vyřešen, kromě několika zvláštních případů, kdy uzavřená forma řešení lze odvodit analyticky. Obecně lze mnoho optimalizačních algoritmů interpretovat jako metody numerického řešení systému KKT rovnic a nerovností.^[7]

Nezbytné podmínky

Předpokládejme, že Objektivní funkce ${ displaystyle f: mathbb {R} ^ {n} rightarrow mathbb {R}}$ a omezovací funkce ${ displaystyle g_ {i}: , ! mathbb {R} ^ {n} rightarrow mathbb {R}}$ a ${ displaystyle h_ {j}: , ! mathbb {R} ^ {n} rightarrow mathbb {R}}$ jsou průběžně diferencovatelné v určitém okamžiku ${ displaystyle x ^ {*} in mathbb {R} ^ {n}}$. Li ${ displaystyle x ^ {*}}$ je místní optimum a problém optimalizace splňuje některé podmínky pravidelnosti (viz níže), pak existují konstanty ${ displaystyle mu _ {i} (i = 1, ldots, m)}$ a ${ displaystyle lambda _ {j} (j = 1, ldots, ell)}$zvané multiplikátory KKT, takže platí následující čtyři skupiny podmínek:

Diagram omezení nerovnosti pro optimalizační problémy

Stacionarita

Pro minimalizaci ${ displaystyle f (x)}$: ${ displaystyle nabla f (x ^ {*}) + součet _ {i = 1} ^ {m} mu _ {i} nabla g_ {i} (x ^ {*}) + součet _ { j = 1} ^ { ell} lambda _ {j} nabla h_ {j} (x ^ {*}) = mathbf {0}}$

Pro maximalizaci ${ displaystyle f (x)}$: ${ displaystyle - nabla f (x ^ {*}) + součet _ {i = 1} ^ {m} mu _ {i} nabla g_ {i} (x ^ {*}) + součet _ {j = 1} ^ { ell} lambda _ {j} nabla h_ {j} (x ^ {*}) = mathbf {0}}$

Prvotní proveditelnost

${ displaystyle g_ {i} (x ^ {*}) leq 0, { text {pro}} i = 1, ldots, m}$

${ displaystyle h_ {j} (x ^ {*}) = 0, { text {pro}} j = 1, ldots, ell , !}$

Duální proveditelnost

${ displaystyle mu _ {i} geq 0, { text {pro}} i = 1, ldots, m}$

Doplňková ochablost

${ displaystyle sum _ {i = 1} ^ {m} mu _ {i} g_ {i} (x ^ {*}) = 0.}$

Poslední podmínka je někdy psána v ekvivalentní formě: ${ displaystyle mu _ {i} g_ {i} (x ^ {*}) = 0, { text {pro}} i = 1, ldots, m.}$

V konkrétním případě ${ displaystyle m = 0}$, tj. když neexistují žádná omezení nerovnosti, podmínky KKT se změní na Lagrangeovy podmínky a multiplikátory KKT se nazývají Lagrangeovy multiplikátory.

Pokud jsou některé funkce nediferencovatelné, subdiferenciální jsou k dispozici verze podmínek Karush – Kuhn – Tucker (KKT).^[8]

Maticová reprezentace

Potřebné podmínky lze napsat s Jacobian matice omezujících funkcí. Nechat ${ displaystyle mathbf {g} (x): , ! mathbb {R} ^ {n} rightarrow mathbb {R} ^ {m}}$ být definován jako ${ displaystyle mathbf {g} (x) = left (g_ {1} (x), ldots, g_ {m} (x) right) ^ { top}}$ a nechte ${ displaystyle mathbf {h} (x): , ! mathbb {R} ^ {n} rightarrow mathbb {R} ^ { ell}}$ být definován jako ${ displaystyle mathbf {h} (x) = left (h_ {1} (x), ldots, h _ { ell} (x) right) ^ { top}}$. Nechat ${ displaystyle { boldsymbol { mu}} = left ( mu _ {1}, ldots, mu _ {m} right) ^ { top}}$ a ${ displaystyle { boldsymbol { lambda}} = left ( lambda _ {1}, ldots, lambda _ { ell} right) ^ { top}}$. Poté lze potřebné podmínky zapsat jako:

Stacionarita

Pro maximalizaci ${ displaystyle f (x)}$: ${ displaystyle nabla f (x ^ {*}) - D mathbf {g} (x ^ {*}) ^ { top} { boldsymbol { mu}} - D mathbf {h} (x ^ {*}) ^ { top} { boldsymbol { lambda}} = mathbf {0}}$

Pro minimalizaci ${ displaystyle f (x)}$: ${ displaystyle nabla f (x ^ {*}) + D mathbf {g} (x ^ {*}) ^ { top} { boldsymbol { mu}} + D mathbf {h} (x ^ {*}) ^ { top} { boldsymbol { lambda}} = mathbf {0}}$

Prvotní proveditelnost

${ displaystyle mathbf {g} (x ^ {*}) leq mathbf {0}}$

${ displaystyle mathbf {h} (x ^ {*}) = mathbf {0}}$

Duální proveditelnost

${ displaystyle { boldsymbol { mu}} geq mathbf {0}}$

Doplňková ochablost

${ displaystyle { boldsymbol { mu}} ^ { top} mathbf {g} (x ^ {*}) = 0.}$

Podmínky pravidelnosti (nebo omezení kvalifikace)

Lze se zeptat, zda bod minimalizátoru ${ displaystyle x ^ {*}}$ původního omezeného optimalizačního problému (za předpokladu, že existuje) musí splňovat výše uvedené podmínky KKT. Je to podobné, jako když se ptáte, za jakých podmínek minimalizátor ${ displaystyle x ^ {*}}$ funkce ${ displaystyle f (x)}$ v neomezeném problému musí podmínku splnit ${ displaystyle nabla f (x ^ {*}) = 0}$. Pro omezený případ je situace komplikovanější a lze uvést řadu (stále komplikovanějších) podmínek „pravidelnosti“, za kterých omezený minimalizátor rovněž splňuje podmínky KKT. Některé běžné příklady podmínek, které to zaručují, jsou uvedeny v následujících tabulkách, přičemž LICQ je nejčastěji používaný:

Omezení	Akronym	Tvrzení
Kvalifikace omezení linearity	LCQ	Li ${ displaystyle g_ {i}}$ a ${ displaystyle h_ {j}}$ jsou afinní funkce, pak není nutná žádná další podmínka.
Kvalifikace omezení lineární nezávislosti	LICQ	Přechody omezení aktivní nerovnosti a přechody omezení rovnosti jsou lineárně nezávislé na ${ displaystyle x ^ {*}}$.
Mangasarian-Fromovitz omezení kvalifikace	MFCQ	Gradienty omezení rovnosti jsou lineárně nezávislé na ${ displaystyle x ^ {*}}$ a existuje vektor ${ displaystyle d in mathbb {R} ^ {n}}$ takhle ${ displaystyle nabla g_ {i} (x ^ {*}) ^ { top} d <0}$ pro všechna aktivní omezení nerovnosti a ${ displaystyle nabla h_ {j} (x ^ {*}) ^ { top} d = 0}$ pro všechna omezení rovnosti.[9]
Konstantní kvalifikace omezení pozice	CRCQ	U každé podmnožiny přechodů aktivních omezení nerovnosti a přechodů omezení rovnosti je pořadí v blízkosti ${ displaystyle x ^ {*}}$ je konstantní.
Kvalifikace omezení konstantní pozitivní lineární závislosti	CPLD	Pro každou podmnožinu přechodů aktivních omezení nerovnosti a přechody omezení rovnosti, pokud je podmnožina vektorů lineárně závislá na ${ displaystyle x ^ {*}}$ s nezápornými skaláry spojenými s omezeními nerovnosti pak zůstává lineárně závislý v sousedství ${ displaystyle x ^ {*}}$.
Kvalifikace omezení kvazi-normality	QNCQ	Pokud jsou přechody omezení aktivní nerovnosti a přechody omezení rovnosti lineárně závislé na ${ displaystyle x ^ {*}}$ s přidruženými multiplikátory ${ displaystyle lambda _ {j}}$ pro rovnost a ${ displaystyle mu _ {i} geq 0}$ pro nerovnosti pak neexistuje žádná sekvence ${ displaystyle x_ {k} až x ^ {*}}$ takhle ${ displaystyle lambda _ {j} neq 0 Rightarrow lambda _ {j} h_ {j} (x_ {k})> 0}$ a ${ displaystyle mu _ {i} neq 0 Rightarrow mu _ {i} g_ {i} (x_ {k})> 0.}$
Slaterův stav	SC	Pro konvexní problém (tj. za předpokladu minimalizace, ${ displaystyle f, g_ {i}}$ jsou konvexní a ${ displaystyle h_ {j}}$ je afinní), existuje bod ${ displaystyle x}$ takhle ${ displaystyle h (x) = 0}$ a ${ displaystyle g_ {i} (x) <0.}$

To lze ukázat

LICQ ⇒ MFCQ ⇒ CPLD ⇒ QNCQ

a

LICQ ⇒ CRCQ ⇒ CPLD ⇒ QNCQ

(a konverze nejsou pravdivé), i když MFCQ není ekvivalentní CRCQ.^[10]V praxi se dává přednost slabším kvalifikacím, protože se vztahují na širší výběr problémů.

Dostatečné podmínky

V některých případech jsou nezbytné podmínky také dostatečné pro dosažení optimality. Obecně platí, že nezbytné podmínky nejsou dostatečné pro dosažení optimality a jsou vyžadovány další informace, například Dostatečné podmínky druhého řádu (SOSC). Pro plynulé funkce zahrnuje SOSC druhé derivace, což vysvětluje jeho název.

Nezbytné podmínky jsou dostatečné pro optimálnost, pokud objektivní funkce ${ displaystyle f}$ problému maximalizace je konkávní funkce, omezení nerovnosti ${ displaystyle g_ {j}}$ jsou průběžně diferencovatelné konvexní funkce a omezení rovnosti ${ displaystyle h_ {i}}$ jsou afinní funkce. Podobně, pokud objektivní funkce ${ displaystyle f}$ problému minimalizace je konvexní funkce, nezbytné podmínky jsou také dostatečné pro optimálnost.

Martin v roce 1985 ukázal, že širší třídou funkcí, v nichž podmínky KKT zaručují globální optimálnost, jsou tzv. Typ 1 funkce invex.^[11][12]

Dostatečné podmínky druhého řádu

Pro hladký, nelineární optimalizace problémů, je dostatečná podmínka druhého řádu dána následujícím způsobem.

Řešení ${ displaystyle x ^ {*}, lambda ^ {*}, mu ^ {*}}$ ve výše uvedené části je omezené místní minimum, pokud pro lagrangisty,

${ Displaystyle L (X, lambda, mu) = f (x) + součet _ {i = 1} ^ {m} mu _ {i} g_ {i} (x) + součet _ {j = 1} ^ { ell} lambda _ {j} h_ {j} (x)}$

pak,

${ displaystyle s ^ {T} nabla _ {xx} ^ {2} L (x ^ {*}, lambda ^ {*}, mu ^ {*}) s geq 0}$

kde ${ displaystyle s neq 0}$ je vektor splňující následující,

${ displaystyle left [ nabla _ {x} g_ {i} (x ^ {*}), nabla _ {x} h_ {j} (x ^ {*}) right] ^ {T} s = 0}$

kde pouze ta aktivní omezení nerovnosti ${ displaystyle g_ {i} (x)}$ odpovídající přísné doplňkovosti (tj. kde ${ displaystyle mu _ {i}> 0}$). Řešením je přísně omezené místní minimum v případě, že nerovnost je také přísná.

Li ${ displaystyle s ^ {T} nabla _ {xx} ^ {2} L (x ^ {*}, lambda ^ {*}, mu ^ {*}) s = 0}$by měla být použita Taylorova expanze Lagrangeova třetího řádu k ověření, zda ${ displaystyle x ^ {*}}$ je místní minimum. Minimalizace ${ displaystyle f (x_ {1}, x_ {2}) = (x_ {2} -x_ {1} ^ {2}) (x_ {2} -3x_ {1} ^ {2})}$ je dobrým protikladem, viz také Peano povrch.

Ekonomika

Často v matematická ekonomie přístup KKT se používá v teoretických modelech za účelem získání kvalitativních výsledků. Například,^[13] zvažte společnost, která maximalizuje své tržby s omezením minimálního zisku. Pronájem ${ displaystyle Q}$ být množství vyrobeného výstupu (bude vybráno), ${ displaystyle R (Q)}$ být tržbami z prodeje s kladným prvním derivátem as nulovou hodnotou při nulovém výstupu, ${ displaystyle C (Q)}$ být výrobní náklady s kladným prvním derivátem as nezápornou hodnotou při nulovém výstupu, a ${ displaystyle G _ { min}}$ být pozitivní minimální přijatelná úroveň zisk, pak je problém smysluplný, pokud se příjmová funkce vyrovná, takže je nakonec méně strmá než nákladová funkce. Problém vyjádřený v dříve uvedené minimalizační formě je

Minimalizovat ${ displaystyle -R (Q)}$

podléhá

${ displaystyle G _ { min} leq R (Q) -C (Q)}$

${ displaystyle Q geq 0,}$

a podmínky KKT jsou

${ displaystyle { begin {aligned} & left ({ frac {{ text {d}} R} {{ text {d}} Q}} right) (1+ mu) - mu left ({ frac {{ text {d}} C} {{ text {d}} Q}} right) leq 0, [5pt] & Q geq 0, [5pt] & Q left [ left ({ frac {{ text {d}} R} {{ text {d}} Q}} right) (1+ mu) - mu left ({ frac {{ text {d}} C} {{ text {d}} Q}} vpravo) vpravo] = 0, [5 bodů] & R (Q) -C (Q) -G _ { min} geq 0 , [5pt] & mu geq 0, [5pt] & mu [R (Q) -C (Q) -G _ { min}] = 0. end {zarovnáno}}}$

Od té doby ${ displaystyle Q = 0}$ by porušilo omezení minimálního zisku, máme ${ displaystyle Q> 0}$ a tedy třetí podmínka znamená, že první podmínka platí s rovností. Řešení, které rovnost dává

${ displaystyle { frac {{ text {d}} R} {{ text {d}} Q}} = { frac { mu} {1+ mu}} vlevo ({ frac {{ text {d}} C} {{ text {d}} Q}} vpravo).}$

Protože to bylo dáno ${ displaystyle { text {d}} R / { text {d}} Q}$ a ${ displaystyle { text {d}} C / { text {d}} Q}$ jsou přísně pozitivní, tato nerovnost spolu s podmínkou nezápornosti ${ displaystyle mu}$ zaručuje to ${ displaystyle mu}$ je pozitivní, a tak firma maximalizující výnosy pracuje na úrovni výstupu, na které vedlejší příjem ${ displaystyle { text {d}} R / { text {d}} Q}$ je méně než mezní náklady ${ displaystyle { text {d}} C / { text {d}} Q}$ - výsledek, který je zajímavý, protože kontrastuje s chováním a maximalizace zisku firma, která funguje na úrovni, na které jsou si rovni.

Hodnotová funkce

Pokud přehodnotíme problém s optimalizací jako problém s maximalizací s omezeními konstantní nerovnosti:

${ displaystyle { text {Maximalizovat}} ; f (x)}$

${ displaystyle { text {předmět}} }$

${ displaystyle g_ {i} (x) leq a_ {i}, h_ {j} (x) = 0.}$

Hodnotová funkce je definována jako

${ displaystyle V (a_ {1}, ldots, a_ {n}) = sup limity _ {x} f (x)}$

${ displaystyle { text {předmět}} }$

${ displaystyle g_ {i} (x) leq a_ {i}, h_ {j} (x) = 0}$

${ displaystyle j in {1, ldots, ell }, i in {1, ldots, m },}$

takže doména ${ displaystyle V}$ je ${ displaystyle {a in mathbb {R} ^ {m} mid { text {pro některé}} x v X, g_ {i} (x) leq a_ {i}, i in {1, ldots, m } }.}$

Vzhledem k této definici každý koeficient ${ displaystyle mu _ {i}}$ je rychlost, s jakou se hodnotová funkce zvyšuje jako ${ displaystyle a_ {i}}$ zvyšuje. Tedy pokud každý ${ displaystyle a_ {i}}$ je interpretováno jako omezení zdroje, koeficienty vám řeknou, o kolik zvýšení zdroje zvýší optimální hodnotu naší funkce ${ displaystyle f}$. Tato interpretace je obzvláště důležitá v ekonomii a používá se například v problémy s maximalizací užitku.

Zobecnění

S extra multiplikátorem ${ displaystyle mu _ {0} geq 0}$, což může být nula (pokud ${ displaystyle ( mu _ {0}, mu, lambda) neq 0}$), před ${ displaystyle nabla f (x ^ {*})}$ podmínky stacionárnosti KKT se promění

${ displaystyle { begin {seřazeno} & mu _ {0} , nabla f (x ^ {*}) + sum _ {i = 1} ^ {m} mu _ {i} , nabla g_ {i} (x ^ {*}) + sum _ {j = 1} ^ { ell} lambda _ {j} , nabla h_ {j} (x ^ {*}) = 0, [4pt] & mu _ {j} g_ {i} (x ^ {*}) = 0, quad i = 1, dots, m, end {zarovnáno}}}$

které se nazývají Podmínky Fritze Johna. Tato podmínka optimality platí bez omezení omezení a je ekvivalentní podmínce optimality KKT nebo (ne-MFCQ).

Podmínky KKT patří do širší třídy nezbytných podmínek prvního řádu (FONC), které umožňují plynulé funkce pomocí subderiváty.

Viz také

• Farkasovo lemma
• Lagrangeův multiplikátor
• The Metoda Big M., pro lineární problémy, které rozšiřují simplexní algoritmus k problémům, které obsahují omezení „větší než“.
• Povolená proměnná

Reference

Další čtení

• Andreani, R .; Martínez, J. M .; Schuverdt, M. L. (2005). "O vztahu mezi podmínkou konstantní pozitivní lineární závislosti a kvalifikací omezení kvazinormality". Journal of Optimization Theory and Applications. 125 (2): 473–485. doi:10.1007 / s10957-004-1861-9. S2CID  122212394.
• Avriel, Mordechaj (2003). Nelineární programování: Analýza a metody. Doveru. ISBN  0-486-43227-0.
• Boltyanski, V .; Martini, H .; Soltan, V. (1998). „The Kuhn – Tuckerova věta“. Geometrické metody a problémy s optimalizací. New York: Springer. str. 78–92. ISBN  0-7923-5454-0.
• Boyd, S .; Vandenberghe, L. (2004). „Podmínky optimality“ (PDF). Konvexní optimalizace. Cambridge University Press. str. 241–249. ISBN  0-521-83378-7.
• Kemp, Murray C .; Kimura, Yoshio (1978). Úvod do matematické ekonomie. New York: Springer. str.38–73. ISBN  0-387-90304-6.
• Rau, Nicholas (1981). "Lagrangeovy multiplikátory". Matice a matematické programování. Londýn: Macmillan. str. 156–174. ISBN  0-333-27768-6.
• Nocedal, J .; Wright, S. J. (2006). Numerická optimalizace. New York: Springer. ISBN  978-0-387-30303-1.
• Sundaram, Rangarajan K. (1996). „Omezení nerovnosti a teorém Kuhna a Tuckera“. První kurz teorie optimalizace. New York: Cambridge University Press. str. 145–171. ISBN  0-521-49770-1.

externí odkazy

• Karush – Kuhn – Tuckerovy podmínky s odvozením a příklady
• Příklady a návody k podmínkám KKT