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

Рассмотрим задачу — $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 { х}$.

Если $\ hat {x}$ решает вышеуказанную проблему локально, то существует $u_0, u_i \ in \ mathbb {R}, i \ in I$, такой, что $u_0 \ bigtriangledown f \ left (\ hat {x} \ справа) + \ displaystyle \ sum \ limit_ {i \ 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 \ limit_ {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 \ limit_ {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$

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

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

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

Требование $u_0 \ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ limit_ {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}$ является глобальным оптимальным решением задачи описано выше.

minf left(x1,x2 right)= left(x1−3 right)2+ left(x2−2 right)2$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 \ left (x_1, x_2 \ right) \ 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)$

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

u0= frac32u2,u1= frac12u2,$u_0 = \ frac {3} {2} u_2, \: \: u_1 = \ frac {1} {2} u_2,$ и пусть $u_2 = 1$, поэтому u0= frac32,u1= frac12$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 \ left (x_1, x_2 \ right) \ 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) )$

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

u0=0,u1=u2=a>0$u_0 = 0, \: \: u_1 = u_2 = a> 0$

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