Две задачи

[SpBTimes]

1. Функция $f: \mathbb{R}^n \to \mathbb{R}$ выпукла вниз, ее градиент $\nabla f$ существует в каждой точке и удовлетворяет условию Липшица:

$$ \exists M > 0: \quad \forall x_1, x_2 \in \mathbb{R}^n \quad \|\nabla f(x_1) - \nabla f(x_2) \| \leqslant M\|x_1 - x_2\|. $$

Доказать, что

$$ \forall x_1, x_2 \in \mathbb{R}^n \quad \|\nabla f(x_1) - \nabla f(x_2) \|^2 \leqslant M(\nabla f(x_1) - \nabla f(x_2), x_1 - x_2) $$

2. Существует ли функция $f: \mathbb{R} \to \mathbb{R}$ такая, что $f(0) = 0$ и для всех $x, y$ выполнено неравенство:

$$ f(x + y) \geqslant f(x) + yf(f(x))? $$

[1r0pb]

Прошу сильно не бить.
2. Только $f(t)\equiv 0.$
$x=0:\ f(y)\geq f(0);$
$y=-x:\ f(x)\leq xf(f(x)).$

[ex-math]

Пока ноль получается лишь при неположительных иксах.

[Red_Herring]

ex-math в сообщении #889311 писал(а):

Пока ноль получается лишь при неположительных иксах.

Положите $x>0, y=-x$ и воспользуйтесь неотрицательностью $f$.

[Oleg Zubelevich]

для гладких функций верно такое равенство

$$\|\nabla f(x_2)-\nabla f(x_1)\|^2=(x_2-x_1)^T\cdot d^2f(s)\cdot (\nabla f(x_2)-\nabla f(x_1)),\quad (\exists s\in[x_1,x_2])$$

[ex-math]

Red_Herring
И что? Я что-то упускаю? То, что Вы предлагаете, уже сделано 1r0pb, но из этого при положительных иксах ничего определенного не следует.

-- 22.07.2014, 15:38 --

Все бы хорошо вышло, будь в условии задачи в правой части минус перед $y$, а не плюс.

[Red_Herring]

ex-math в сообщении #889443 писал(а):

о из этого при положительных иксах ничего определенного не следует.

Да, Вы правы. Поспешишь—людей насмешишь, и на старуху бывает проруха. Значит надо решать!

(Опять ерунда)

ОК, что у нас есть для $x\ge 0$? Очевидно $f$ дифференцируема и $f'(x)=f(f(x))$ (и потому она бесконечно гладкая). Поэтому $f'\ge 0$ и $f(x)$ не убывает и если она не равна $0$ тождественно, то существует $a$ т.ч. $f(a)=0$ и $f(x)>0$ при любых $х>a$.

Но тогда для некотоых $b>a$ и $M$ при $x<b$ $f(x)$ достаточно близка к $0$ и $f(f(x))\le Mf(x)$. Значит при $x<b$ $f'(x)\le Mf(x)$ и потому $f(x)\le g(x)$ при $a<x<b$, где $g'=Mg$ и $g(0)=f(0)=0$. Тогда $g=0$ и $f(x)=0$ при $x<b$. Противоречие.

[sup]

Можно доказать, что $f(x)$ монотонна и $f(f(x)) \equiv 0$. А отсюда уже получаем $f(x) \equiv 0$.

[1r0pb]

SpBTimes в сообщении #889268 писал(а):

и для всех $x, y$ выполнено неравенство:

$$ f(x + y) \geqslant f(x) + yf(f(x))? $$

А разве это не является ключевым фактором? Ведь неравенство должно выполняться для $x\in R,$ но оно не выполняется для $x<0,$ если $f(t)\neq 0.$

[Oleg Zubelevich]

SpBTimes в сообщении #889268 писал(а):

1. Функция $f: \mathbb{R}^n \to \mathbb{R}$ выпукла вниз, ее градиент $\nabla f$ существует в каждой точке и удовлетворяет условию Липшица:

$$ \exists M > 0: \quad \forall x_1, x_2 \in \mathbb{R}^n \quad \|\nabla f(x_1) - \nabla f(x_2) \| \leqslant M\|x_1 - x_2\|. $$

Доказать, что

