Rozważmy problem optymalizacyjny z ograniczeniami mieszanymi (8.1). Załóżmy, że pewnym punkcie x¯∈W spełniony jest warunek pierwszego rzędu, tzn. istnieją wektory μ∈0,∞m i λ∈Rl, takie że

D⁢f⁢x¯+∑i∈I⁢x¯μi⁢D⁢gi⁢x¯+∑j=1lλj⁢D⁢hj⁢x¯=0T,μi⁢gi⁢x¯=0,⁢i=1,2,…,m.

Możemy teraz zapisać warunek pierwszego rzędu w skróconej formie:

Dx⁢L⁢x¯,μ,λ=0T,⁢oraz⁢⁢μi⁢gi⁢x¯=0,⁢i=1,2,…,m,

gdzie Dx oznacza różniczkowanie względem zmiennej x∈Rn.

Bez dowodu pozostawiamy następujące uogólnienie powyższego twierdzenia:

Podamy teraz warunek dostateczny istnienia rozwiązania lokalnego. Zwróćmy uwagę na to, że warunek ten implikuje, iż rozwiązanie jest ścisłe. Pozostaje więc szara strefa, gdzie jest spełniony warunek konieczny drugiego rzędu, lecz nie zachodzi warunek dostateczny drugiego rzędu. Podobnie jak w przypadku optymalizacji bez ograniczeń, na to nie ma niestety rady.

Zanim przejdziemy do dowodu podkreślmy, iż w powyższym twierdzeniu nie zakłada się regularności punktu ograniczeń.

Opiszemy teraz ogólny algorytm postępowania w przypadku rozwiązywania problemów optymalizacyjnych z ograniczeniami mieszanymi.

Krok 1. Szukamy punktów podejrzanych:

	A1={x∈X:	w punkcie x nie zachodzi warunek regularności},
	A2={x∈X:	w punkcie x zachodzi warunek regularności
		i spełnione są warunki pierwszego rzędu}.

Krok 2. Sprawdzamy, czy w punktach ze zbiorów A1,A2 spełnione są założenia tw. 7.6, tzw. warunki dostateczne pierwszego rzędu. Jeśli tak, to w punktach tych są rozwiązania globalne. Pozostałe kroki podejmujemy, jeśli

• nie znaleźliśmy żadnego rozwiązania globalnego, lub

• chcemy znaleźć wszystkie rozwiązania globalne, lub

• chcemy znaleźć wszystkie rozwiązania lokalne.

Usuwamy ze zbiorów A1,A2 punkty, które są rozwiązaniami globalnymi. Oznaczmy nowe zbiory A1′,A2′.

Krok 3. Eliminujemy ze zbioru A2′ te punkty, gdzie nie zachodzi warunek konieczny drugiego rzędu. Pozostałe punkty oznaczamy A2′′.

Krok 4. W każdym punkcie ze zbioru A1′∩A2′′ sprawdzamy warunek dostateczny drugiego rzędu. Punkty, w których jest spełniony, są rozwiązaniami lokalnymi.

Krok 5. Optymalność punktów ze zbioru A1′∩A2′′, w których nie jest spełniony warunek dostateczny drugiego rzędu sprawdzamy innymi metodami.

W tym podrozdziale opiszemy bardzo dokładnie rozwiązanie następującego problemu optymalizacyjnego:

x1-12+x22→min,2⁢k⁢x1-x22≤0,x=x1,x2∈R2,

gdzie k>0 jest parametrem.

Zauważmy, że w każdym punkcie, gdzie aktywne jest ograniczenie, spełniony jest warunek liniowej niezależności ograniczeń: pierwsza pochodna ograniczenia wynosi 2⁢k,-2⁢x2≠0T. Wynika stąd, że A1=∅.

Funkcja Lagrange'a dla powyższego problemu ma postać:

L⁢x1,x2;μ=x1-12+x22+μ⁢2⁢k⁢x1-x22.

Zapiszmy warunek pierwszego rzędu:

		2⁢x1-1,2⁢x2+μ⁢2⁢k,-2⁢x2=0T,		(9.3)
		μ⁢2⁢k⁢x1-x22=0,		(9.4)
		μ≥0.

Sprawdźmy, czy możliwe jest μ=0. Wówczas z równania (9.3) dostajemy

2⁢x1-1=0,⁢2⁢x2=0,

co pociąga x1=1, x2=0. Punkt ten nie jest dopuszczalny: nie spełnia warunku nierównościowego dla żadnego k>0. Wnioskujemy zatem, że μ>0 i warunek konieczny pierwszego rzędu może być spełniony tylko w punktach, w których ograniczenie nierównościowe jest aktywne:

