Дифференцируемая квазивыпуклая функция

Пусть S — непустое выпуклое множество в $\ mathbb {R} ^ n$ и $f: S \ rightarrow \ mathbb {R}$ — дифференцируемо на S, тогда f квазивыпукло тогда и только тогда, когда для любого $x_1, x_2 \ in S$ и $f \ left (x_1 \ right) \ leq f \ left (x_2 \ right)$, у нас есть $\ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_2-x_1 \ right) \ leq 0$

доказательство

Пусть f — квазивыпуклая функция.

Пусть $x_1, x_2 \ in S$ такие, что $f \ left (x_1 \ right) \ leq f \ left (x_2 \ right)$

По дифференцируемости f в $x_2, \ lambda \ in \ left (0, 1 \ right)$

$f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) = f \ left (x_2 + \ lambda \ left (x_1-x_2 \ right) \ right) = f \ left (x_2 \ right) ) + \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right)$

$ + \ lambda \ left \ | x_1-x_2 \ right \ | \ alpha \ left (x_2, \ lambda \ left (x_1-x_2 \ right) \ right) $

$\ Rightarrow f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) -f \ left (x_2 \ right) -f \ left (x_2 \ right) = \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right)$

$ + \ lambda \ left \ | x_1-x_2 \ right \ | \ alpha \ left (x2, \ lambda \ left (x_1-x_2 \ right) \ right) $

Но поскольку f квазивыпуклая, $f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq f \ left (x_2 \ right)$

$ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) + \ lambda \ left \ | x_1-x_2 \ right \ | \ alpha \ left (x_2, \ lambda \ left (x_1, x_2 \ right) \ right) \ leq 0 $

Но $\ alpha \ left (x_2, \ lambda \ left (x_1, x_2 \ right) \ right) \ rightarrow 0$ при $\ lambda \ rightarrow 0$

Следовательно, $\ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq 0$

обратный

пусть для $x_1, x_2 \ in S$ и $f \ left (x_1 \ right) \ leq f \ left (x_2 \ right)$, $\ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1, x_2 \ right) \ leq 0$

Чтобы показать, что f квазивыпуклый, т. Е. $F \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq f \ left (x_2 \ right)$

Доказательство от противного

Предположим, существует $x_3 = \ lambda x_1 + \ left (1- \ lambda \ right) x_2$, такой что $f \ left (x_2 \ right) <f \ left (x_3 \ right)$ для некоторого $\ lambda \ in \ left (0, 1 \ right)$

Для $x_2$ и $x_3: \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_2-x_3 \ right) \ leq 0$

$\ Rightarrow - \ lambda \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_2-x_3 \ right) \ leq 0$

$\ Rightarrow \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1-x_2 \ right) \ geq 0$

Для $x_1$ и $x_3: \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1-x_3 \ right) \ leq 0$

$\ Rightarrow \ left (1- \ lambda \ right) \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1-x_2 \ right) \ leq 0$

$\ Rightarrow \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1-x_2 \ right) \ leq 0$

таким образом, из приведенных выше уравнений $\ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1-x_2 \ right) = 0$

Определите $U = \ left \ {x: f \ left (x \ right) \ leq f \ left (x_2 \ right), x = \ mu x_2 + \ left (1- \ mu \ right) x_3, \ mu \ in \ left (0,1 \ right) \ right \}$

Таким образом, мы можем найти $x_0 \ in U$ такой, что $x_0 = \ mu_0 x_2 = \ mu x_2 + \ left (1- \ mu \ right) x_3$ для некоторого $\ mu _0 \ in \ left (0,1 \ right) )$, ближайший к $x_3$ и $\ hat {x} \ in \ left (x_0, x_1 \ right)$, так что по теореме о среднем значении

$$\ frac {f \ left (x_3 \ right) -f \ left (x_0 \ right)} {x_3-x_0} = \ bigtriangledown f \ left (\ hat {x} \ right)$$

$$\ Rightarrow f \ left (x_3 \ right) = f \ left (x_0 \ right) + \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (x_3-x_0 \ right)$$

$$ \ Rightarrow f \ left (x_3 \ right) = f \ left (x_0 \ right) + \ mu_0 \ lambda f \ left (\ hat {x} \ right) ^ T \ left (x_1-x_2 \ right) $ $

Поскольку $x_0$ представляет собой комбинацию $x_1$ и $x_2$ и $f \ left (x_2 \ right) <f \ left (\ hat {x} \ right)$

Повторяя процедуру запуска, $\ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (x_1-x_2 \ right) = 0$

Таким образом, объединяя приведенные выше уравнения, получаем:

$$f \ left (x_3 \ right) = f \ left (x_0 \ right) \ leq f \ left (x_2 \ right)$$

$$\ Rightarrow f \ left (x_3 \ right) \ leq f \ left (x_2 \ right)$$

Следовательно, это противоречие.

Примеры

Шаг 1 — $f \ left (x \ right) = X ^ 3$

$Пусть f \ left (x_1 \ right) \ leq f \ left (x_2 \ right)$

$\ Rightarrow x_ {1} ^ {3} \ leq x_ {2} ^ {3} \ Rightarrow x_1 \ leq x_2$

$\ bigtriangledown f \ left (x_2 \ right) \ left (x_1-x_2 \ right) = 3x_ {2} ^ {2} \ left (x_1-x_2 \ right) \ leq 0$

Таким образом, $f \ left (x \ right)$ является квазивыпуклым.

Шаг 2 — $f \ left (x \ right) = x_ {1} ^ {3} + x_ {2} ^ {3}$

Пусть $\ hat {x_1} = \ left (2, -2 \ right)$ и $\ hat {x_2} = \ left (1, 0 \ right)$

таким образом, $f \ left (\ hat {x_1} \ right) = 0, f \ left (\ hat {x_2} \ right) = 1 \ Rightarrow f \ left (\ hat {x_1} \ right) \ setminus <f \ left (\ hat {x_2} \ right)$

Таким образом, $\ bigtriangledown f \ left (\ hat {x_2} \ right) ^ T \ left (\ hat {x_1} - \ hat {x_2} \ right) = \ left (3, 0 \ right) ^ T \ left (1, -2 \ справа) = 3> 0$

Следовательно, $f \ left (x \ right)$ не является квазивыпуклым.