$$ \forall x_1, x_2 \in \mathbb{R}^n \quad \|\nabla f(x_1) - \nabla f(x_2) \|^2 \leqslant M(\nabla f(x_1) - \nabla f(x_2), x_1 - x_2) $$

Пусть $f$ -- гладкая функция. Дополнительно будем считать, что младшее собственное число матрицы $d^2f(x)$ отделено от нуля некоторой положительной константой $m$, которая не зависит от $x$.
Тогда легко проверить, что оператор $\nabla f:\mathbb{R}^m\to\mathbb{R}^m$ является строго монотонным и

$$\lim_{\|x\|\to\infty}\frac{(\nabla f(x),x)}{\|x\|}\to\infty$$

Действительно, применяя теоремк Лагранжа к функции
$u(t)=(\nabla f(x_2+t(x_1-x_2)),x_1-x_2)$ получаем

$$(\nabla f(x_1)-\nabla f(x_2),x_1-x_2)=(x_1-x_2)^Td^2 f(\xi)(x_1-x_2)\ge m\|x_1-x_2\|^2,\quad \xi\in[x_1,x_2]$$

Таким образм $\nabla f$ это диффеоморфизм. (Использована теорема Минти)


Пусть $g$ это обратный диффеоморфизм.
Применяя теорему Лагранжа к функции $h(t)=(g(x_1+t(x_2-x_1))-g(x_1),\eta)$ находим

$$(g(x_2)-g(x_1),\eta)=(x_2-x_1)^T(d^2f(s))^{-1}\eta,\quad s\in [x_1,x_2],\quad s=s(\eta)$$

Пусть теперь

$$x_i=\nabla f(y_i),\quad \eta=\nabla f(y_2)-\nabla f(y_1)$$

тогда

$$(y_2-y_1,\nabla f(y_2)-\nabla f(y_1))=(\nabla f(y_2)-\nabla f(y_1))^T(d^2f(s))^{-1}(\nabla f(y_2)-\nabla f(y_1))$$

последнее выражение больше или равно чем

$$\frac{1}{M}\|\nabla f(y_2)-\nabla f(y_1)\|^2$$

где $M$ -- супремум по всем собственным числам и всем точкам $x$ матрицы $d^2f(x)$.
Для данного класса функций теорема доказана.

Теперь надо как-то убедить окружающих в том, что исходная функция приближается в каком-то смысле ,на самом деле достаточно, чтобы производная исходной $f$ приближалась поточечно производными указанных гладких функций с равномерно (по $x$ ) невырожденными гессианами

[ex-math]

sup
А как получить $f(f(x))\equiv0$?
Red_Herring
Мне даже дифференцируемость не очевидна.

[Red_Herring]

ex-math в сообщении #889526 писал(а):

sup
А как получить $f(f(x))\equiv0$?
Red_Herring
Мне даже дифференцируемость не очевидна.

sup прав. После того как мы доказали, что $f(x)$ монотонна и неотрицательна, предположим, что $f(f(a)=b>0$ для какого-тo $a$. Тогда подставляя $x=y:=x/2$ мы видим, что для $x>2a$ $f(x)\ge kx$ с $k>0$. Аналогично $f(x)>k_1x^2$ для $x>4a$. Тогда для достаточно больших $x$ $f(x/2)\ge x$ и $f(x)\ge \frac{1}{2}xf(f(x/2))\ge \frac{1}{2}xf(x))$ и тогда при больших $x$ $f(x)=0$.

[sup]

Я рассуждал достаточно прямолинейно. Пусть $f(x) > 0$ для $x>a$. Положим $y=1$. Тогда для $x>a$
$f(x+1) > f(f(x))$
И в силу монотонности
$f(x) < x + 1$.
Теперь устремим $y \to \infty$. Тогда для $x>a$
$x+y+1 > f(x+y) > yf(f(x))$
А значит $f(f(x)) \leqslant 1$.
Отсюда следует, что $f(x)$ ограничена, а значит
$yf(f(x)) < C$
Поскольку $y$ произвольно - $f(f(x)) \equiv 0$.

[ex-math]

Red_Herring
Да, теперь понятно.

sup в сообщении #889582 писал(а):

Я рассуждал достаточно прямолинейно.

И, как всегда, очень изящно