Выпуклая оптимизация - условия Фрица-Джона

Необходимые условия

Теорема

Рассмотрим задачу - $ min f \ left (x \ right) $ такую, что $ x \ in X $, где X - открытое множество в $ \ mathbb {R} ^ n $, и пусть $ g_i \ left (x \ right) \ leq 0, \ forall i = 1,2, .... m $.

Пусть $ f: X \ rightarrow \ mathbb {R} $ и $ g_i: X \ rightarrow \ mathbb {R} $

Пусть $ \ hat {x} $ - допустимое решение и пусть f и $ g_i, i \ in I $ дифференцируемы в $ \ hat {x} $, а $ g_i, i \ in J $ непрерывны в $ \ hat { x} $.

Если $ \ hat {x} $ решает указанную выше проблему локально, то существуют $ u_0, u_i \ in \ mathbb {R}, i \ in I $ такие, что $ u_0 \ bigtriangledown f \ left (\ hat {x} \ справа) + \ displaystyle \ sum \ limits_ {я \ in I} u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) $ = 0

где $ u_0, u_i \ geq 0, i \ in I $ и $ \ left (u_0, u_I \ right) \ neq \ left (0,0 \ right) $

Кроме того, если $ g_i, i \ in J $ также дифференцируемы в $ \ hat {x} $, то указанные выше условия могут быть записаны как -

$ u_0 \ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ limits_ {i = 1} ^ m u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) = 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 $

Замечания

• $ u_i $ называются лагранжевыми множителями.

• Условие выполнимости $ \ hat {x} $ для данной задачи называется прямым допустимым условием.

• Требование $ u_0 \ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ limits_ {i = 1} ^ m ui \ bigtriangledown g_i \ left (x \ right) = 0 $ называется двойной выполнимостью состояние.

• Условие $ u_ig_i \ left (\ hat {x} \ right) = 0, i = 1, 2, ... m $ называется условием дополнительной расслабленности. Это условие требует $ u_i = 0, i \ in J $

• Вместе первичное возможное условие, двойное условие выполнимости и дополнительная расслабленность называются условиями Фрица-Джона.

Достаточные условия

Теорема

Если существует $ \ varepsilon $ -окрестность $ \ hat {x} N_ \ varepsilon \ left (\ hat {x} \ right), \ varepsilon> 0 $ такая, что f псевдовыпукло над $ N_ \ varepsilon \ left ( \ hat {x} \ right) \ cap S $ и $ g_i, i \ in I $ строго псевдовыпуклы над $ N_ \ varepsilon \ left (\ hat {x} \ right) \ cap S $, то $ \ hat { x} $ - локальное оптимальное решение описанной выше проблемы. Если функция f псевдовыпуклая в $ \ hat {x} $ и если $ g_i, i \ in I $ являются строго псевдовыпуклой и квазивыпуклой функцией в $ \ hat {x}, \ hat {x} $ является глобальным оптимальным решением проблемы. описано выше.

пример

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

  такие, что $ x_ {1} ^ {2} + x_ {2} ^ {2} \ leq 5, x_1 + 2x_2 \ leq 4, x_1, x_2 \ geq 0 $ и $ \ hat {x} = \ left (2 , 1 \ вправо) $

  Пусть $ 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 $ и $ g_4 \ left (x_1, x_2 \ right) = -x_2 $.

  Таким образом, указанные выше ограничения можно записать как -

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

  $ g_2 \ влево (x_1, x_2 \ вправо) \ leq 0, $

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

  $ g_4 \ left (x_1, x_2 \ right) \ leq 0 $ Таким образом, $ I = \ left \ {1,2 \ right \} $, следовательно, $ 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 ) $ и $ \ bigtriangledown g_2 \ left (\ hat {x} \ right) = \ left (1,2 \ right) $

  Таким образом, помещая эти значения в первое условие условий Фрица-Джона, мы получаем:

  $ u_0 = \ frac {3} {2} u_2, \: \: u_1 = \ frac {1} {2} u_2, $ и пусть $ u_2 = 1 $, поэтому $ u_0 = \ frac {3} {2} , \: \: u_1 = \ frac {1} {2} $

  Таким образом, условия Фрица Джона выполнены.

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

  такое, что $ x_2- \ left (1-x_1 \ right) ^ 3 \ leq 0 $,

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

  Пусть $ 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 $

  Таким образом, вышеуказанные ограничения могут быть записаны как -

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

  $ g_2 \ влево (x_1, x_2 \ вправо) \ leq 0, $

  Таким образом, $ 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) $ и $ g_2 \ left (\ hat {x} \ right) = \ left (0, -1 \ right ) $

  Таким образом, помещая эти значения в первое условие условий Фрица-Джона, мы получаем:

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

  Таким образом, условия Фрица Джона выполнены.