KKTtingimused

KKTtingimukset, eli Karush-Kuhn-Tucker -ehdot, ovat epälineaarisen ohjelmoinnin rajoitetun optimoinnin keskeisiä ehtoja, jotka antavat välittömät ehdot optimaalisen ratkaisun löytämiseksi. Niitä sovelletaan kun tavoitteena on minimoida funktio f(x) tietyin rajoittein: g_i(x) ≤ 0 (i = 1, ..., m) ja h_j(x) = 0 (j = 1, ..., p). Ehdot ovat nimetty tutkijoiden Karushin, Kuhnin ja Tuckerin mukaan; monissa yhteyksissä puhutaan myös KKT-ehdoista.

Matemaattisesti asettaa ongelman

minimoi f(x) jatkuvin differentiablien g_i(x) ja h_j(x) suhteen

algebra: g_i(x) ≤ 0, i = 1,...,m; h_j(x) = 0, j = 1,...,p.

Lagrangian L(x, λ, μ) = f(x) + sum_i λ_i g_i(x) + sum_j μ_j h_j(x).

KKT-ehdot koostuvat neljästä osasta: primaarifasiliteetti (g_i(x) ≤ 0, h_j(x) = 0), dualisuus (λ_i ≥ 0), stationaarisuus (nabla_x L(x, λ, μ) = 0) sekä komplementaarinen vapaus (λ_i g_i(x) = 0 jokaiselle i).

Ehdot ovat välttämättömiä ja joidenkin ehtojen mukaan riittäviä. Jos ongelma on konveksi (f on convex, g_i ovat convex, h_j ovat affinisia) ja Slaterin ehto pätee, KKT-ehdot ovat sekä necessary että sufficient optima varten. Ilman konveksisuutta KKT-ehdot ovat vain välttämättömiä eivätkä takuta optimaalisuutta.

Käytännössä KKT-ongelma muodostaa epälineaarisen yhtälö- ja epäyhtälöjärjestelmän, jonka ratkaiseminen antaa potentiaaliset optimit. Eri algoritmit, kuten sisäinen piste- ja aktiivisuhdemenetelmät, hyödyntävät näitä ehtoja. Multipliers- eli KKT-vakioita tulkitaan usein varjohinnansijaisiksi. Variaatioina on subgradient-merkintö sekä ei-smooth- eli epäjatkuvien rajoitteiden laajennukset.