Wykład 3

3. Optymalizacja z ograniczeniami

Sformułujemy teraz warunki konieczne dla istnienia rozwiązań zagadnienia optymalizacyjnego:

min f(x)
(Subscript[g, i])(x) ≤ 0,  i = 1, 2,  ... , m                                    (ograniczenia LE)                                   (3.1)
(Subscript[h, j])(x) = 0,  j = 1, 2,  ... , 
      p,  p<n                       (ograniczenia EQ).

Założenie.  f,(Subscript[g, i]),(Subscript[h, j]):U→(R^n) są funkcjami klasy (C^1), zbiór U jest otwarty.	
	Zbiór D ⊂ U wektorów, spełniających ograniczenia typu LE i EQ nazywać będziemy zbiorem dopuszczalnym. Oznaczmy przez: (Subscript[D, LE]) zbiór wektorów, spełniających wszystkie ograniczenia LE,  (Subscript[D, EQ]) zbiór wektorów, spełniających wszystkie ograniczenia EQ. Oczywiście, D = (Subscript[D, LE]) ⋂ (Subscript[D, EQ]).
	Szukamy warunków koniecznych jakie musi spełniać punkt minimum globalnego \(TraditionalForm\`\(x\^*\)\) w zbiorze dopuszczalnym D.

Redukcja 3.1. Wystarczy ograniczyć się do przypadku, gdy wszystkie ograniczenia są typu LE. Każde ograniczenie typu EQ zastąpimy dwoma ograniczeniami: ograniczenie (Subscript[h, j])(x) = 0 zastąpimy przez (Subscript[g, m + 2  j - 1])(x) ≤ 
        0,  (Subscript[g, m + 2  j])(x)≤0  gdzie (Subscript[g, m + 2  j - 1])(x) = (Subscript[h, j])(x) i (Subscript[g, m + 2  j])(x) = -(Subscript[h, j])(x) dla  j = 1, 2,  ... , p. Mamy więc M = m + 2  p ograniczeń typu LE

Definicja 3.1. Ograniczenie u(x) jest aktywne  w punkcie \(TraditionalForm\`\(x\^*\)\) gdy zachodzi równość \(TraditionalForm\`u(\(x\^*\)) = 0\).
Oznaczmy przez  \(TraditionalForm\`AKT = {i : \(g\_i\)(\(x\^*\)) = 0}\) zbiór ograniczeń aktywnych. Wszystkie ograniczenia EQ są z definicji aktywne więc indeksy o numerach i = m + 1,  ... , m + 2  p należą do zbioru AKT. Jednak zbiór AKT może być pusty.

Redukcja 3.2. Wystarczy ograniczyć się do przypadku, gdy wszystkie ograniczenia są aktywne. Niech
			(Subscript[D, AKT]) = {x ∈ U :  (Subscript[g, i])(
                  x) ≤ 0, i ∈ AKT}, (Subscript[D, 0]) = {x ∈ U :  (Subscript[g, i])(x) < 0, 
          i ∉ AKT}
Zbiór (Subscript[D, 0]) jest otwarty (wynika to z ciągłości (Subscript[g, i])). Tak więc zagadnienie

min f(x)
(Subscript[g, i])(x) ≤ 0,  i = 1, 2,  ... , M, x ϵ U

jest równoważne zagadnieniu

min f(x)
(Subscript[g, i])(x) ≤ 0,  i ϵ AKT, x ϵ (Subscript[U, 0])=U⋂(Subscript[D, 0])

Warunki można tak przenumerować aby pierwszych (Subscript[M, 0]) było aktywnych

Niech \(TraditionalForm\`C\_i = {x : \ 
            x\^T\ ▽\ \(\(g\_i\)(\(x\^*\))\) ≤ \((\(x\^*\))\)\^T\ ▽\ \(\(g\_i\)(\(x\^*\))\)}\) będzie półprzestrzenią wyznaczoną przez styczną do (Subscript[g, i]) w punkcie \(TraditionalForm\`\(x\^*\)\ ϵ\ C\_i\). Jak łatwo sprawdzić, (Subscript[C, i]) jest zbiorem wypukłym, zaś \(TraditionalForm\`C = \(⋂\_\(i ∈ AKT\)C\_i\)\) jako część wspólna wypukłych półpłaszczyzn zbiorem wypukłym, zawierającym \(TraditionalForm\`\(x\^*\)\).

Niech \(TraditionalForm\`C\_0 = {h : \ 
            h\^T\ ▽\ \(\(g\_i\)(\(x\^*\))\) ≤ \ 
              0, \ \ i\  ∈ \ AKT}\). Wtedy \(TraditionalForm\`∀ \_\(μ ≥ 0\)\ μ\ C\_0 ⊂ C\_0\),  \(TraditionalForm\`C = \(x\^*\) + C\_0\) czyli C jest stożkiem o wierzchołku \(TraditionalForm\`\(x\^*\)\) i kierunkach w zbiorze (Subscript[C, 0]).

Definicja 3.2. Punkt  \(TraditionalForm\`\(x\^*\)\) jest regularny gdy dla każdego  h ∈ (Subscript[C, 0]) istnieje otoczenie \(TraditionalForm\`\(\(U(\(x\^*\))\)\(\ \)\)\) oraz gładka, klasy (C^2) krzywa φ(t) taka, że:
1. \(TraditionalForm\`φ(0) = \(x\^*\)\), 2. φ' (0) = μ h dla pewnego μ>0, 3. (Subscript[∃ , (Subscript[t, 0])])\(TraditionalForm\`∀ \_\(0 < t < t\_0\)φ(t) ⊂ 
          U(\(x\^*\)) ⋂ D\)

Lemat 3.1. Jeżeli punkt  \(TraditionalForm\`\(x\^*\)\) jest regularny, h ∈ (Subscript[C, 0]) to \(TraditionalForm\`\(h\^T\) ▽\ \(f(\(x\^*\))\) ≥ 0\)

Dowód (niewprost)
(Subscript[∃ , (Subscript[h, 1])])(Subscript[h, 1]) ∈ (Subscript[C, 0])takie, że \(TraditionalForm\`\(h\_1\^T\) ▽\ \(f(\(x\^*\))\) < 
        0\). Funkcja ((Subscript[h, 1])^T) ▽ f(x) jako funkcja zmiennej x jest ciągła, więc istnieje otoczenie \(TraditionalForm\`U(\(x\^*\))\) takie, że w tym otoczeniu ((Subscript[h, 1])^T) ▽ f(x) < 0. Z regularności punktu \(TraditionalForm\`\(x\^*\)\)wynika, że istnieje otoczenie \(TraditionalForm\`\(U\_1\)(\(x\^*\)) ⊂ U(\(x\^*\))\) i gładka, klasy (C^2) krzywa φ(t) taka, że:
\(TraditionalForm\`φ(0) = \(x\^*\)\),  φ' (0) = μ (Subscript[h, 1]) dla pewnego μ>0,  (Subscript[∃ , (Subscript[t, 0])])\(TraditionalForm\`∀ \_\(0 ≤ t < t\_0\)φ(
            t) ⊂ \(U\_1\)(\(x\^*\)) ⋂ D\).
Rozwijając φ w pobliżu 0 w szereg Taylora mamy dla 0 ≤ t < (Subscript[t, 1]) < (Subscript[t, 0])
	\(TraditionalForm\`φ(
          t) = \(x\^*\) + μ\ t\ h\_1 + μ\ t\ \(γ(t)\)\) i γ(t)->0 gdy t -> 0+. 
Ponieważ \(TraditionalForm\`φ(
          t) ⊂ \(U\_1\)(\(x\^*\)) ⋂ D\) więc dla 0 ≤ t < (Subscript[t, 1]) ((Subscript[h, 1])^T) ▽ f(φ(
              t) ) < 0
Funkcja \(TraditionalForm\`\(\(y\^T\) \(▽\)\(\ \)\(f(φ(t))\)\(\ \)\)\)jako funkcja zmiennej y jest ciągła, wię istnieje otoczenie (Subscript[U, t])((Subscript[h, 1])) takie, że w tym otoczeniu  \(TraditionalForm\`\(\(y\^T\) \(▽\)\(\ \)\(f(φ(t))\)\(\ \)\)\)<0. 
Kładąc (Subscript[U, 0])(
          (Subscript[h, 1])) = (⋂_(0 ≤ t < 
                (Subscript[t, 1])))(Subscript[U, t])((Subscript[h, 1]))  mamy dla każdego y ϵ (Subscript[U, 0])((Subscript[h, 1])) i dla każdego 0 ≤ t < (Subscript[t, 1]),  \(TraditionalForm\`0 > \(y\^T\) ▽\ \(f(φ(
                t))\)\  = \(\(y\^T\) \(▽\)\(\ \)\(f(\(x\^*\) + μ\ t\ \((h\_1 + \ γ(t))\))\)\(\ \)\)\). 
Łatwo zauważyć, że dla dostatecznie małych θ>0 dla każdego y ϵ (Subscript[U, 0])((Subscript[h, 1])) i dla każdego 0 ≤ t < (Subscript[t, 1])zachodzi nierówność \(TraditionalForm\`\(\(\(y\^T\) ▽\ \(f(\(x\^*\) + θμ\ t\ \((h\_1 + \ γ(t))\))\)\)\(<\)\(0\)\(\ \)\)\)
Wektor (Subscript[h, 1]) +  γ(t) dla dostetecznie małych t należy do (Subscript[U, 0])((Subscript[h, 1])) więc zachodzi dla dostatecznie małych t > 0, \(TraditionalForm\`\(\((h\_1 + \ γ(
                    t))\)\^T\) ▽\ \(f(\(x\^*\) + θμ\ t\ \((h\_1 + \ γ(t))\))\) < 0\) a więc dla h = μ t ((Subscript[h, 1]) +  γ(t)) mamy \(TraditionalForm\`\(x\^*\) + h\  ∈ D\), \(TraditionalForm\`\(\(\(h\^T\) ▽\ \(f(\(x\^*\) + θ\ h)\)\)\(<\)\(0\)\(\ \)\)\). Wzór ten zachodzi dla dostatecznie małych t > 0. 
Wtedy, z rozwinięcia Taylora funkcji f mamy \(TraditionalForm\`f(\(x\^*\) + h) = 
        f(\(x\^*\)) + \(h\^T\) ▽\ \(f(\(x\^*\) + θ\ h)\) < f(\(x\^*\))\) co stanowi sprzeczność z założeniem, że w \(TraditionalForm\`\(x\^*\)\) jest minimum globalne ■

Stwierdzenie 3.1. Niech ograniczenie (Subscript[g, i])(x)∈(C^1) będzie  aktywne  w punkcie  \(TraditionalForm\`\(x\^*\) ∈ D\_LE\), h  wektorem takim, że dla pewnego otoczenia \(TraditionalForm\`U(\(x\^*\))\) punktu \(TraditionalForm\`\(x\^*\)\) zbiór  \(TraditionalForm\`U(\(x\^*\)) ⋂ \([\(x\^*\), \(x\^*\) + 
              h]\) ⊂ \(\(D\_LE\)\(.\)\)\)Wtedy

\(\(\(\ \)\(\(h\^T\) ∇g\_i \((\(x\^*\))\) ≤ 
      0\)\)\)

Dowód. Przypuśćmy niewprost, że \(\(h\^T\) ∇g\_i \((\(x\^*\))\) > 0\) Z ciągłości pochodnej wynika, że istnieje (Subscript[λ, 0]) > 0, że dla każdego 0 < λ ≤ (Subscript[λ, 0]) zachodzi

\(\(\(\ \)\(\(h\^T\) ∇g\_i \((\(x\^*\) + λ\ h)\) > 
      0\)\)\)

Oczywiście, \(\(\(\(x\^*\) + λ\ h\)\(∈\)\)\)(Subscript[D, LE]) oraz (Subscript[λ, 0]) można wybrać dowolnie małe. Wtedy z rozkładu Taylora mamy:

\(\(\(\ \)\(\(g\_i\) \((\(x\^*\) + λ\ h)\) = \(\(g\_i\) \((\(x\^*\))\) + λ\ \(h\^T\) ∇g\_i \((\(x\^*\) + θ\ λ\ h)\) = λ\ \(h\^T\) ∇g\_i \((\(x\^*\) + θ\ λ\ h)\) > 0\)\)\)\)

Z tego wynika, że istnieje punkt \(\(\(\(x\^*\) + λ\ h\)\(∈\)\)\)(Subscript[D, LE]) taki, że \(\(g\_i\) \((\(x\^*\) + λ\ h)\) > 0\) co stanowi sprzeczność bo ograniczenie (Subscript[g, i])(x) ≤ 0 nie jest spełnione w tym otoczeniu. ■

Twierdzenie 3.1. (Warunek konieczny istnienia minimum , warunki Kuhna-Tuckera, warunki Karusha-Kuhna-Tuckera) 
Niech w regularnym punkcie \(TraditionalForm\`\(x\^*\) ∈ D\) funkcja celu osiąga w tym punkcie minimum w dopusz-czalnym obszarze D  Wtedy:

\(∑\+\(i ∈ Akt\)u\_i\ ∇g\_i \((\(x\^*\))\) + ∑\+\(j = 1\)\%p\( v\_j\) ∇h\_j \((\(x\^*\))\)\)=-∇f\((\(x\^*\))\)                                                                   (3.2)

dla pewnych (Subscript[u, i]) ≥ 0 oraz (Subscript[v, j]).

Definicja 3.3. Punkty regularne, spełniające warunki (3.2) twierdzenia 3.1 nazywać będziemy punktami Kuhna-Tuckera (punktami KT)

Dowód 
W dowodzie wykorzystamy lemat Farkasa.

Lemat Farkasa (1902). Niech  A będzie macierzą o k wierszach i n kolumnach , b i h n-wymiarowymi wektorami, w wektorem k-wymiarowym. Równoważne są następujące warunki:

\(dla\ każdego\ h\ \ zachodzi\ implikacja\ A\ h ≥ 
        0\  ⇒ \(b\^T\) h ≥ 
        0\ , 
∃ u ≥ 
          0\ \(A\^T\) u = \(\(b\)\(.\)\)\)

Dla wektora q warunek q ≥ 0 oznacza, że wszystkie jego współrzędne są nieujemne.

Podstawiając w lemacie Farkasa

\(b = ∇f \((\(x\^*\))\), 
A = \(-\((\ ∇g\_1 \((\(x\^*\))\), ∇g\_2 \((\(x\^*\))\),  ... , ∇g\_\(M\_0\) \((\(x\^*\))\))\)\^T\), \)

uzyskamy z Lematu 3.1, że dla każdego h  zachodzi implikacja  A h ≥ 
          0  ⇒ (b^T) 
            h≥0 .
Z Lematu Farkasa mamy, że dla wektora u o nieujemnych składnikach
				\(∑\+\(i ∈ Akt\)u\_i\ ∇g\_i \((\(x\^*\))\) = \(-∇f\) \((\(x\^*\))\)\)

Dla j-tego ograniczenia typu równości (Subscript[h, j])(x) = 0 , \(TraditionalForm\`\(u\_\(m + 2  j - 
                  1\)\) ▽\ \(\(h\_j\)(\(x\^*\))\) + \(u\_\(m + 2  
                    j\)\)(\(-▽\)\ \(\(h\_j\)(\(x\^*\))\)) = \(\((u\_\(m + 2  j - 1\) - 
                u\_\(m + 2  j\))\) ▽\ \(\(h\_j\)(\(x\^*\))\) = \(v\_j\) ▽\ \(\(h\_j\)(\(x\^*\))\)\)\), 
				\(∑\+\(i ∈ Akt\)u\_i\ ∇g\_i \((\(x\^*\))\) + ∑\+\(j = 1\)\%p\( 
                    v\_j\) ∇h\_j \((\(x\^*\))\) = \(-∇f\) \((\(x\^*\))\)\)
dla pewnych (Subscript[u, i]) ≥ 0 oraz (Subscript[v, j]).

Warunek regularności jest istotny.

◼ Przykład 3.1
Obliczmy minimum globalne funkcji f(x) = (Subscript[x, 1]) z warunkami (Subscript[x, 2]) ≤ ((Subscript[x, 1])^3), (Subscript[x, 2]) ≥ 0. Rozwiązując to zadanie geometrycznie widzimy, że minimum globalne jest w \(TraditionalForm\`\(x\^*\) = \((0, 0)\)\^T\)

Zbiór \(TraditionalForm\`C\_0 = \({h = \((h\_1, 
                  h\_2)\) : \ \(h\^T\) ▽\ \(\(g\_1\)(\(x\^*\))\) ≤ 
                  0, \ \(h\^T\) ▽\ \(\(g\_2\)(\(x\^*\))\) ≤ 0} = {h = \((h\_1, 0)\), \ \(h\_1\) ϵ\ R}\)\). Nie istnieje krzywa φ leżąca w zbiorze dopuszczalnym dla h = (-1, 0), gdyż wtedy (Subscript[φ, 1])(
          t) = -μ t + t(Subscript[γ, 1])(t) ≥ 0 dla dostatecznie małych t > 0. Wtedy -μ  + (Subscript[γ, 1])(t) ≥ 
        0 i przechodzą z t  do 0 otrzymamy -μ≥0 co jest sprzeczne z założeniem, że μ>0.■

Sprawdzenie, czy punkt \(TraditionalForm\`\(\(x\^*\)\(\ \)\)\)jest  regularny jest trudne. Prawdziwe jest

Twierdzenie 3.2. Punkt \(TraditionalForm\`\(x\^*\) ∈ D\) jest regularny jeżeli wektory:

\(\(\(\ \)\(∇g\_i \((\(x\^*\))\), \ 
    i ∈ Akt, 
∇h\_j \((\(x\^*\))\), \ j = 1, 
    2,  ... , p\)\)\)

są liniowo niezależne.

Z tego wynika, że łączna liczba ograniczeń aktywnych i ograniczeń typu EQ w punkcie regularnym nie może przekraczać n.

Zbadanie, czy układ wektorów jest liniowo niezależny jest ważne przy ustaleniu czy analizowany punkt jest regularny.

Twierdzenie 3.3. ( warunek dostateczny na to, by punkt był regularny). Dany jest układ  fukcji n zmiennych (Subscript[x, 1]), (Subscript[x, 2]),  ... , (Subscript[x, n]) , będących ograniczeniami typu EQ ( funkcji (Subscript[h, 1]), (Subscript[h, 2]),  ... , (Subscript[h, p])) i ograniczeniami aktywnymi typu LE (funkcji (Subscript[g, (Subscript[i, 1])]), (Subscript[g, (Subscript[i, 2])]),  ... , (Subscript[g, (Subscript[i, k])])). Punkt \(TraditionalForm\`\(x\^*\)\) jest regularny jeśli macierz 
(({{\(▽\ \(\(g\_\(i\_1\)\)(\(x\^*\))\)\), \(\(▽\ \(\(g\_\(i\_2\)\)(\(x\^*\))\) ... \) ▽\ \(\(g\_\(i\_k\)\)(\(x\^*\))\)\ \ ▽\ \(\(h\_1\)(\(x\^*\))\)\ ▽\ h\_2\ \((\(x\^*\))\) ... \)}})▽ (Subscript[h, p]) \((\(x\^*\))\)) jest rzędu k+p.

Przykład 3.2 (Minimum w punkcie nieregularnym)

Znajdźmy rozwiązanie zadania optymalizacyjnego:

f (x, y) = x =  MIN!, 
(x^2) ≤ 
      0.

Gradienty, związane z tym zadaniem mają postać:

∇f (x) = 1, 
∇g (x) = 
      2  x.

Ograniczenie g(x) jest aktywne, gdyż jedyny punkt , spełniający to ograniczenie to punkt 0. Tak więc jest to również rozwiązanie naszego zagadnienia. 
	Jednocześnie jest to punkt nieregularny, gdyż ∇g(0)=0 a to nie jest wektor liniowo niezależny.

Warunki Kuhna Tuckera wymagają dodatkowych założeń, gdyż w naszym przykładzie, gdy g jest ograniczeniem aktywnym, musiałyby zachodzić:

u (2  x) = -1, 
(x^2) = 
      0, 
u ≥ 0.

co stanowi sprzeczność.  ■

Przykład 3.3 (Warunki Kuhna-Tuckera)

Znajdźmy punkty KT dla zagadnienia:

f (x, y) = (x^2) + (y^2) =  MIN!, 
x + 
        y ≥ 5, 
x + 2  y = 
      3.

Sprowadzając do postaci standardowej

f (x, y) = (x^2) + (y^2) =  MIN!, 
g (x, 
          y) = 5 - x - y ≤ 
        0, 
h (x, y) = x + 2  y - 3 = 
        0.

∇f (x, 
          y) = (((2  x, 2  y))^T), 
∇g (x, 
          y) = (((-1, -1))^T), 
∇h (x, 
          y) = (((1, 2))^T)

Łatwo sprawdzic, że wszystkie punkty, należące do zbioru dopuszczalnego są regularne. Niech \(TraditionalForm\`\((\(x\^*\), \(y\^*\))\)\) będzie  rozwiązaniem naszego zadania.  Rozważmy dwa przypadki:
I. g(x) jest aktywne w \(TraditionalForm\`\((\(x\^*\), \(y\^*\))\)\). 
	Wtedy muszą zachodzić warunki Kuhna Tuckera:

u (-1, -1) + 
        v (1, 2) = -(2  x, 2  y)
5 - x - y = 0, 
x + 2  y - 3 = 
      0, 
u ≥ 0.

Układ ten ma rozwiązanie:

\(\(x\^*\) = 7, \(y\^*\) = \(-2\), u = 32, 
    v = 18, 
f \((\(x\^*\), \(y\^*\))\) = 
      53. \)

II. g(x) nie jest aktywne w \(TraditionalForm\`\((\(x\^*\), \(y\^*\))\)\). 
	Warunki Kuhna Tuckera w tym przypadku przybiorą postać:

v (1, 2) = -(2  x, 2  y), 
5 - x - y < 
      0, 
x + 2  y - 3 = 0.

Układ ten nie ma rozwiązania, gdyż pierwiastki układu, składającego się z pierwszego i trzeciego równania x = (3/5) i y = (6/5) nie spełniaj nierówności.
Tak więc rozwiązanie \(TraditionalForm\`\(x\^*\) = 7\) i \(TraditionalForm\`\(y\^*\) = \(-2\)\), jako jedyne, jest odpowiedzią w naszym zadaniu.  ■

Warunki Kuhna Tuckera można uprościć, wprowadzając dodatkowe zmienne (Subscript[s, i]) ,  i = 1, 2,  ... , m , które przekształcą wszystkie ograniczenia LE na ograniczenia EQ. Wtedy też wszystkie ograniczenia są aktywne. Nasze zadanie będzie równoważne :

min f(x)
\(TraditionalForm\`\(\(g\^*\)\_i\)(x, s) = \(\(g\_i\)(x) + s\_i\^2 = 
          0\), \ i = 1, 2,  ... , m\)                
(Subscript[h, j])(x) = 0,  j = 1, 2,  ... , 
      p,  p<n

Zauważmy, że

\(∇f \((x, s)\) = \((∇f \((x)\), 
        0)\), 
∇\(g\^*\)\_i \((x, 
          s)\) = \((∇g\_i \((x)\), 
        2  s\_i)\), \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \((3.2)\)\)
∇(Subscript[h, j]) (x, s) = (∇(Subscript[h, j]) (x), 
        0)

W powyższych równaniach 0, (Subscript[e, i]) są wektorami m-wymiarowymi: pierwszy składa się z samych 0, drugi ma na i-tym miejscu 1 a na pozostałych miejscach 0.

Zapisując w nowej sytuacji warunki Kuhna Tuckera, otrzymamy:

\(∑\+\(i = 1\)\%m u\_i\ ∇\(g\^*\)\_i \((\(x\^*\), \(s\^*\))\) + ∑\+\(j = 1\)\%p\( 
                v\_j\) ∇h\_j \((\(x\^*\), \(s\^*\))\) = \(-∇f\) \((\(x\^*\), \(s\^*\))\)\)

co po uwzględnieniu (3.2) daje układ (zmodyfikowane warunki Kuhna-Tuckera (warunki K-T))

\(∑\+\(i = 1\)\%m u\_i\ ∇g\_i \((\(x\^*\))\) + ∑\+\(j = 1\)\%p\( v\_j\) ∇h\_j \((\(x\^*\))\) = \(-∇f\) \((\(x\^*\))\), \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \((3.3)\)\)
\(\(u\_i\) \(s\^*\)\_i = 0, \ 
    u\_i ≥ 
      0, \ 
\(g\_i\) \((\(x\^*\))\) + \((\(s\^*\))\)\_i\^2 = 0, i = 1, 2,  ... , 
    m, 
\(h\_j\) \((\(x\^*\))\) = \(0\ j = 1\), 2,  ... , 
    p\)

Gdy (Subscript[s, i]) = 0 to ograniczenie (Subscript[g, i]) jest aktywne, gdy (Subscript[s, i]) ≠ 0 to (Subscript[u, i]) = 0 i ograniczenie (Subscript[g, i]) nie bierze udziału w wyznaczeniu \(TraditionalForm\`\(x\^*\)\). Z poprzednich rozważań wynika, że liczba ograniczeń aktywnych, więc takich, dla których (Subscript[s, i]) = 0 wraz z liczbą ograniczeń EQ nie może przekraczać n.

Przykład 3.4 (Rozwiązanie przykładu 3.3 zmodyfikowaną metodą K-T)

Zapiszmy od razu warunki (3.3):

\(u \((\(-1\), 1)\) + 
        v \((1, 2)\) = \(-\((2  x, 
          2  y)\)\), \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 
u\ s = 0, \ 
    u ≥ 0, \ 
\(-x\) - y + 5 + s\^2 = 
      0, 
x + 2  y - 3 = 0, \)

Wyznaczmy x i y z ostatnich dwóch równań:

x = 7 + 2  (s^2),  y = -2 - (s^2)

Podstawiając do pierwszego równania otrzymamy, że 3u = 32 + 10  (s^2) > 0, co od razu daje rozwiązanie s = 0,  x = 7,  y = -2.   ■