2⁢k⁢x1-x22=0.

(9.5)

Rozpiszmy równanie (9.3):

x1-1+μ⁢k=0,x2-μ⁢x2=0.

Z drugiego równania wynika, że albo μ=1 albo x2=0. Jeśli x2=0, to z (9.5) dostajemy x1=0. Punkt 0,0 wraz z mnożnikiem Lagrange'a μ=1/k spełnia warunek pierwszego rzędu.

Rozważmy teraz przypadek μ=1. Wówczas z równania x1-1+μ⁢k=0 dostajemy x1=1-k. Jeśli k>1, to x1<0 i równanie (9.5) nie ma rozwiązania. Dla k=1 dostajemy punkt 0,0, zaś dla k∈0,1 dwa punkty

x1=1-k,⁢x2=±2⁢k⁢1-k.

Podsumowując: A1=∅ oraz

		A2=0,0⁢⁢dla⁢⁢k≥1,
		A2=0,0,1-k,2⁢k⁢1-k,1-k,-2⁢k⁢1-k⁢⁢dla⁢⁢0<k<1.

Funkcja g1⁢x1,x2=2⁢k⁢x1-x22 nie jest quasi-wypukła, wiec nie możemy skorzystać z twierdzenia 7.6 stwierdzającego dostateczność warunku pierwszego rzędu. Zatem A2′=A2.

Przechodzimy do kroku 3 i sprawdzamy warunek konieczny drugiego rzędu dla punktów z A2′. Rozważmy najpierw punkt 0,0. Odpowiada mu mnożnik Lagrange'a μ=1/k. Pierwsza pochodna funkcji Lagrange'a ma postać:

DxL(x1,x2,1/k)=[(2(x1-1)+2,2x2(1-1k)].

Macierz drugich pochodnych to;

Dx2⁢L⁢x1,x2,1/k=2,00,2⁢1-1k.

Na mocy twierdzenia wystarczy sprawdzić, że

dT⁢2,00,2⁢1-1k⁢d≥0

dla wektorów d∈R2∖0 spełniających D⁢g1⁢0,0⁢d=2⁢k,0⁢d=0, czyli takich że d1=0. Wstawiając do powyższej nierówności dostajemy 1-1k⁢d22≥0. Nierówność ta zachodzi dla k≥1: w punkcie 0,0 może być rozwiązanie lokalne. Dla k<1 nierówność nie zachodzi, więc w 0,0 nie ma rozwiązania lokalnego.

Załóżmy teraz 0<k<1 i rozważmy dwa pozostałe punkty. W obu przypadkach mnożnik Lagrange'a μ=1. Mamy zatem

		DxL(x1,x2,1)=[(2(x1-1)+2k,0],
		Dx2⁢L⁢x1,x2,1=2,00,0.

Macierz drugich pochodnych jest nieujemnie określona, więc warunek konieczny drugiego rzędu jest spełniony w obu punktach. Podsumowując:

		A2′′=0,0⁢⁢dla⁢⁢k≥1,
		A2′′=1-k,2⁢k⁢1-k,1-k,-2⁢k⁢1-k⁢⁢dla⁢⁢0<k<1.

Przechodzimy do sprawdzenia warunku dostatecznego drugiego rzędu. W przypadku k>1 macierz drugich pochodnych funkcji Lagrange'a jest dodatnio określona, więc na mocy tw. 9.3 w punkcie 0,0 jest ścisłe rozwiązanie lokalne. Niestety nie możemy nic powiedzieć o punkcie 0,0, gdy k=1.

Rozważmy przypadek 0<k<1. Zajmijmy się punktem x¯=1-k,2⁢k⁢1-k. Musimy sprawdzić warunki tw. 9.3:

dT⁢2,00,0⁢d=2⁢d12>0

dla d∈R2∖0 spełniającego 2⁢k,-2⁢2⁢k⁢1-k⁢d=0, czyli d1=1k⁢2⁢k⁢1-k⁢d2. A zatem jeśli d≠0, to d1≠0 i w punkcie x¯ spełniony jest warunek dostateczny drugiego rzędu: x¯ jest ścisłym rozwiązaniem lokalnym. Analogicznie dowodzimy, że punkt 1-k,-2⁢k⁢1-k jest również ścisłym rozwiązaniem lokalnym.

Pozostaje jeszcze przypadek k=1. Choć 0,0 jest rozwiązaniem globalnym, to nie udało nam się tego pokazać korzystając z teorii Kuhna-Tuckera. Łatwo można to jednak udowodnić bezpośrednio.