Kuhn-Tucker-betingelsene

For maksimering av \(f(\mathbf{x})\) gitt ulikhetsbibetingelsene \(g_j(\mathbf{x}) \leq b_j\) er Kuhn-Tucker-betingelsene (nødvendige betingelser under passende regularitetsbetingelser):

\(\nabla f(\mathbf{x}^*) - \sum_j \lambda_j \nabla g_j(\mathbf{x}^*) = \mathbf{0}\) (stasjonaritetsbetingelse)
\(\lambda_j \geq 0\) for alle \(j\) (ikke-negativitet for maksimering)
\(g_j(\mathbf{x}^*) \leq b_j\) (primal feasibility)
\(\lambda_j(g_j(\mathbf{x}^*) - b_j) = 0\) (komplementær slakkhet: enten er bibetingelsen bindende eller \(\lambda_j = 0\))

For minimering med \(g_j(\mathbf{x}) \geq c_j\): skriv om til \(-g_j(\mathbf{x}) \leq -c_j\) og bruk samme betingelser, eller bruk KT direkte med \(\lambda_j \geq 0\) for \(g_j \geq c_j\).

Kandidatpunkter og aktive bibetingelser

Komplementær slakkhet betyr at for hvert \(j\) er enten \(\lambda_j = 0\) (bibetingelsen er ikke aktiv/bindende) eller \(g_j(\mathbf{x}^*) = b_j\) (bibetingelsen er aktiv). Typisk analyse: gå gjennom de mulige kombinasjonene av aktive/inaktive bibetingelser (casene \(\lambda_j=0\) vs. \(g_j=b_j\)) og sjekk hvilke som er konsistente.

Suffisiensbetingelser

Hvis \(f\) er konkav og bibetingelsene er konvekse (\(g_j\) konkav for maksimering under \(g_j \leq b_j\)), er Kuhn-Tucker-betingelsene tilstrekkelige for globalt maksimum. Fra H2023, Problem 4: maks \(F(x,y) = x+y-xy-x^2-y^2\) gitt \(12x+6y \geq 11\) og \(x+y \leq 1\). Her er \(F\) konkav (sjekk Hessian), og begge bibetingelsene er lineære (dermed konvekse). KT-betingelsene gir kandidatpunkt, og konkaviteten beviser globalitet.

Eksempel (KT med to ulikheter)

Maks \(f(x,y) = xy\) gitt \(x+y \leq 4\) og \(x,y \geq 0\).

KT-betingelser (maximering, \(g_1 = x+y \leq 4\), \(g_2 = -x \leq 0\), \(g_3 = -y \leq 0\))

Stasjonaritet: \(y = \lambda_1\), \(x = \lambda_1\)

Så \(x = y\). Komplementær slakkhet: enten \(\lambda_1=0\) (men da \(x=y=0\), ikke maksimum) eller \(x+y=4\)

Aktiv: \(2x=4\), \(x=y=2\), \(\lambda_1=2\), \(f(2,2)=4\)

Studieguide: Kuhn-Tucker Conditions and Inequality Constraints

Studieguide: Kuhn-Tucker Conditions and Inequality Constraints