Wykład 4

4. Warunki dostateczne istnienia minimum

Warunki konieczne Kuhna-Tuckera nie muszą być dostateczne

Przykład 4.1 (W punktach KT nie ma minimum)

Znajdź punkty Kuhna-Tuckera dla zagadnienia

f = 2 x - y = MIN!,  2 x + 
        y≤(x^2)

Rozwiązanie. Gradienty funkcji celu i ograniczenia LE (w postaci standardowej) mają postać:

▽ f=(((2, -1))^T), ▽ g = (((-2 x + 2, 1))^T)

Warunki K-T:

u (-2 x + 2) = -2,  u = 1, 2 x + y - (x^2) + (s^2) = 0,  
    u s = 0,  u ≥ 0

Rozwiązanie tego układu jest punkt KT \(TraditionalForm\`\(x\^*\) = \((2, 0)\)\), w którym f nie ma minimum. Funkcja ta nie ma bowiem w ogóle minimów. ◼

Szczególn rolę w zagadnieniach optymalizacji stanowi zagadnienie zwane programem wypukłym.

Definicja 4.1. Programem wypukłym nazywamy zagadnienie optymalizacji, w którym:
	• funkcja celu f jest wypukła, • funkcje (Subscript[g, i]) są wypukłe, • funkcje (Subscript[h, j]) są liniowe, • wspólna dziedzina U dla funkcji f, (Subscript[g, i]) jest wypukła.

Definicja 4.2. Funkcja p(x) jest wypukła (słabo wypukła) gdy ∀ x, y ϵ U∀ 0≤λ≤1 p((1 - λ) 
              x + λ y) ≤ (1 - λ) p(x)+λ p(y). 
Funkcja jest ściśle wypukła, gdy ∀ x ≠ y ϵ U∀ 0<λ<1 p((1 - λ) 
              x + λ y) < (1 - λ) p(x)+λ p(y)

Twierdzenie 4.1. Funkcja p ϵ (C^2) jest wypukła jeżeli jej hesjan (▽^2) p jest nieujemnie określony. Jest ściśle wypukła, gdy jej hesjan jest dodatnio określony.

Przykład 4.2. (Program niewypukły)

Zadanie optymalizacyjne z przykładu 4.1 jest programem niewypukłym.
Funkcja f = 2 x - y ma hesjan (({{0, 0}, {0, 0}})) a więc jest wypukła, ale nie ściśle wypukła.
Funkcja g =  2 x + y - (x^2) ma hesjan (({{-2, 0}, {0, 0}})) a więc jest niewypukła. ◼

Przykład 4.3. (Program wypukły)

Zagadnienie optymalizacyjne

f = (((x - 5))^2) + (((y - 1))^2) + x y,  x + y ≤ 4,  
    2 x + (x^2) + (y^2) ≤ 16,  ((x^2)/y) ≤ 1,  
    y > 0

jest programem wypukłym.
Hesjany poszczególnych funkcji są równe, odpowiednio, (({{2, 1}, {1, 2}})), (({{0, 0}, {0, 0}})), (({{2, 0}, {0, 2}})), (({{(2/y), -((2 x)/(y^2))}, {-((2 x)/(y^2)), ((2 (x^2))/(y^3))}})), (({{0, 0}, {0, 0}}))

Funkcja f i drugie ograniczenie są ściśle wypukłe, pierwsze i ostatnie ograniczenie, jako funkcje liniowe są słabo wypukłe. Ograniczenie ((x^2)/y) ≤ 1 jest słabo wypukłe w obszarze dopuszczalnym (w dziedzinie tej nierówności jest to funkcja niewypukła). Zagadnienie to ma jedyne minimum w \(TraditionalForm\`\(x\^*\) = \((5\/4, 25\/16)\)\) jak to widać z poniższego rysunku. Jest to też jedyny punkt KT dla tego zagadnienia.

Tak jest zawsze. Warunki Kuhna-Tuckera są dostateczne dla programu wypukłego. Mówi o tym:

Twierdzenie 4.2. Punkt KT programu wypukłego jest jego minimum globalnym.

Dowód.(niewprost)
Niech \(TraditionalForm\`\(x\^*\)\) będzie punktem KT programu wypukłego

f (x) = MIN,  (Subscript[g, i]) (x) ≤ 
      0,  (Subscript[h, j]) (x) = 0

gdzie f,  (Subscript[g, i]) są wypukłe (Subscript[h, j])(x) = ((Subscript[a, j])^T) x + (Subscript[b, j]). AKT niech będzie zbiorem tych indeksów w których ograniczenia (Subscript[g, i]) są aktywne w \(TraditionalForm\`\(\(x\^*\)\(.\)\(\ \)\)\)
Jeżeli \(TraditionalForm\`\(x\^*\)\) nie jest minimum globalnym to istnieje (x^1) ϵ D takie, że f((x^1))<\(f(\(x\^*\))\). Niech \(TraditionalForm\`w = x\^1 - \(x\^*\)\).

1. \(TraditionalForm\`w\^T\ ▽\ \(\(h\_j\)(\(x\^*\))\) = 
        0\)
Dowód. \(TraditionalForm\`\(\(\ \)\(w\^T\ ▽\ \(\(h\_j\)(\(x\^*\))\) = \(\(w\^T\) 
            a\_j = \(\(a\_j\^T\)(
              x\^1 - \(x\^*\)) = \(\((\(a\_j\^T\) x\^1 + 
                    b\_j)\) - \((\(a\_j\^T\) \(x\^*\) + b\_j)\) = \(\(h\_j\)(
                    x\^1) - \(h\_j\)(\(x\^*\)) = 
                0\ •\)\)\)\)\)\)\)

2. \(TraditionalForm\`w\^T\ ▽\ \(\(g\_i\)(\(x\^*\))\) ≤ 0\) gdy i ϵ AKT
Dowód. \(TraditionalForm\`\(g\_i\)(\(x\^*\)) = 0\) (bo jest to ograniczenie aktywne w \(TraditionalForm\`\(x\^*\)\)) 
dla t dostatecznie małych \(TraditionalForm\`\(x\^*\) + t\ w = \((1 - t)\) \(x\^*\) + 
          t\ \(x\^1\) ϵ\ D\)(dziedzina jest zbiorem otwartym, wypukłym). Stąd \(TraditionalForm\`\(\(\ \ \)\(\(g\_i\)(\(x\^*\) + t\ w) ≤ 
        0\)\)\)

\(w\^T\ ▽\ \(g\_i\) \((\(x\^*\))\) = \(lim\+\(t -> \(\(0\)\(+\)\)\)\ \ \(\(g\_i\) \((\(x\^*\) + t\ w)\) - \(g\_i\) \((\(x\^*\))\)\)\/t = 
        lim\+\(t -> \(\(0\)\(+\)\)\)\ \ \(\(g\_i\) \((\(x\^*\) + t\ w)\)\)\/t ≤ 0  •\)\)

3. \(TraditionalForm\`w\^T\ ▽\ \(f(\(x\^*\))\) < 0\)

\(\(w\^T\) ▽\ f \((\(x\^*\))\) = \(\(\(\(d\ f \((\(x\^*\) + t\ w)\)\)\/\(d\ t\)\)\( | \_\(t = 0\)\)\) = 
        lim\+\(t -> \(\(0\)\(+\)\)\)\ \ \(f \((\(x\^*\) + t\ w)\) - f \((\(x\^*\))\)\)\/t\), 
\(f \((\(x\^*\) + t\ w)\) - f \((\(x\^*\))\)\)\/t = \(\(f \((\((1 - t)\) \(x\^*\) + t\ x\^1)\) - f \((\(x\^*\))\)\)\/t ≤ \(\((1 - t)\) f \((\(x\^*\))\) + t\ f \((x\^1)\) - f \((\(x\^*\))\)\)\/t = 
        f \((x\^1)\) - f \((\(x\^*\))\)\)\)

dla t>0 dostatecznie małych (z wypukłości f)

\(\(w\^T\) ▽\ f \((\(x\^*\))\) = \(\(\(\(d\ f \((\(x\^*\) + t\ w)\)\)\/\(d\ t\)\)\( | \_\(t = 0\)\)\) = 
        lim\+\(t -> \(\(0\)\(+\)\)\)\ \ \(f \((\(x\^*\) + t\ w)\) - f \((\(x\^*\))\)\)\/t ≤ f \((x\^1)\) - f \((\(x\^*\))\) < 
          0  •\)\)

Sprzeczność uzyskamy z warunku Kuhna-Tuckera:

\(0 < \(-w\^T\) ▽\ f \((\(x\^*\))\)\)=(w^T)(\(∑\+\(i ∈ AKT\)\(u\_i\) ▽\ \(g\_i\) \((\(x\^*\))\)\)+(∑_j)(Subscript[v, j])\(▽\ \(\(h\_j\)(\(x\^*\))\)\))=\(∑\+\(i ∈ AKT\)\(u\_i\) \(w\^T\) ▽\ \(g\_i\) \((\(x\^*\))\)\)+(∑_j)(Subscript[v, j])\(\(w\^T\) ▽\ \(\(h\_j\)(\(x\^*\))\)\)=\(∑\+\(i ∈ AKT\)\(u\_i\) \(w\^T\) ▽\ \(g\_i\) \((\(x\^*\))\) ≤ 
            0  ■\)

Dla zagadnienia optymalizacyjnego, które nie jest programem wypukłym, punkty KT nie muszą być, jak to pokazuje przykład 4.1 minimum globalnym. Jak pamiętamy, w przypadku optymalizacji bez ograniczeń warunkiem dostatecznym była dodatnia określoność hesjanu. W przypadku optymalizacji z ograniczeniami hesjan też odgrywa ważną rolę.

Twierdzenie 4.3. (warunek dostateczny istnienia minimum).
Niech \(TraditionalForm\`\(x\^*\)\) będzie punktem Kuhna-Tuckera zagadnienia

f (x) = MIN,  (Subscript[g, i]) (x) ≤ 
      0,  (Subscript[h, j]) (x) = 0

ze współczynnikami \(TraditionalForm\`\(u\^*\) = \((u\_1, u\_2,  ... , u\_k)\)\^T\) i \(TraditionalForm\`\(\(\(v\^*\) = \((v\_1, v\_2,  ... , v\_p)\)\^T\)\(\ \)\(,\)\)\)zbiór aktywnych ograniczeń ma indeksy 1,2,...,k.
Niech wektor d ≠ 0 spełnia warunki

\(\(d\^T\) ▽\ \(g\_i\) \((\(x\^*\))\) = 0, \ i = 1, 
    2,  ... , 
    k, \ \(d\^T\) ▽\ \(h\_j\) \((\(x\^*\))\) = 0, \ j = 1, 
    2, \(\(...\) \(p . \ \ \ \ \ \ \((4.1)\)\)\)\)

Warunkiem dostatecznym na to, by \(TraditionalForm\`\(x\^*\)\) był punktem minimum globalnego jest, by dla dowolnego d spełniającego warunki (4.1) zachodziła nierówność:

(d^T)(\(\(\(\(▽\^2\) 
                    f \((\(x\^*\))\) + ∑\)\+\(\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \)\(i ∈ 
                  AKT\)\)\)\(\(u\_i\) ▽\^2\ \(g\_i\) \((\(x\^*\))\)\)\)+(∑_j)(Subscript[v, j])\(▽\^2\ \(\(h\_j\)(\(x\^*\))\)\))d>\(0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \((4.2)\)\)

Przykład 4.4 (warunek dostateczny dla przykładu 4.1)

Punkt KT \(TraditionalForm\`\(x\^*\) = \((2, 0)\)\^T\) \(TraditionalForm\`\(u\^*\) = 1\), ▽ f=(((2, -1))^T), ▽ g = (((-2 , 1))^T).  (▽^2) f=(({{0, 0}, {0, 0}}))=(▽^2) g
Niech d = ((((Subscript[d, 1]), (Subscript[d, 2])))^T) ≠ 0. Warunek (4.1) oznacza, że (Subscript[d, 2]) = 2  (Subscript[d, 1]), (Subscript[d, 1]) ≠ 0

(d^T)(\(\(\(\(▽\^2\) 
                    f \((\(x\^*\))\) + ∑\)\+\(\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \)\(i ∈ 
                  AKT\)\)\)\(\(u\_i\) ▽\ \(g\_i\) \((\(x\^*\))\)\)\)+(∑_j)(Subscript[v, j])\(▽\ \(\(h\_j\)(\(x\^*\))\)\))d=((Subscript[d, 1]), 2  (Subscript[d, 1]))(({{0, 0}, {0, 0}}))(({{(Subscript[d, 1])}, {2  (Subscript[d, 1])}}))=0

Punkt KT nie spełnia wawunku dostatecznego - nie ma w nim minimum.

Przykład 4.5. (warunek dostateczny)

Rozwiąż zagadnienie optymalizacji (nie jest to program wypukły)

f = (x^2) + 9  (y^2) + (z^2) =  MIN!,  
    xyz ≥ 1

Rozwiązanie
Znajdźmy punkty KT dla tego zagadnienia

\(▽\ f \((x)\) = \((2\ x, 18  y, 2  z)\)\^T, \ ▽g = \((\(-yz\), \(-xz\), \(-xy\))\)\^T\)

Warunki KT:

u y z = 2  x,  u x z = 18  y,  u x y = 2  z,  
    xyz = 1 + (s^2)

Ponieważ z tych warunków wynika, że żadna z wartości x, y, z nie jest równa 0, więc mnożąc pierwsze 3 równania odpowiednio przez x, y, z otrzymamy

u (1 + (s^2)) = 2  (x^2),  u (1 + (s^2)) = 18  (y^2),  
    u (1 + (s^2)) = 2  (z^2),  
    x y z = 1 + (s^2)⟹u > 0, s = 0

Rozwiążemy te równania, przyjmując α, β takie, że (α^2) = (β^2) = 1 x = 3  α y,  z = 3  β y i podstawiając do ostatniego równania mamy 9αβ (y^3) = 1 czyli y = αβγ gdzie (γ^3) = (1/9). Stąd x =  3  βγ,  
      z = 3  αγ, u = 2 (x^2) = 18  (γ^2).
Hesjany funkcji f i g są postaci

\(\(▽\^2\) f \((\(x\^*\))\)\)=(({{2, 0, 0}, {0, 18, 0}, {0, 0, 2}})),\(\(▽\^2\) g \((\(x\^*\))\)\)=(({{0, -3 αγ, -αβγ}, {-3 αγ, 0, -3 βγ}, {-αβγ, -3 βγ, 2}})),
\(\(▽\^2\) f \((\(x\^*\))\) + 
          u\ \(▽\^2\) g \((\(x\^*\))\)\)=(({{2, -6 α, -2 αβ}, {-6 α, 18, -6 β}, {-2 αβ, -6 β, 2}}))

Warunek 4.1 jest spełniony, gdy ((Subscript[d, 1]), (Subscript[d, 2]), (Subscript[d, 3]))(({{-3 β(γ^2)}, {-9 αβ(γ^2)}, {-3 α(γ^2)}}))=0 co jest równoważne warunkowi, że (Subscript[d, 1]) β + 
          3  (Subscript[d, 2]) αβ + (Subscript[d, 3]) α = 0 czyli (Subscript[d, 1]) + 
          3  (Subscript[d, 2]) α + (Subscript[d, 3]) αβ = 0

Warunek (4.2) , po uwzgędnieniu równania -(Subscript[d, 1]) = 
        3  (Subscript[d, 2]) α + (Subscript[d, 3]) αβ ma postać:

((Subscript[d, 1]), (Subscript[d, 2]), (Subscript[d, 3]))(({{2, -6 α, -2 αβ}, {-6 α, 18, -6 β}, {-2 αβ, -6 β, 2}}))(({{(Subscript[d, 1])}, {(Subscript[d, 2])}, {(Subscript[d, 3])}}))=8 (9 (Subscript[d, 2]^2) + 3 β (Subscript[d, 2]) (Subscript[d, 3]) + (Subscript[d, 3]^2)) = 
        8 (((((Subscript[d, 3]) + (3/2) β (Subscript[d, 2])))^2) + (27/4) 
                  ((Subscript[d, 2])^2)) ≥ 0

Gdy wektor d nie jest zerowy to nierówność jest ostra. Zadanie ma więc 4 punkty minimum globalnego  x =  3  βγ,  
      z = 3  αγ, y = αβγ gdzie (α^2) = (β^2) = 1,(γ^3) = (1/9)◼