Optymalizacja wypukła - warunki Fritza-Johna

Niezbędne warunki

Twierdzenie

Rozważmy problem - $ min f \ left (x \ right) $ tak, że $ x \ in X $ gdzie X jest zbiorem otwartym w $ \ mathbb {R} ^ n $ i niech $ g_i \ left (x \ right) \ leq 0, \ forall i = 1,2, .... m $.

Niech $ f: X \ rightarrow \ mathbb {R} $ i $ g_i: X \ rightarrow \ mathbb {R} $

Niech $ \ hat {x} $ będzie wykonalnym rozwiązaniem i niech f i $ g_i, i \ in I $ są różniczkowalne przy $ \ hat {x} $ i $ g_i, i \ in J $ są ciągłe przy $ \ hat { x} $.

Jeśli $ \ hat {x} $ rozwiązuje powyższy problem lokalnie, to istnieje $ u_0, u_i \ in \ mathbb {R}, i \ in I $ takie, że $ u_0 \ bigtriangledown f \ left (\ hat {x} \ po prawej) + \ Displaystyle \ suma \ limity_ {i \ in I} u_i \ bigtriangledown g_i \ lewo (\ kapelusz {x} \ po prawej) $ = 0

gdzie $ u_0, u_i \ geq 0, i \ in I $ and $ \ left (u_0, u_I \ right) \ neq \ left (0,0 \ right) $

Ponadto, jeśli $ g_i, i \ in J $ są również różniczkowalne w $ \ hat {x} $, to powyższe warunki można zapisać jako -

$ u_0 \ bigtriangledown f \ lewo (\ kapelusz {x} \ po prawej) + \ Displaystyle \ suma \ limit_ {i = 1} ^ m u_i \ bigtriangledown g_i \ lewo (\ kapelusz {x} \ w prawo) = 0 $

$ u_ig_i \ left (\ hat {x} \ right) $ = 0

$ u_0, u_i \ geq 0, \ forall i = 1,2, ...., m $

$ \ left (u_0, u \ right) \ neq \ left (0,0 \ right), u = \ left (u_1, u_2, s, u_m \ right) \ in \ mathbb {R} ^ m $

Uwagi

• $ u_i $ nazywane są mnożnikami Lagrange'a.

• Warunek, że $ \ hat {x} $ będzie wykonalny dla danego problemu, nazywa się pierwotnym warunkiem wykonalnym.

• Wymóg $ u_0 \ bigtriangledown f \ lewo (\ kapelusz {x} \ prawej) + \ Displaystyle \ suma \ limit_ {i = 1} ^ m ui \ bigtriangledown g_i \ lewo (x \ prawo) = 0 $ nazywa się podwójną wykonalnością stan: schorzenie.

• Warunek $ u_ig_i \ left (\ hat {x} \ right) = 0, i = 1, 2, ... m $ nazywa się warunkiem uzupełniającym luzu. Ten warunek wymaga $ u_i = 0, i \ in J $

• Pierwotny warunek wykonalności, podwójny warunek wykonalności i uzupełniająca się niezdolność nazywane są warunkami Fritza-Johna.

Wystarczające warunki

Twierdzenie

Jeśli istnieje $ \ varepsilon $ -nighbourhood of $ \ hat {x} N_ \ varepsilon \ left (\ hat {x} \ right), \ varepsilon> 0 $ takie, że f jest pseudo wypukłe nad $ N_ \ varepsilon \ left ( \ hat {x} \ right) \ cap S $ i $ g_i, i \ in I $ są ściśle pseudo wypukłe na $ N_ \ varepsilon \ left (\ hat {x} \ right) \ cap S $, a następnie $ \ hat { x} $ jest lokalnie optymalnym rozwiązaniem problemu opisanego powyżej. Jeśli f jest pseudowypukłe w $ \ hat {x} $ i jeśli $ g_i, i \ in I $ są zarówno funkcją ściśle pseudokwypukłą, jak i quasikonwypukłą w $ \ hat {x}, \ hat {x} $ jest globalnym optymalnym rozwiązaniem problemu opisane powyżej.

Przykład

• $ min \: f \ left (x_1, x_2 \ right) = \ left (x_1-3 \ right) ^ 2 + \ left (x_2-2 \ right) ^ 2 $

  takie, że $ x_ {1} ^ {2} + x_ {2} ^ {2} \ leq 5, x_1 + 2x_2 \ leq 4, x_1, x_2 \ geq 0 $ And $ \ hat {x} = \ left (2 , 1 \ po prawej) $

  Niech $ g_1 \ left (x_1, x_2 \ right) = x_ {1} ^ {2} + x_ {2} ^ {2} -5, $

  $ g_2 \ left (x_1, x_2 \ right) = x_1 + 2x_2-4, $

  $ g_3 \ left (x_1, x_2 \ right) = - x_1 $ i $ g_4 \ left (x_1, x_2 \ right) = -x_2 $.

  Zatem powyższe ograniczenia można zapisać jako -

  $ g_1 \ left (x_1, x_2 \ right) \ leq 0, $

  $ g_2 \ left (x_1, x_2 \ right) \ leq 0, $

  $ g_3 \ left (x_1, x_2 \ right) \ leq 0 $ i

  $ g_4 \ left (x_1, x_2 \ right) \ leq 0 $ Zatem $ I = \ left \ {1,2 \ right \} $, zatem $ u_3 = 0, u_4 = 0 $

  $ \ bigtriangledown f \ left (\ hat {x} \ right) = \ left (2, -2 \ right), \ bigtriangledown g_1 \ left (\ hat {x} \ right) = \ left (4,2 \ right) ) $ i $ \ bigtriangledown g_2 \ left (\ hat {x} \ right) = \ left (1,2 \ right) $

  W ten sposób umieszczając te wartości w pierwszym warunku warunków Fritza-Johna, otrzymujemy -

  $ u_0 = \ frac {3} {2} u_2, \: \: u_1 = \ frac {1} {2} u_2, $ i niech $ u_2 = 1 $, więc $ u_0 = \ frac {3} {2} , \: \: u_1 = \ frac {1} {2} $

  Zatem warunki Fritza Johna są spełnione.

• $ min f \ left (x_1, x_2 \ right) = - x_1 $.

  takie, że $ x_2- \ left (1-x_1 \ right) ^ 3 \ leq 0 $,

  $ -x_2 \ leq 0 $ i $ \ hat {x} = \ left (1,0 \ right) $

  Niech $ g_1 \ left (x_1, x_2 \ right) = x_2- \ left (1-x_1 \ right) ^ 3 $,

  $ g_2 \ left (x_1, x_2 \ right) = - x_2 $

  Zatem powyższe ograniczenia można zapisać jako -

  $ g_1 \ left (x_1, x_2 \ right) \ leq 0, $

  $ g_2 \ left (x_1, x_2 \ right) \ leq 0, $

  Zatem $ I = \ left \ {1,2 \ right \} $

  $ \ bigtriangledown f \ left (\ hat {x} \ right) = \ left (-1,0 \ right) $

  $ \ bigtriangledown g_1 \ left (\ hat {x} \ right) = \ left (0,1 \ right) $ i $ g_2 \ left (\ hat {x} \ right) = \ left (0, -1 \ right) ) $

  W ten sposób umieszczając te wartości w pierwszym warunku warunków Fritza-Johna, otrzymujemy -

  $ u_0 = 0, \: \: u_1 = u_2 = a> 0 $

  Zatem warunki Fritza Johna są spełnione.