2023-10-07T11:22:42Z

Alexandra22: Новая страница: « __TOC__ == Определение == '''Метрическим пространством M''' называется множество элементов $$x, y...»

Субдифференциалы выпуклых функций

2022-12-12T21:21:26Z

Alexandra22:

__TOC__
[[Файл:Subdiff.png|150px|thumb|right|$$f(x) = |x|$$]]
Пусть $$X = \mathbb{R}^n$$ и $$f -$$ собственная [https://sawiki.cs.msu.ru/index.php?title=%D0%92%D1%8B%D0%BF%D1%83%D0%BA%D0%BB%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%B8_%D0%B5%D0%B5_%D1%81%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0&action=edit&redlink=1 выпуклая функция]

На графике приведен пример выпуклой функции, которая недифференцируема в точке $$x = 0$$ (на графике показано множество касательных в этой точке).

== Используемые определения ==

Функция $$f$$ называется ''собственной'', если dom $$f \neq \varnothing$$ и $$f(x) > -\infty~~\forall x$$, где $$\text{dom f} = \{x \in X: f(x) < +\infty\} -$$ эффективное множество функции $$f$$.

''Субградиентом функции $$f$$ в точке $$x$$'' называется вектор $$x^* \in X$$ такой, что $$f(y) \geqslant f(x) + \langle x^*,y - x \rangle~~\forall y \in X$$. Это неравенство называется субградиентным неравенством.

== Определение субдифференциала==

''Субдифференциалом функции $$f$$ в точке $$x$$'' называется множество всех субградиентов функции $$f$$ в этой точке. Субдифференциал обозначается $$\partial f(x)$$.

Например, на графике выше $$\partial f(0) = [-1,1]$$.

Заметим, что функция $$f$$ достигает в точке $$x$$ минимума тогда и только тогда, когда $$0 \in \partial f(x)$$.

== Вспомогательные утверждения ==
'''Теорема 1.'''
Пусть функция $$f$$ [https://sawiki.cs.msu.ru/index.php?title=%D0%92%D1%8B%D0%BF%D1%83%D0%BA%D0%BB%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%B8_%D0%B5%D0%B5_%D1%81%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0&action=edit&redlink=1 выпукла] и конечна в точке $$x$$. Тогда
\[
f'(x,y) = \inf \limits_{\lambda > 0} \dfrac{f(x + \lambda y) - f(x)}{\lambda}
\]
(где $$f'(x,y) - $$ производная $$f(x)$$ по направлению $$y$$), функция $$f'(x, \cdot)$$ выпукла, [https://ru.wikipedia.org/wiki/%D0%9E%D0%B4%D0%BD%D0%BE%D1%80%D0%BE%D0%B4%D0%BD%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F положительно однородна] и
\[
f'(x,0) = 0, -f'(x, -y) \leqslant f'(x,y)~~\forall y.
\]

'''Доказательство:'''

Для удобства будем считать, что $$x = 0, f(x) = 0$$. Для $$\lambda > 0$$ положим $$h(y) = \dfrac{f(\lambda y)}{\lambda}$$. Покажем, что функция $$h(\cdot)$$ не убывает. Действительно, пусть $$0 < \mu < \lambda$$. Тогда в силу выпуклости $$f$$ имеем $$f(\mu y) = f\left(0\left(1 - \dfrac{\mu}{\lambda}\right) + \dfrac{\mu}{\lambda} \lambda y\right) \leqslant f(0)\left( 1 - \dfrac{\mu}{\lambda} \right) + f(\lambda y)\dfrac{\mu}{\lambda} = f(\lambda y)\dfrac{\mu}{\lambda} \Rightarrow \dfrac{f(\mu y)}{\mu} \leqslant \dfrac{f(\lambda y)}{\lambda}$$ и, значит, $$h$$ не убывает. Поэтому $$\lim \limits_{\lambda \to 0+} h(\lambda) = \inf \limits_{\lambda > 0} h(\lambda) = f'(0, y).$$

Пусть дано $$\mu \geqslant 0$$. Тогда, очевидно, $$\dfrac{f(\lambda(\mu y))}{\lambda} = \mu \dfrac{f(\chi y)}{\chi} = \mu h(\chi)$$, где $$\chi = \lambda \mu$$. Поэтому $$f'(0, (\mu y)) = \mu \lim \limits_{\chi \to 0+} h(\chi) = \mu f'(0, y)$$ и, значит, функция $$f'(0, \cdot)$$ положительно однородна, $$f'(0,0) = 0$$ по определению.

Докажем выпуклость функции $$f'(x, \cdot)$$. Пусть $$\alpha, \beta \geqslant 0, \alpha + \beta = 1, y_1, y_2 \in X$$. В силу выпуклости $$f$$ имеем
\[
f'(x, \alpha y_1 + \beta y_2) = \lim \limits_{\lambda \to 0+} \dfrac{f(x + \lambda \alpha y_1 + \lambda \beta y_2) - f(x)}{\lambda} \leqslant
\]
\[
\leqslant \lim \limits_{\lambda \to 0+} \dfrac{\alpha f(x + \lambda y_1) + \beta f(x + \lambda y_2) - \alpha f(x) - \beta f(x)}{\lambda} =
\]
\[
= \lim \limits_{\lambda \to 0+} \alpha \dfrac{f(x + \lambda y_1) - f(x)}{\lambda} + \lim \limits_{\lambda \to 0+} \beta \dfrac{f(x + \lambda y_2) - f(x)}{\lambda} = \alpha f'(x, y_1) + \beta f'(x, y_2).
\]

Значит, функция $$f'(x, \cdot)$$ выпукла. Из ее выпуклости и положительной однородности получаем $$f'(x,y) + f'(x, -y) \geqslant 2f'(x, \frac{y + (-y)}{2}) = 2f'(x,0) = 0$$, откуда имеем $$-f'(x,-y) \leqslant f'(x,y)$$. $$\blacksquare$$

'''Лемма 1.'''
Пусть $$f -$$ собственная выпуклая функция и $$x \in \text{int}(\text{dom }f)$$. Тогда существует $$c > 0$$ такое, что
\[
|f'(x,y)| \leqslant c|y|~~\forall y,
\]
где $$\text{int A} -$$ [https://ru.wikipedia.org/wiki/%D0%92%D0%BD%D1%83%D1%82%D1%80%D0%B5%D0%BD%D0%BD%D0%BE%D1%81%D1%82%D1%8C внутренность множества]$$A -$$ множество всех внутренних точек множества $$A$$.

'''Доказательство:'''

По [https://sawiki.cs.msu.ru/index.php?title=%D0%92%D1%8B%D0%BF%D1%83%D0%BA%D0%BB%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%B8_%D0%B5%D0%B5_%D1%81%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0&action=edit&redlink=1 теореме о липшицевости выпуклой функции] существует такая окрестность $$O$$ точки $$x$$, что функция $$f$$ на $$O$$ удовлетворяет условию Липшица с некоторой константой $$c > 0$$. Поэтому для каждого фиксированного $$y$$ неравенство $$\left| \dfrac{f(x + \lambda y) - f(x)}{\lambda} \right| \leqslant c|y|$$ выполняется при всех достаточно малых $$\lambda > 0$$. Искомое утверждение непосредственно вытекает из этого неравенства и соотношения
\[
f'(x,y) = \lim \limits_{\lambda \to 0+} \dfrac{f(x + \lambda y) - f(x)}{\lambda}.\blacksquare
\]

'''Лемма 2.'''
Пусть функция $$f$$ выпукла и конечна в точке $$x$$. Тогда
\[
x^* \in \partial f(x) \Leftrightarrow f'(x,y) \geqslant \langle x^*, y \rangle~~\forall y \in X.
\]

'''Доказательство:'''

Пусть $$x^* \in \partial f(x)$$. Тогда в силу субградиентного неравенства при всяком $$\lambda > 0$$ имеем $$f(x + \lambda y) - f(x) \geqslant \langle x^*, y \rangle~~\forall y$$ и, значит,
\[
f'(x,y) = \lim \limits_{\lambda \to 0+} \dfrac{f(x + \lambda y) - f(x)}{\lambda} \geqslant \langle x^*, y \rangle.
\]
Теперь пусть
\[
\langle x^*, y \rangle \leqslant f'(x,y) = \inf \limits_{\lambda > 0} \dfrac{f(x + \lambda y) - f(x)}{\lambda}~~\forall y \Rightarrow
\]
\[
\Rightarrow f(x + \lambda y) - f(x) \geqslant \langle x^*, y \rangle~~\forall y \in X,~~\forall \lambda > 0.
\]
Отсюда при $$\lambda = 1, z = x + y$$ имеем $$f(z) - f(x) \geqslant \langle x^*, z - x \rangle~~\forall z \in X$$, откуда $$x^* \in \partial f(x)$$. $$\blacksquare$$

'''Лемма 3.'''
Пусть функция $$f$$ выпуклая, собственная и $$x \in \text{int}(\text{dom }f)$$. Тогда функция $$\text{cl }f'(x,\cdot)$$, являющаяся замыканием производной $$f'(x,y)$$ как выпуклой функции от $$y$$, совпадает c [https://sawiki.cs.msu.ru/index.php/%D0%9E%D0%BF%D0%BE%D1%80%D0%BD%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0 опорной функцией] множества $$\partial f(x)$$, где $$\text{cl }A -$$ замыкание множества $$A$$.

'''Доказательство:'''

По теореме 1 и лемме 1 функция $$f'(x,\cdot)$$ является выпуклой, положительно однородной и собственной. Поэтому имеет место $$\text{cl }f'(x,\cdot) = \rho(\cdot, A)$$, где $$A = \{x^*: \langle x^*, y \rangle \leqslant f'(x,y)~~\forall y\}$$. По лемме 2: $$A = \partial f(x)$$. $$\blacksquare$$

'''Лемма 4.'''
Для любых функций $$f_1,...,f_k$$ имеет место
\[
\partial (f_1+...+f_k)(x) \supseteq \partial f_1(x) +...+ \partial f_k(x)~~\forall x \in X.
\]

'''Доказательство:'''

Пусть $$x^* \in \partial f_1(x) +...+ \partial f_k(x)$$. Тогда $$x^* = x_1^* +...+ x_k^*$$, где $$x_i^* \in \partial f_i(x)$$. Поэтому
\[
f_1(y) \geqslant f_1(x) + \langle x_1^*,y-x \rangle,...,f_k(y) \geqslant f_k(x) + \langle x_k^*,y-x \rangle~~\forall y \in X.
\]
Складывая при каждом фиксированном $$y$$ все эти неравенства, получаем, что $$x^* \in \partial (f_1+...+f_k)(x)$$.$$\blacksquare$$

==Структура субдифференциала выпуклой функции==

'''Теорема 2.'''
Пусть $$f -$$ выпуклая собственная функция и $$x \in \text{int}(\text{dom }f)$$. Тогда субдифференциал $$\partial f(x)$$ в точке $$x$$ является непустым компактом.

'''Доказательство:'''

Вначале докажем, что $$\partial f(x) \neq \varnothing.$$ Рассмотрим множество $$\text{cl epi }f (\text{epi }f = \{(x, \alpha) \in X \times \mathbb{R}: f(x) \leqslant \alpha\} -$$ надграфик функции $$f$$). Оно выпукло, [https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%BC%D0%BA%D0%BD%D1%83%D1%82%D0%BE%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE замкнуто], и $$(x, f(x)) \notin \text{int}(\text{cl epi }f).$$ Здесь несложно показать, что последнее утверждение вытекает из непрерывности на $$\text{int}(\text{dom }f)$$ определенной на $$\mathbb{R}^n$$ выпуклой собственной функции. Поэтому по [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE%D1%82%D0%B4%D0%B5%D0%BB%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8 теореме отделимости] существуют $$x^* \in \mathbb{R}^n, r \in \mathbb{R}$$ такие, что
\[
r\alpha + \langle x^*, z \rangle \geqslant rf(x) + \langle x^*, x \rangle \; \forall \alpha, z: \alpha \geqslant f(z).
\]
Условие $$r \neq 0$$ вытекает из того, что $$x \in \text{int}(\text{dom }f)$$. Условие $$r > 0$$ следует из того, что приведенное неравенство выполняется при сколь угодно больших $$\alpha \geqslant f(z)$$. Поэтому, не теряя общности, будем считать, что $$r = 1$$. Из приведенного неравенства при $$\alpha = f(z)$$ имеем
\[
f(z) \geqslant f(x) + \langle -x^*, z-x \rangle \; \forall z \Rightarrow -x^* \in \partial f(x)
\]
и, значит, $$\partial f(x) \neq \varnothing$$.

Докажем ограниченность множества $$\partial f(x)$$. Действительно, предположим обратное, т. е. что в $$\partial f(x)$$ существует такая последовательность $$\{x^*_i\}$$, что $$|x^*_i| \rightarrow \infty$$. Выберем такое $$\delta > 0$$, что $$\text{cl}(O(x, \delta)) \subset \text{int}(\text{dom }f)$$. Тогда функция $$f$$ непрерывна и, значит, ограничена на компакте $$\text{cl}(O(x, \delta))$$. Положим $$x_i = x + \delta x^*_i/|x^*_i|$$. Из субградиентного неравенства при $$y = x_i$$ и $$x^* = x^*_i$$ получаем что $$f(x_i) \geqslant f(x) + \delta|x^*_i|$$. Но в полученном неравенстве правая часть стремится к бесконечности, а левая ограничена, поскольку $$x_i \in \text{cl}(O(x, \delta)) \; \forall i$$. Это противоречие доказывает ограниченность множества $$\partial f(x)$$.

Докажем замкнутость множества $$\partial f(x)$$. Пусть $$x^*_i \in \partial f(x) \; \forall i$$ и $$x^*_i \rightarrow x^*$$. При каждом фиксированном $$y$$, подставляя в субградиентное неравенство $$x^* = x^*_i$$ и переходя к пределу при $$i \rightarrow \infty$$,
получаем $$x^* \in \partial f(x)$$.

Осталось доказать выпуклость множества $$\partial f(x)$$. Пусть $$x_1^*, x_2^* \in \partial f(x), \alpha \geqslant 0, \beta \geqslant 0, \alpha + \beta = 1$$. Тогда:
\[
f(z) - f(x) \geqslant \langle x_1^*, z - x \rangle, \; f(z) - f(x) \geqslant \langle x_2^*, z - x \rangle \; \forall z \in X.
\]
При фиксированном $$z$$ умножим первое из этих неравенств на $$\alpha$$, а второе на $$\beta$$, и затем сложим их. В результате этого получаем, что $$\alpha x_1^* + \beta x_2^* \in \partial f(x). \blacksquare$$

'''Лемма 5''' (альтернатива). Пусть выпуклая функция $$f$$ конечна в точке $$x_0$$, принадлежащей границе эффективного множества $$\text{dom }f$$. Тогда в этой точке субдифференциал $$\partial f(x_0)$$ либо пуст, либо содержит бесконечно много точек.

'''Доказательство:'''

В силу выпуклости субдифференциала $$\partial f(x_0)$$ достаточно доказать, что если это множество непусто, то оно содержит хотя бы два различных элемента. Итак, пусть $$x^* \in \partial f(x_0)$$. Рассмотрим выпуклую функцию $$h(y) = f(x_0 + y) - f(x_0) - \langle x^*,y \rangle$$. Для нее $$h(0) = 0$$, и нуль принадлежит границе эффективного множества $$\text{dom }h$$. Кроме того, $$0 \in \partial h(0)$$, откуда в силу субградиентного неравенства получаем, что $$h(y) \geqslant 0 ~~\forall y \in X$$.

В силу сказанного выше $$0 \notin \text{int(dom }h)$$. Поэтому выпуклое множество $$\text{dom }h$$ можно отделить от нуля и, значит, в силу конечномерной теоремы отделимости существует такой $$a \in X, a \neq 0$$ что $$\langle a,y \rangle \leqslant 0 ~~\forall y \in \text{dom }h.$$ Следовательно, $$h(y) \geqslant \langle a,y \rangle ~~\forall y \in X,$$ поскольку $$h(y) \geqslant 0 ~~\forall y \in X.$$ Значит, $$0,a \in \partial h(0), a \neq 0 \Rightarrow x^*, (a + x^*) \in \partial f(x_0)$$. $$\blacksquare$$

'''Лемма 6''' (бесконечномерная альтернатива). Пусть $$X -$$ произвольное [https://ru.wikipedia.org/wiki/%D0%9D%D0%BE%D1%80%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%82%D0%B2%D0%BE нормированное пространство], а заданная на нем выпуклая функция $$f$$ конечна в точке $$x_0$$, принадлежащей границе эффективного множества $$\text{dom }f$$, и, кроме того, внутренность эффективного множества $$\text{int(dom }f)$$ непуста. Тогда в этой точке субдифференциал $$\partial f(x_0)$$ либо пуст, либо содержит бесконечно много точек.

'''Доказательство:'''

Доказательство этой леммы аналогично доказательству предыдущей, но вместо теоремы о конечномерной отделимости следует использовать теорему отделимости. $$\blacksquare$$

==Пример к теореме 2==
Рассмотрим на $$\mathbb{R}$$ функцию
\[
f(x) =
\begin{cases}
-(1 - x^2)^{\frac{1}{2}}, & \quad |x| \leqslant 1,\\
+\infty, & \quad |x| > 1.
\end{cases}
\]
Эта функция субдифференцируема (и даже дифференцируема) во всех точках $$x \in \text{int}(\text{dom }f) = (-1,1)$$. Однако в точках $$x = 1, -1$$, составляющих границу $$\text{dom }f$$, ее субдифференциал пуст.

==Теорема Моро-Рокафеллара==

'''Теорема 3 '''(Моро-Рокафеллара).
Пусть функции $$f_1,...,f_k$$ являются собственными и выпуклыми, причем существует точка $$x_0 \in \cap_i \text{dom } f_i$$, в которой все функции $$f_i$$, за исключением, возможно, одной, непрерывны.

Тогда имеет место
\[
\partial (f_1+...+f_k)(x) = \partial f_1(x) +...+ \partial f_k(x)~~\forall x \in X.
\]

'''Доказательство:'''

Приведем доказательство только для случая $$k = 2$$ (общий случай доказывается по индукции). Исходя из предыдущего утверждения, достаточно показать, что
\[
\partial (f_1+f_2)(x) \subset \partial f_1(x) + \partial f_2(x)~~\forall x \in X.
\]
По условию в точке $$x_0 \in \text{dom } f_1 \cap \text{dom } f_2$$ хотя бы одна из рассматриваемых функций, пусть для определенности это $$f_1$$, непрерывна. Тогда $$x_0 \in \text{int(dom } f_1)$$ и, значит, пересечение множеств $$\text{int(dom } f_1)$$ и $$\text{dom } f_2$$ непусто.

Зафиксируем $$x \in X$$. Возьмем произвольное $$x^* \in \partial(f_1+f_2)(x)$$. Заменяя, если необходимо, функции $$f_1, f_2$$ собственными выпуклыми функциями
\[
g_1(z) = f_1(x+z) - f_1(x) - \langle x^*,z \rangle, g_2(z) = f_2(x+z) - f_2(x),
\]
будем считать, не ограничивая общности, что
\[
x = 0, f_1(0) = 0, f_2(0) = 0, x^* = 0.
\]
Итак, $$0 \in \partial (f_1 + f_2)(0)$$. Докажем, что $$0 \in \partial f_1(0) + \partial f_2(0)$$.
Действительно, в силу сделанного предположения
\begin{equation}
\label{1}
f_1(z) + f_2(z) \geqslant f_1(0) + f_2(0) = 0~~\forall z \in X.
\end{equation}
Рассмотрим множества
\[
C_1 = \{(z,\mu): \mu \geqslant f_1(z)\}, C_2 = \{(z,\mu): \mu < -f_2(z)\}.
\]
Из выпуклости функций $$f_1,f_2$$ непосредственно вытекает, что оба эти множества выпуклы. Кроме того, они не пересекаются, ибо иначе в некоторой точке $$z$$ выполнялось бы неравенство $$-f_2(z) > f_1(z)$$, которое, в свою очередь, противоречило бы $$\ref{1}$$. Таким образом, выпуклые множества $$C_1$$ и $$C_2$$ не пересекаются. Поэтому по теореме отделимости для конечномерных пространств эти два множества можно отделить, т.е. существуют такие одновременно неравные нулю $$z^* \in \mathbb{R}^n$$ и $$\beta \in \mathbb{R}$$, что
\begin{equation}
\label{2}
\sup \limits_{(z,\mu) \in C_1} (\beta \mu + \langle z^*,z \rangle) \leqslant \inf \limits_{(z,\mu) \in C_2} (\beta \mu + \langle z^*,z \rangle).
\end{equation}
Очевидно, $$\beta \leqslant 0$$, ибо при $$\beta > 0$$ верхняя грань в $$\ref{2}$$ равнялась бы $$+\infty$$, а нижняя грань равнялась бы $$-\infty$$. Случай $$\beta = 0$$ также невозможен, так как если $$\beta = 0$$, то $$z^* \neq 0$$ и $$\ref{2}$$ принимает вид
\[
\sup \limits_{z \in \text{dom }f_1} \langle z^*,z \rangle \leqslant \inf \limits_{z \in \text{dom }f_2} \langle z^*,z \rangle.
\]
А это противоречит тому, что пересечение множеств $$\text{int(dom }f_1)$$ и $$\text{dom }f_2$$ непусто. Таким образом, доказано, что $$\beta < 0$$, и поэтому, не ткряя общности, будем считать $$\beta = -1$$.

Из $$\ref{2}$$ следует неравенство
\[
\sup \limits_z \{\langle z^*,z \rangle - f_1(z)\} \leqslant \inf \limits_z \{\langle z^*,z \rangle - f_2(z)\}.
\]
Но при $$z = 0$$ выражения в фигурных скобках как в левой, так и в правой частях этого неравенства обращаются в нуль.

Поэтому получаем
\[
f_1(z) \geqslant \langle z^*,z \rangle, f_2(z) \geqslant \langle -z^*,z \rangle~~\forall z \in X.
\]
Итак,
\[
f_1(z) \geqslant f_1(0) + \langle z^*,z - 0 \rangle~~\forall z \in X,
\]
\[
f_2(z) \geqslant f_2(0) + \langle -z^*,z - 0 \rangle~~\forall z \in X.
\]
Значит, $$z^* \in \partial f_1(0), -z^* \in \partial f_2(0)$$; следовательно, $$0 \in \partial f_1(0) + \partial f_2(0)$$.$$\blacksquare$$

==Критерий дифференцируемости==

'''Теорема 4.'''
Пусть выпуклая функция $$f$$ конечна в точке $$x_0$$. Если $$f$$ дифференцируема в точке $$x_0$$, то субдифференциал $$\partial f(x_0)$$ содержит единственный элемент $$f'(x_0)$$ и, в частности,
\[
f(z) \geqslant f(x_0) + \langle f'(x_0), z - x_0 \rangle~~\forall z \in X.
\]
Наоборот, если субдифференциал $$\partial f(x_0)$$ содержит единственный элемент, то функция $$f$$ дифференцируема в точке $$x_0$$ и $$\partial f(x_0) = \{f'(x_0)\}$$.

'''Доказательство:'''

Пусть $$f$$ дифференцируема в точке $$x_0$$. Тогда $$f'(x_0,y) = \langle f'(x_0),y \rangle~~\forall y$$. Поэтому в силу леммы 2 для любого $$x^* \in \partial f(x_0)$$ выполняется
\[
\langle f'(x_0),y \rangle = f'(x_0,y) \geqslant \langle x^*,y \rangle~~\forall y \in X,
\]
откуда
\[
\langle (f'(x_0) - x^*),y \rangle \geqslant 0 \rangle~~\forall y \in X.
\]
Но если линейный функционал неотрицателен на всем пространстве, то он равен нулю и, следовательно, $$x^* = f'(x_0)~~\forall x^* \in \partial f(x_0)$$, т.е. субдифференциал $$\partial f(x_0)$$ состоит из единственной точки $$f'(x_0)$$.

Пусть теперь $$\partial f(x_0) = \{x^*\}$$. Рассмотрим выпуклую функцию $$h(y) = f(x_0 + y) - f(x_0) - \langle x^*,y \rangle$$. Для нее $$h(0) = 0, \partial h(0) = \{0\}$$, откуда в силу субградиентного неравенства получаем $$h(y) \geqslant 0~~\forall y \in X$$ и, значит, функция $$h$$ является собственной. Кроме того, в силу леммы 5 имеет место $$0 \in \text{int}(\text{dom }h)$$. Поэтому согласно лемме 3 функция $$\text{cl }h'(0,\cdot)$$ является опорной функцией для множества $$\partial h(0)$$. Таким образом, $$\text{cl }h'(0,y) = \rho(y, \partial h(0)) = 0~~\forall y \in X$$.

Итак, $$0 \in \text{int}(\text{dom }h)$$, а $$h -$$ собственная выпуклая функция. Поэтому в силу леммы 1 выпуклая функция $$h'(0,\cdot)$$ принимает лишь конечные значения и, следовательно, она непрерывна на $$\mathbb{R}^n$$. Поэтому в силу доказанного выше $$h'(0,y) \equiv 0$$. Следовательно,
\[
\lim \limits_{\lambda \to 0+} \dfrac{h(\lambda y)}{\lambda} = 0~~\forall y \in X.
\]
Кроме того, из доказательства теоремы 1 вытекает, что при каждом фиксированном $$y$$ функция $$g(\lambda) = \dfrac{h(\lambda y)}{\lambda}$$ не убывает при $$\lambda > 0$$.

При произвольном $$\lambda > 0$$ рассмотрим функцию $$g_{\lambda}(u) = \dfrac{h(\lambda y)}{\lambda}$$. Каждая из функций $$g_{\lambda}$$ выпукла, и для любого $$u$$ в силу доказанного имеем: $$g_{\lambda}(u) \to 0, \lambda \to 0+, g_{\lambda}(u) \geqslant 0$$. Пусть $$B = \{x: |x| \leqslant 1\} -$$ единичный шар, а $$\{b_1,...,b_m\} -$$ конечный набор точек, выпуклая оболочка которых содержит $$B$$.

Всякое $$u \in B$$ можно представить в виде выпуклой комбинации $$u = \alpha_1 b_1 +...+ \alpha_m b_m$$. Следовательно, в силу выпуклости каждой из функций $$g_{\lambda}$$, для любого $$u \in B$$ имеет место
\[
0 \leqslant g_{\lambda}(u) \leqslant \alpha_1 g_{\lambda}(b_1) +...+ \alpha_m g_{\lambda}(b_m) \leqslant \max\{g_{\lambda}(b_i), i = 1,...,m\}.
\]
Тогда, поскольку $$g_{\lambda}(b_i) \to 0. \lambda \to 0+$$ для каждого $$i$$, функция $$g_{\lambda}$$ сходятся к нулю равномерно на $$B$$. Поэтому для любого $$\varepsilon > 0$$ существует $$\delta > 0$$ такое, что
\[
\dfrac{h(\lambda u)}{\lambda} \leqslant \varepsilon~~\forall \lambda \in (0, \delta],~~\forall \in B.
\]
Но любой вектор $$y \neq 0, |y| \leqslant \delta$$ можно представить в виде $$y = \lambda u$$, где $$\lambda = |y| \leqslant \delta, u = \dfrac{y}{|y|} \in B$$. Поэтому неравенство $$\dfrac{h(y)}{|y|} \leqslant \varepsilon$$ выполняется при всех $$y$$, для которых $$|y| \leqslant \delta$$.

Таким образом, мы доказали, что $$\dfrac{h(y)}{|y|} \to 0, y \to 0$$. Иными словами, функция $$h$$ дифференцируема в нуле, причем ее производная равна нулю. Значит, $$f$$ дифференцируема в точке $$x_0$$. $$\blacksquare$$

== Список литературы ==
''Арутюнов А. В.'' Лекции по выпуклому и многозначному анализу. — М.: ФИЗМАТЛИТ, 2014

Субдифференциалы выпуклых функций

2022-12-11T13:29:56Z

Alexandra22:

__TOC__
[[Файл:Subdiff.png|150px|thumb|right|$$f(x) = |x|$$]]
Пусть $$X = \mathbb{R}^n$$ и $$f -$$ собственная [https://sawiki.cs.msu.ru/index.php?title=%D0%92%D1%8B%D0%BF%D1%83%D0%BA%D0%BB%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%B8_%D0%B5%D0%B5_%D1%81%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0&action=edit&redlink=1 выпуклая функция]

На графике приведен пример выпуклой функции, которая недифференцируема в точке $$x = 0$$ (на графике показано множество касательных в этой точке).

== Используемые определения ==

Функция $$f$$ называется ''собственной'', если dom $$f \neq \varnothing$$ и $$f(x) > -\infty~~\forall x$$, где $$\text{dom f} = \{x \in X: f(x) < +\infty\} -$$ эффективное множество функции $$f$$.

''Субградиентом функции $$f$$ в точке $$x$$'' называется вектор $$x^* \in X$$ такой, что $$f(y) \geqslant f(x) + \langle x^*,y - x \rangle~~\forall y \in X$$. Это неравенство называется субградиентным неравенством.

== Определение субдифференциала==

''Субдифференциалом функции $$f$$ в точке $$x$$'' называется множество всех субградиентов функции $$f$$ в этой точке. Субдифференциал обозначается $$\partial f(x)$$.

Например, на графике выше $$\partial f(0) = [-1,1]$$.

Заметим, что функция $$f$$ достигает в точке $$x$$ минимума тогда и только тогда, когда $$0 \in \partial f(x)$$.

== Вспомогательные утверждения ==
'''Теорема 1.'''
Пусть функция $$f$$ [https://sawiki.cs.msu.ru/index.php?title=%D0%92%D1%8B%D0%BF%D1%83%D0%BA%D0%BB%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%B8_%D0%B5%D0%B5_%D1%81%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0&action=edit&redlink=1 выпукла] и конечна в точке $$x$$. Тогда
\[
f'(x,y) = \inf \limits_{\lambda > 0} \dfrac{f(x + \lambda y) - f(x)}{\lambda},
\]
функция $$f'(x, \cdot)$$ выпукла, [https://ru.wikipedia.org/wiki/%D0%9E%D0%B4%D0%BD%D0%BE%D1%80%D0%BE%D0%B4%D0%BD%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F положительно однородна] и
\[
f'(x,0) = 0, -f'(x, -y) \leqslant f'(x,y)~~\forall y.
\]

'''Доказательство:'''

Для удобства будем считать, что $$x = 0, f(x) = 0$$. Для $$\lambda > 0$$ положим $$h(y) = \dfrac{f(\lambda y)}{\lambda}$$. Покажем, что функция $$h(\cdot)$$ не убывает. Действительно, пусть $$0 < \mu < \lambda$$. Тогда в силу выпуклости $$f$$ имеем $$f(\mu \lambda) = f\left(0\left(1 - \dfrac{\mu}{\lambda}\right) + \dfrac{\mu}{\lambda} \lambda y\right) \leqslant f(0)\left( 1 - \dfrac{\mu}{\lambda} \right) + f(\lambda y)\dfrac{\mu}{\lambda} = f(\lambda y)\dfrac{\mu}{\lambda} \Rightarrow \dfrac{f(\mu y)}{\mu} \leqslant \dfrac{f(\lambda y)}{\lambda}$$ и, значит, $$h$$ не убывает. Поэтому $$\lim \limits_{\lambda \to 0+} h(\lambda) = \inf \limits_{\lambda > 0} h(\lambda) = f'(0, y).$$

Пусть дано $$\mu \geqslant 0$$. Тогда, очевидно, $$\dfrac{f(\lambda(\mu y))}{\lambda} = \mu \dfrac{f(\chi y)}{\chi} = \mu h(\chi)$$, где $$\chi = \lambda \mu$$. Поэтому $$f'(0, (\mu y)) = \mu \lim \limits_{\chi \to 0+} h(\chi) = \mu f'(0, y)$$ и, значит, функция $$f'(0, \cdot)$$ положительно однородна, $$f'(0,0) = 0$$ по определению.

Докажем выпуклость функции $$f'(x, \cdot)$$. Пусть $$\alpha, \beta \geqslant 0, \alpha + \beta = 1, y_1, y_2 \in X$$. В силу выпуклости $$f$$ имеем
\[
f'(x, \alpha y_1 + \beta y_2) = \lim \limits_{\lambda \to 0+} \dfrac{f(x + \lambda \alpha y_1 + \lambda \beta y_2) - f(x)}{\lambda} \leqslant
\]
\[
\leqslant \lim \limits_{\lambda \to 0+} \dfrac{\alpha f(x + \lambda y_1) + \beta f(x + \lambda y_2) - \alpha f(x) - \beta f(x)}{\lambda} =
\]
\[
= \lim \limits_{\lambda \to 0+} \alpha \dfrac{f(x + \lambda y_1) - f(x)}{\lambda} + \lim \limits_{\lambda \to 0+} \beta \dfrac{f(x + \lambda y_2) - f(x)}{\lambda} = \alpha f'(x, y_1) + \beta f'(x, y_2).
\]

Значит, функция $$f'(x, \cdot)$$ выпукла. Из ее выпуклости и положительной однородности получаем $$f'(x,y) + f'(x, -y) \geqslant 2f'(x, \frac{y + (-y)}{2}) = 2f'(x,0) = 0$$, откуда имеем $$-f'(x,-y) \leqslant f'(x,y)$$. $$\blacksquare$$

'''Лемма 1.'''
Пусть $$f -$$ собственная выпуклая функция и $$x \in \text{int}(\text{dom }f)$$. Тогда существует $$c > 0$$ такое, что
\[
|f'(x,y)| \leqslant c|y|~~\forall y,
\]
где $$\text{int A} -$$ [https://ru.wikipedia.org/wiki/%D0%92%D0%BD%D1%83%D1%82%D1%80%D0%B5%D0%BD%D0%BD%D0%BE%D1%81%D1%82%D1%8C внутренность множества]$$A -$$ множество всех внутренних точек множества $$A$$.

'''Доказательство:'''

По [https://sawiki.cs.msu.ru/index.php?title=%D0%92%D1%8B%D0%BF%D1%83%D0%BA%D0%BB%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%B8_%D0%B5%D0%B5_%D1%81%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0&action=edit&redlink=1 теореме о липшицевости выпуклой функции] существует такая окрестность $$O$$ точки $$x$$, что функция $$f$$ на $$O$$ удовлетворяет условию Липшица с некоторой константой $$c > 0$$. Поэтому для каждого фиксированного $$y$$ неравенство $$\left| \dfrac{f(x + \lambda y) - f(x)}{\lambda} \right| \leqslant c|y|$$ выполняется при всех достаточно малых $$\lambda > 0$$. Искомое утверждение непосредственно вытекает из этого неравенства и соотношения
\[
f'(x,y) = \lim \limits_{\lambda \to 0+} \dfrac{f(x + \lambda y) - f(x)}{\lambda}.\blacksquare
\]

'''Лемма 2.'''
Пусть функция $$f$$ выпукла и конечна в точке $$x$$. Тогда
\[
x^* \in \partial f(x) \Leftrightarrow f'(x,y) \geqslant \langle x^*, y \rangle~~\forall y \in X.
\]

'''Доказательство:'''

Пусть $$x^* \in \partial f(x)$$. Тогда в силу субградиентного неравенства при всяком $$\lambda > 0$$ имеем $$f(x + \lambda y) - f(x) \geqslant \langle x^*, y \rangle~~\forall y$$ и, значит,
\[
f'(x,y) = \lim \limits_{\lambda \to 0+} \dfrac{f(x + \lambda y) - f(x)}{\lambda} \geqslant \langle x^*, y \rangle.
\]
Теперь пусть
\[
\langle x^*, y \rangle \leqslant f'(x,y) = \inf \limits_{\lambda > 0} \dfrac{f(x + \lambda y) - f(x)}{\lambda}~~\forall y \Rightarrow
\]
\[
\Rightarrow f(x + \lambda y) - f(x) \geqslant \langle x^*, y \rangle~~\forall y \in X,~~\forall \lambda > 0.
\]
Отсюда при $$\lambda = 1, z = x + y$$ имеем $$f(z) - f(x) \geqslant \langle x^*, z - x \rangle~~\forall z \in X$$, откуда $$x^* \in \partial f(x)$$. $$\blacksquare$$

'''Лемма 3.'''
Пусть функция $$f$$ выпуклая, собственная и $$x \in \text{int}(\text{dom }f)$$. Тогда функция $$\text{cl }f'(x,\cdot)$$, являющаяся замыканием производной $$f'(x,y)$$ как выпуклой функции от $$y$$, совпадает c [https://sawiki.cs.msu.ru/index.php/%D0%9E%D0%BF%D0%BE%D1%80%D0%BD%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0 опорной функцией] множества $$\partial f(x)$$, где $$\text{cl }A -$$ замыкание множества $$A$$.

'''Доказательство:'''

По теореме 1 и лемме 1 функция $$f'(x,\cdot)$$ является выпуклой, положительно однородной и собственной. Поэтому имеет место $$\text{cl }f'(x,\cdot) = \text{c}(\cdot, A)$$, где $$A = \{x^*: \langle x^*, y \rangle \leqslant f'(x,y)~~\forall y\}$$. По лемме 2: $$A = \partial f(x)$$. $$\blacksquare$$

==Структура субдифференциала выпуклой функции==

'''Теорема 2.'''
Пусть $$f -$$ выпуклая собственная функция и $$x \in \text{int}(\text{dom }f)$$. Тогда субдифференциал $$\partial f(x)$$ в точке $$x$$ является непустым компактом.

'''Доказательство:'''

Вначале докажем, что $$\partial f(x) \neq \varnothing.$$ Рассмотрим множество $$\text{cl epi }f (\text{epi }f = \{(x, \alpha) \in X \times \mathbb{R}: f(x) \leqslant \alpha\} -$$ надграфик функции $$f$$). Оно выпукло, [https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%BC%D0%BA%D0%BD%D1%83%D1%82%D0%BE%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE замкнуто], и $$(x, f(x)) \notin \text{int}(\text{cl epi }f).$$ Здесь несложно показать, что последнее утверждение вытекает из непрерывности на $$\text{int}(\text{dom }f)$$ определенной на $$\mathbb{R}^n$$ выпуклой собственной функции. Поэтому по [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE%D1%82%D0%B4%D0%B5%D0%BB%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8 теореме отделимости] существуют $$x^* \in \mathbb{R}^n, r \in \mathbb{R}$$ такие, что
\[
r\alpha + \langle x^*, z \rangle \geqslant rf(x) + \langle x^*, x \rangle \; \forall \alpha, z: \alpha \geqslant f(z).
\]
Условие $$r \neq 0$$ вытекает из того, что $$x \in \text{int}(\text{dom }f)$$. Условие $$r > 0$$ следует из того, что приведенное неравенство выполняется при сколь угодно больших $$\alpha \geqslant f(z)$$. Поэтому, не теряя общности, будем считать, что $$r = 1$$. Из приведенного неравенства при $$\alpha = f(z)$$ имеем
\[
f(z) \geqslant f(x) + \langle -x^*, z-x \rangle \; \forall z \Rightarrow -x^* \in \partial f(x)
\]
и, значит, $$\partial f(x) \neq \varnothing$$.

Докажем ограниченность множества $$\partial f(x)$$. Действительно, предположим обратное, т. е. что в $$\partial f(x)$$ существует такая последовательность $$\{x^*_i\}$$, что $$|x^*_i| \rightarrow \infty$$. Выберем такое $$\delta > 0$$, что $$\text{cl}(O(x, \delta)) \subset \text{int}(\text{dom }f)$$. Тогда функция $$f$$ непрерывна и, значит, ограничена на компакте $$\text{cl}(O(x, \delta))$$. Положим $$x_i = x + \delta x^*_i/|x^*_i|$$. Из субградиентного неравенства при $$y = x_i$$ и $$x^* = x^*_i$$ получаем что $$f(x_i) \geqslant f(x) + \delta|x^*_i|$$. Но в полученном неравенстве правая часть стремится к бесконечности, а левая ограничена, поскольку $$x_i \in \text{cl}(O(x, \delta)) \; \forall i$$. Это противоречие доказывает ограниченность множества $$\partial f(x)$$.

Докажем замкнутость множества $$\partial f(x)$$. Пусть $$x^*_i \in \partial f(x) \; \forall i$$ и $$x^*_i \rightarrow x^*$$. При каждом фиксированном $$y$$, подставляя в субградиентное неравенство $$x^* = x^*_i$$ и переходя к пределу при $$i \rightarrow \infty$$,
получаем $$x^* \in \partial f(x)$$.

Осталось доказать выпуклость множества $$\partial f(x)$$. Пусть $$x_1^*, x_2^* \in \partial f(x), \alpha \geqslant 0, \beta \geqslant 0, \alpha + \beta = 1$$. Тогда:
\[
f(z) - f(x) \geqslant \langle x_1^*, z - x \rangle, \; f(z) - f(x) \geqslant \langle x_2^*, z - x \rangle \; \forall z \in X.
\]
При фиксированном $$z$$ умножим первое из этих неравенств на $$\alpha$$, а второе на $$\beta$$, и затем сложим их. В результате этого получаем, что $$\alpha x_1^* + \beta x_2^* \in \partial f(x). \blacksquare$$

'''Лемма 4''' (альтернатива). Пусть выпуклая функция $$f$$ конечна в точке $$x_0$$, принадлежащей границе эффективного множества $$\text{dom }f$$. Тогда в этой точке субдифференциал $$\partial f(x_0)$$ либо пуст, либо содержит бесконечно много точек.

'''Доказательство:'''

В силу выпуклости субдифференциала $$\partial f(x_0)$$ достаточно доказать, что если это множество непусто, то оно содержит хотя бы два различных элемента. Итак, пусть $$x^* \in \partial f(x_0)$$. Рассмотрим выпуклую функцию $$h(y) = f(x_0 + y) - f(x_0) - \langle x^*,y \rangle$$. Для нее $$h(0) = 0$$, и нуль принадлежит границе эффективного множества $$\text{dom }h$$. Кроме того, $$0 \in \partial h(0)$$, откуда в силу субградиентного неравенства получаем, что $$h(y) \geqslant 0 ~~\forall y \in X$$.

В силу сказанного выше $$0 \notin \text{int(dom }h)$$. Поэтому выпуклое множество $$\text{dom }h$$ можно отделить от нуля и, значит, в силу конечномерной теоремы отделимости существует такой $$a \in X, a \neq 0$$ что $$\langle a,y \rangle \leqslant 0 ~~\forall y \in \text{dom }h.$$ Следовательно, $$h(y) \geqslant \langle a,y \rangle ~~\forall y \in X,$$ поскольку $$h(y) \geqslant 0 ~~\forall y \in X.$$ Значит, $$0,a \in \partial h(0), a \neq 0 \Rightarrow x^*, (a + x^*) \in \partial f(x_0)$$. $$\blacksquare$$

'''Лемма 5''' (бесконечномерная альтернатива). Пусть $$X -$$ произвольное [https://ru.wikipedia.org/wiki/%D0%9D%D0%BE%D1%80%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%82%D0%B2%D0%BE нормированное пространство], а заданная на нем выпуклая функция $$f$$ конечна в точке $$x_0$$, принадлежащей границе эффективного множества $$\text{dom }f$$, и, кроме того, внутренность эффективного множества $$\text{int(dom }f)$$ непуста. Тогда в этой точке субдифференциал $$\partial f(x_0)$$ либо пуст, либо содержит бесконечно много точек.

'''Доказательство:'''

Доказательство этой леммы аналогично доказательству предыдущей, но вместо теоремы о конечномерной отделимости следует использовать теорему отделимости. $$\blacksquare$$

==Пример к теореме 2==
Рассмотрим на $$\mathbb{R}$$ функцию
\[
f(x) =
\begin{cases}
-(1 - x^2)^{\frac{1}{2}}, & \quad |x| \leqslant 1,\\
+\infty, & \quad |x| > 1.
\end{cases}
\]
Эта функция субдифференцируема (и даже дифференцируема) во всех точках $$x \in \text{int}(\text{dom }f) = (-1,1)$$. Однако в точках $$x = 1, -1$$, составляющих границу $$\text{dom }f$$, ее субдифференциал пуст.

==Критерий дифференцируемости==

'''Теорема 3.'''
Пусть выпуклая функция $$f$$ конечна в точке $$x_0$$. Если $$f$$ дифференцируема в точке $$x_0$$, то субдифференциал $$\partial f(x_0)$$ содержит единственный элемент $$f'(x_0)$$ и, в частности,
\[
f(z) \geqslant f(x_0) + \langle f'(x_0), z - x_0 \rangle~~\forall z \in X.
\]
Наоборот, если субдифференциал $$\partial f(x_0)$$ содержит единственный элемент, то функция $$f$$ дифференцируема в точке $$x_0$$ и $$\partial f(x_0) = \{f'(x_0)\}$$.

'''Доказательство:'''

Пусть $$f$$ дифференцируема в точке $$x_0$$. Тогда $$f'(x_0,y) = \langle f'(x_0),y \rangle~~\forall y$$. Поэтому в силу леммы 2 для любого $$x^* \in \partial f(x_0)$$ выполняется
\[
\langle f'(x_0),y \rangle = f'(x_0,y) \geqslant \langle x^*,y \rangle~~\forall y \in X,
\]
откуда
\[
\langle (f'(x_0) - x^*),y \rangle \geqslant 0 \rangle~~\forall y \in X.
\]
Но если линейный функционал неотрицателен на всем пространстве, то он равен нулю и, следовательно, $$x^* = f'(x_0)~~\forall x^* \in \partial f(x_0)$$, т.е. субдифференциал $$\partial f(x_0)$$ состоит из единственной точки $$f'(x_0)$$.

Пусть теперь $$\partial f(x_0) = \{x^*\}$$. Рассмотрим выпуклую функцию $$h(y) = f(x_0 + y) - f(x_0) - \langle x^*,y \rangle$$. Для нее $$h(0) = 0, \partial h(0) = \{0\}$$, откуда в силу субградиентного неравенства получаем $$h(y) \geqslant 0~~\forall y \in X$$ и, значит, функция $$h$$ является собственной. Кроме того, в силу леммы 4 имеет место $$0 \in \text{int}(\text{dom }h)$$. Поэтому согласно лемме 3 функция $$\text{cl }h'(0,\cdot)$$ является опорной функцией для множества $$\partial h(0)$$. Таким образом, $$\text{cl }h'(0,y) = \text{c}(y, \partial h(0)) = 0~~\forall y \in X$$.

Итак, $$0 \in \text{int}(\text{dom }h)$$, а $$h -$$ собственная выпуклая функция. Поэтому в силу леммы 1 выпуклая функция $$h'(0,\cdot)$$ принимает лишь конечные значения и, следовательно, она непрерывна на $$\mathbb{R}^n$$. Поэтому в силу доказанного выше $$h'(0,y) \equiv 0$$. Следовательно,
\[
\lim \limits_{\lambda \to 0+} \dfrac{h(\lambda y)}{\lambda} = 0~~\forall y \in X.
\]
Кроме того, из доказательства теоремы 1 вытекает, что при каждом фиксированном $$y$$ функция $$g(\lambda) = \dfrac{h(\lambda y)}{\lambda}$$ не убывает при $$\lambda > 0$$.

При произвольном $$\lambda > 0$$ рассмотрим функцию $$g_{\lambda}(u) = \dfrac{h(\lambda y)}{\lambda}$$. Каждая из функций $$g_{\lambda}$$ выпукла, и для любого $$u$$ в силу доказанного имеем: $$g_{\lambda}(u) \to 0, \lambda \to 0+, g_{\lambda}(u) \geqslant 0$$. Пусть $$B = \{x: |x| \leqslant 1\} -$$ единичный шар, а $$\{b_1,...,b_m\} -$$ конечный набор точек, выпуклая оболочка которых содержит $$B$$.

Всякое $$u \in B$$ можно представить в виде выпуклой комбинации $$u = \alpha_1 b_1 +...+ \alpha_m b_m$$. Следовательно, в силу выпуклости каждой из функций $$g_{\lambda}$$, для любого $$u \in B$$ имеет место
\[
0 \leqslant g_{\lambda}(u) \leqslant \alpha_1 g_{\lambda}(b_1) +...+ \alpha_m g_{\lambda}(b_m) \leqslant \max\{g_{\lambda}(b_i), i = 1,...,m\}.
\]
Тогда, поскольку $$g_{\lambda}(b_i) \to 0. \lambda \to 0+$$ для каждого $$i$$, функция $$g_{\lambda}$$ сходятся к нулю равномерно на $$B$$. Поэтому для любого $$\varepsilon > 0$$ существует $$\delta > 0$$ такое, что
\[
\dfrac{h(\lambda u)}{\lambda} \leqslant \varepsilon~~\forall \lambda \in (0, \delta],~~\forall \in B.
\]
Но любой вектор $$y \neq 0, |y| \leqslant \delta$$ можно представить в виде $$y = \lambda u$$, где $$\lambda = |y| \leqslant \delta, u = \dfrac{y}{|y|} \in B$$. Поэтому неравенство $$\dfrac{h(y)}{|y|} \leqslant \varepsilon$$ выполняется при всех $$y$$, для которых $$|y| \leqslant \delta$$.

Таким образом, мы доказали, что $$\dfrac{h(y)}{|y|} \to 0, y \to 0$$. Иными словами, функция $$h$$ дифференцируема в нуле, причем ее производная равна нулю. Значит, $$f$$ дифференцируема в точке $$x_0$$. $$\blacksquare$$

== Список литературы ==
''Арутюнов А. В.'' Лекции по выпуклому и многозначному анализу. — М.: ФИЗМАТЛИТ, 2014

2022-11-05T16:19:58Z

Alexandra22:

2022-10-24T17:14:57Z

Alexandra22:

== Введение и определения ==
В общей форме дифференциальное включение записывается в виде:
\begin{equation}
\label{1}
\dot{x} \in F(x,t)
\end{equation}
Здесь $$t \in \mathbb{R}$$ - время, $$\dot{x} = \dfrac{dx}{dt}$$ - производная по времени, $$F = F(x,t)$$ - заданное многозначное отображение, ставящее в соответствие каждой паре $$(t,x), t \in \mathbb{R}, x \in \mathbb{R}^n$$, непустой замкнутое подмножество $$F(x,t) \subset \mathbb{R}^n.$$
==== Решение дифференциального включения ====
Решением этого дифференциального включения на заданном отрезке $$[t_1,t_2]$$ называется абсолютно непрерывная функция $$x(t), t \in [t_1,t_2]$$, удовлетворяющая для почти всех $$t$$ включению $$\dot{x}(t) \in F(x(t),t)$$

==== Задача Коши для дифференциального включения ====
Задача Коши для дифференциального включения имеет вид
\begin{equation}
\label{2}
\dot{x} \in F(x,t),~ ~ ~ x(t_0) = x_0
\end{equation}
и заключается в нахождении абсолютно непрерывной функции $$x(\cdot)$$, которая для некоторого $$\overline{t}>t_0$$ при почти всех $$t \in (t_0,\overline{t})$$ удовлетворяет дифференциальному включению $$\dot{x}(t) \in F(x(t),t)$$ и начальному условию $$x(t_0) = x_0$$, где $$x_0$$ и $$t_0$$ заданы. Функция $$x(\cdot)$$ называется ее локальным решением.
== Теорема существования локального решения задачи Коши для дифференциальных включений ==
'''Теорема 1.''' Пусть в $$\mathbb{R}^n \times \mathbb{R}$$ задано открытое множество $$G$$ и на нем определено многозначное отображение $$F$$ со значениями в $$\mathbb{R}^n$$. Пусть его значения $$F(x,t)$$ выпуклы и компактны для любых $$(x,t)$$, а само $$F$$ полунепрерывно сверху.

Тогда для любой точки $$(x_0,t_0) \in G$$ существует локальное решение задачи Коши $$\ref{2}$$. Более того, для любых $$\alpha, \beta > 0$$ таких, что
\[
Z = O(x_0,\beta) \times [t_0,t_0+\alpha] \subset G,
\]
при
\[
d = min(\alpha, \dfrac{\beta}{m}), ~ ~m = sup\{|y|, y \in F(x,t), (x,t) \in Z\}
\]
на отрезке $$[t_0,t_0+d]$$ существует решение задачи Коши $$\ref{2}~ x(\cdot)$$ (т.е. $$\dot{x}(t) \in F(x(t),t)$$ для почти всех $$t \in [t_0,t_0+d]$$).

Отметим, что из полунепрерывности сверху и компактнозначности многозначного отображения $$F$$ легко получить, что точная верхняя грань $$m$$ конечна.
== Вспомогательные леммы ==
'''Лемма 1.''' Пусть $$D$$ - выпуклый компакт в $$\mathbb{R}^n, v(\cdot):[a,b] \to D$$ - измеримая вектор-функция. Тогда
\[
(b-a)^{-1} \int_a^b v(t)dt \in D.
\]
'''Доказательство:'''

Положим
\[
d = (b-a)^{-1} \int_a^b v(t)dt.
\]
Предположим, что $$d \notin D.$$ Тогда по теореме о строгой отделимости выпуклых компактов существуют такие $$l \in \mathbb{R}^n$$ и число $$\alpha$$, что $$\langle l,x \rangle \leqslant \alpha ~\forall x \in D$$ и $$\langle l,d \rangle > \alpha$$. Отсюда имеем
\[
\alpha < \langle l,d \rangle = (b-a)^{-1} \int_a^b \langle l,v(t) \rangle dt \leqslant (b-a)^{-1} \int_a^b \alpha dt = \alpha.
\]
Полученное противоречие завершает доказательство.

'''Лемма 2.''' Пусть $$D$$ - выпуклый компакт в $$\mathbb{R}^n$$, а $$\{x_k\}$$ - последовательность таких абсолютно непрерывных функций $$\{x_k\}: [a,b] \to \mathbb{R}^n$$, что $$x_k(t) \to x(t)$$ при каждом $$t$$, а также для каждого $$k$$ и почти всех $$t \in [a,b]$$ имеет место $$\dot{x_k}(t) \in D$$ для почти всех $$t$$.

'''Доказательство:'''

В силу ограниченности множества $$D$$ существует такое $$c > 0$$, что $$|\dot{x_k}(t)| \leqslant c$$ для всех $$k$$ и почти всех $$t$$. Возьмем произвольные $$t_1, t_2 \in [a,b]$$. С помощью формулы Ньютона-Лейбница имеем
\[
|x_k(t_2) - x_k(t_1)| = \Bigr| \int \limits_{t_1}^{t_2} \dot{x_k}(t) dt \Bigl| \leqslant \int \limits_{t_1}^{t_2} |\dot{x_k}(t)| dt \leqslant c|t_2 - t_1|.
\]
Переходя в этом неравенстве к пределу при $$k \to \infty,$$ получаем
\[
|x(t_2) - x(t_1)| \leqslant c|t_2 - t_1| ~\forall t_1, t_2 \in [a,b].
\]
Следовательно, функция $$x(\cdot)$$ удовлетворяет условию Липшица и, значит, она абсолютно непрерывна.

С помощью формулы Ньютона-Лейбница в силу Леммы 1 для почти всех $$t \in (a,b)$$ и достаточно малых $$\tau > 0$$ имеем
\[
\tau^{-1}(x_k(t+\tau) - x_k(\tau)) = \tau^{-1} \int \limits_{t}^{t+\tau} \dot{x_k}(t)dt \in D.
\]
переходя к пределу при $$k \to \infty$$, получаем
\begin{equation}
\label{3}
\tau^{-1}(x(t+\tau) - x(\tau)) \in D.
\end{equation}
Но функция $$x(\cdot)$$ абсолютно непрерывна и, значит, она дифференцируема почти всюду. Поэтому из $$\ref{3}$$ при $$\tau \to 0$$ получаем, что $$\dot{x}(t) \in D$$ для почти всех $$t$$.
Лемма доказана.

Ниже для удобства для $$\delta > 0$$ через $$M^{\delta}$$ будем обозначать замкнутую $$\delta$$-окрестность множества $$M$$, т.е. $$M^{\delta} = B(M,\delta)$$. Для $$\delta > 0$$ абсолютно непрерывная функция $$y: [a,b] \to \mathbb{R}^n$$ называется $$\delta$$-решением (приближенным с точностью до $$\delta$$) дифференциального включения $$\ref{1}$$ на отрезке $$[a,b]$$, если
$$\dot{y}(t) \in F_{\delta}(y,t)$$ для почти всех $$t \in [a,b]$$, где $$F_{\delta}(y,t) = (convF(y^{\delta},t^{\delta}))^{\delta}$$.

'''Лемма 3.''' Пусть для $$F$$ выполняются все предположения теоремы 1. Пусть $$\delta_k \to 0+$$, функции $$x_k$$ являются $$\delta_k$$-решениями дифференциального включения $$\ref{1}$$ на отрезке $$[a,b]$$, а последовательность функций $$\{x_k\}$$ равномерно сходится к функции $$x(\cdot)$$, причем $$(x(t),t) \in G ~\forall t \in [a,b]$$. Тогда предельная функция $$x(\cdot)$$ является решением $$\ref{1}$$ на отрезке $$[a,b]$$.

'''Доказательство:'''

Функция $$x(\cdot)$$ непрерывна как равномерный предел непрерывных функций. Зафиксируем произвольное $$\tau \in [a,b]$$ и возьмем любое $$\epsilon > 0$$. По условию $$F$$ полунепрерывно сверху. Поэтому существует такое $$\eta > 0$$, что
\begin{equation}
\label{4}
F(x,t) \subset A^\epsilon ~\forall (x,t) \in G_0,
\end{equation}
где
\[
G_0 = \{(x,t): |t-\tau| \leqslant 2\eta, |x-x(\tau)| \leqslant 3\eta\},~ A = F(x(\tau), \tau).
\]
В силу непрерывности функции $$x(\cdot)$$ существуют такие $$\gamma \in (0, \eta)$$ и номер $$k_0$$, что
\[
\delta_k < min\{\eta,\epsilon\}, |x_k(t) - x(t)| \leqslant \eta, |x(t) - x(\tau)| \leqslant \eta
\]
для всех $$t$$ таких, что $$|t-\tau|<\gamma$$, и всех $$k<k_0$$. Отсюда и из $$\ref{4}$$ при $$\delta = \delta_k, k > k_0, |t-\tau|<\gamma<\eta$$ имеем:
\[
t^\delta \subset \tau^{2\eta}, (x_k(t))^\delta \subset (x(t))^{3\eta} \Rightarrow F((x_k(t))^\delta, t^\delta) \subset a^\epsilon
\]
Поскольку функция $$x_k$$ является $$\delta_k$$-решением, а множество $$A$$ выпукло, то для почти всех $$t$$ выполняется
\[
\dot{x_k}(t) \in (convF(x_k(t)^{\delta},t^{\delta}))^{\delta} \subset (convA^\epsilon)^\delta \subset A^{2\epsilon}.
\]
Поэтому в силу леммы 2 на множестве $$\{t:|t-\tau|<\gamma\}$$ функция $$x(\cdot)$$ абсолютно непрерывна и для почти всех $$t$$ из этого множества $$\dot{x}(t) \in A^{2\epsilon}$$.

Таким образом, доказано, что для любого $$\tau$$ из отрезка $$[a,b]$$ существует такой интервал, содержащий содержащий точку $$\tau$$, что на пересечении отрезка $$[a,b]$$ с этим интервалом функция $$x(\cdot)$$ абсолютно непрерывна. Выбирая из этого покрытия отрезка $$[a,b]$$ открытыми интервалами конечное подпокрытие, получаем, что функция $$x(\cdot)$$ абсолютно непрерывна на $$[a,b]$$. Кроме того, доказано, что для любого $$\tau \in (a,b)$$, при котором функция $$x(\cdot)$$ дифференцируема в точке $$\tau$$, имеет место $$\dot{x}(\tau) \in F(x(\tau),\tau)^{2\epsilon}$$ для произвольного $$\epsilon > 0$$. Переходя в этом дифференциальном включении к пределу при $$\epsilon \to 0$$, в силу замкнутости множества $$F(x(\tau), \tau)$$ получаем, что $$\dot{x}(\tau) \in F(x(\tau), \tau)$$. Таким образом, $$x(\cdot)$$ является решением $$\ref{1}$$.

== Доказательство теоремы 1 ==
Проведем доказательство методом ломаных Эйлера. Для $$k = 1,2,...$$ положим:
\[
h_k = \frac{d}{k}, t_{k,i} = t_0 + ih_k, i = 0,1,...,k.
\]
Построим ломаную $$x_k(t)$$. Положим $$x_k(t_{k,0}) = x_0$$. Если для некоторого $$i$$ значение $$x_k(t_{k,i})$$ уже определено и
\begin{equation}
\label{5}
|x_k(t_{k,i}) - x_0| \leqslant m|t_{k,i} - t_0|,
\end{equation}
то при $$t \in (t_{k,i}, t_{k,i+1}]$$ определим $$x_k(t)$$ по формуле
\begin{equation}
\label{6}
x_k(t) = x_k(t_{k,i}) + (t - t_{k,i})v_{k,i},
\end{equation}
взяв любое $$v_{k,i} \in F(x_k(t_{k,i}), t_{k,i}).$$

Поскольку в силу $$\ref{5} (x_k(t_{k,i}),t_{k,i}) \in Z$$, то $$|v_{k,i}| \leqslant m$$, и из $$\ref{5}, \ref{6}$$ имеем
\begin{equation}
\label{7}
|x_k(t) - x_0| \leqslant |x_k(t) - x_k(t_{k,i})| + |x_k(t_{k,i}) - x_0| \leqslant m|t-t_0| ~\forall t \in (t_{k,i},t_{k,i+1}].
\end{equation}
При этом справедливо неравенство, полученное из $$\ref{5}$$ заменой $$i$$ на $$i+1$$.
Таким образом, ломаная $$x_k$$ последовательно строится на отрезках $$[t_{k,i}, t_{k,i+1}]$$ при $$i = 0,1,...,k-1$$. В силу $$\ref{7} (x_k(t),t) \in Z ~\forall t \in [t_0,t_0+d]$$. В силу $$\ref{6}$$ функция $$x_k$$ абсолютно непрерывна и $$|\dot{x_k}(t) \leqslant m| ~\forall t \neq t_{k,i}$$. Поскольку
\begin{equation}
\dot{x_k}(t) = v_{k,i} \in F(x_k(t_{k,i}),t_{k,i}), |x_k(t) - x_k(t_{k,i})| \leqslant mh_k ~\forall t \in [x_k(t_{k,i}), x_k(t_{k,i}) + h_k],
\end{equation}
то $$x_k$$ является $$\sigma_k$$-решением включения $$\ref{2}$$ при $$\sigma_k = h_kmax\{1,m\}$$, причем $$\sigma_k \to 0, k \to \infty$$.

В силу $$\ref{7}$$ последовательность функций $$\{x_k\}$$ равномерно ограничена, а в силу оценки $$|\dot{x_k}| \leqslant m$$ она равностепенно непрерывна. Поэтому по теореме Арцела из этой последовательности можно выбрать равномерно сходящуюся подпоследовательность. По лемме 3 ее предел $$x(\cdot)$$ является решением $$\ref{1}$$. Из того, что $$x_k(t_0) = x_0$$ при всех $$k$$^ имеем $$x(t_0) = x_0$$.

Теорема доказана.
== Список литературы ==
1) Арутюнов А. В. "Лекции по выпуклому и многозначному анализу", М.: ФИЗМАТЛИТ, 2014.

Дифференциальные включения. Теорема о существовании решений

2022-10-24T17:11:37Z

Alexandra22: Новая страница: «== Введение и определения == В общей форме дифференциальное включение записывается в виде...»

== Введение и определения ==
В общей форме дифференциальное включение записывается в виде:
\begin{equation}
\label{1}
\dot{x} \in F(x,t)
\end{equation}
Здесь $$t \in \mathbb{R}$$ - время, $$\dot{x} = \dfrac{dx}{dt}$$ - производная по времени, $$F = F(x,t)$$ - заданное многозначное отображение, ставящее в соответствие каждой паре $$(t,x), t \in \mathbb{R}, x \in \mathbb{R}^n$$, непустой замкнутое подмножество $$F(x,t) \subset \mathbb{R}^n.$$
==== Решение дифференциального включения ====
Решением этого дифференциального включения на заданном отрезке $$[t_1,t_2]$$ называется абсолютно непрерывная функция $$x(t), t \in [t_1,t_2]$$, удовлетворяющая для почти всех $$t$$ включению $$\dot{x}(t) \in F(x(t),t)$$

==== Задача Коши для дифференциального включения ====
Задача Коши для дифференциального включения имеет вид
\begin{equation}
\label{2}
\dot{x} \in F(x,t),~ ~ ~ x(t_0) = x_0
\end{equation}
и заключается в нахождении абсолютно непрерывной функции $$x(\cdot)$$, которая для некоторого $$\overline{t}>t_0$$ при почти всех $$t \in (t_0,\overline{t})$$ удовлетворяет дифференциальному включению $$\dot{x}(t) \in F(x(t),t)$$ и начальному условию $$x(t_0) = x_0$$, где $$x_0$$ и $$t_0$$ заданы. Функция $$x(\cdot)$$ называется ее локальным решением.
== Теорема существования локального решения задачи Коши для диффеенциальных включений ==
'''Теорема 1.''' Пусть в $$\mathbb{R}^n \times \mathbb{R}$$ задано открытое множество $$G$$ и на нем определено многозначное отображение $$F$$ со значениями в $$\mathbb{R}^n$$. Пусть его значения $$F(x,t)$$ выпуклы и компактны для любых $$(x,t)$$, а само $$F$$ полунепрерывно сверху.

Тогда для любой точки $$(x_0,t_0) \in G$$ существует локальное решение задачи Коши $$\ref{2}$$. Более того, для любых $$\alpha, \beta > 0$$ таких, что
\[
Z = O(x_0,\beta) \times [t_0,t_0+\alpha] \subset G,
\]
при
\[
d = min(\alpha, \dfrac{\beta}{m}), ~ ~m = sup\{|y|, y \in F(x,t), (x,t) \in Z\}
\]
на отрезке $$[t_0,t_0+d]$$ существует решение задачи Коши $$\ref{2}~ x(\cdot)$$ (т.е. $$\dot{x}(t) \in F(x(t),t)$$ для почти всех $$t \in [t_0,t_0+d]$$).

Отметим, что из полунепрерывности сверху и компактнозначности многозначного отображения $$F$$ легко получить, что точная верхняя грань $$m$$ конечна.
== Вспомогательные леммы ==
'''Лемма 1.''' Пусть $$D$$ - выпуклый компакт в $$\mathbb{R}^n, v(\cdot):[a,b] \to D$$ - измеримая вектор-функция. Тогда
\[
(b-a)^{-1} \int_a^b v(t)dt \in D.
\]
'''Доказательство:'''

Положим
\[
d = (b-a)^{-1} \int_a^b v(t)dt.
\]
Предположим, что $$d \notin D.$$ Тогда по теореме о строгой отделимости выпуклых компактов существуют такие $$l \in \mathbb{R}^n$$ и число $$\alpha$$, что $$\langle l,x \rangle \leqslant \alpha ~\forall x \in D$$ и $$\langle l,d \rangle > \alpha$$. Отсюда имеем
\[
\alpha < \langle l,d \rangle = (b-a)^{-1} \int_a^b \langle l,v(t) \rangle dt \leqslant (b-a)^{-1} \int_a^b \alpha dt = \alpha.
\]
Полученное противоречие завершает доказательство.

'''Лемма 2.''' Пусть $$D$$ - выпуклый компакт в $$\mathbb{R}^n$$, а $$\{x_k\}$$ - последовательность таких абсолютно непрерывных функций $$\{x_k\}: [a,b] \to \mathbb{R}^n$$, что $$x_k(t) \to x(t)$$ при каждом $$t$$, а также для каждого $$k$$ и почти всех $$t \in [a,b]$$ имеет место $$\dot{x_k}(t) \in D$$ для почти всех $$t$$.

'''Доказательство:'''

В силу ограниченности множества $$D$$ существует такое $$c > 0$$, что $$|\dot{x_k}(t)| \leqslant c$$ для всех $$k$$ и почти всех $$t$$. Возьмем произвольные $$t_1, t_2 \in [a,b]$$. С помощью формулы Ньютона-Лейбница имеем
\[
|x_k(t_2) - x_k(t_1)| = \Bigr| \int \limits_{t_1}^{t_2} \dot{x_k}(t) dt \Bigl| \leqslant \int \limits_{t_1}^{t_2} |\dot{x_k}(t)| dt \leqslant c|t_2 - t_1|.
\]
Переходя в этом неравенстве к пределу при $$k \to \infty,$$ получаем
\[
|x(t_2) - x(t_1)| \leqslant c|t_2 - t_1| ~\forall t_1, t_2 \in [a,b].
\]
Следовательно, функция $$x(\cdot)$$ удовлетворяет условию Липшица и, значит, она абсолютно непрерывна.

С помощью формулы Ньютона-Лейбница в силу Леммы 1 для почти всех $$t \in (a,b)$$ и достаточно малых $$\tau > 0$$ имеем
\[
\tau^{-1}(x_k(t+\tau) - x_k(\tau)) = \tau^{-1} \int \limits_{t}^{t+\tau} \dot{x_k}(t)dt \in D.
\]
переходя к пределу при $$k \to \infty$$, получаем
\begin{equation}
\label{3}
\tau^{-1}(x(t+\tau) - x(\tau)) \in D.
\end{equation}
Но функция $$x(\cdot)$$ абсолютно непрерывна и, значит, она дифференцируема почти всюду. Поэтому из $$\ref{3}$$ при $$\tau \to 0$$ получаем, что $$\dot{x}(t) \in D$$ для почти всех $$t$$.
Лемма доказана.

Ниже для удобства для $$\delta > 0$$ через $$M^{\delta}$$ будем обозначать замкнутую $$\delta$$-окрестность множества $$M$$, т.е. $$M^{\delta} = B(M,\delta)$$. Для $$\delta > 0$$ абсолютно непрерывная функция $$y: [a,b] \to \mathbb{R}^n$$ называется $$\delta$$-решением (приближенным с точностью до $$\delta$$) дифференциального включения $$\ref{1}$$ на отрезке $$[a,b]$$, если
$$\dot{y}(t) \in F_{\delta}(y,t)$$ для почти всех $$t \in [a,b]$$, где $$F_{\delta}(y,t) = (convF(y^{\delta},t^{\delta}))^{\delta}$$.

'''Лемма 3.''' Пусть для $$F$$ выполняются все предположения теоремы 1. Пусть $$\delta_k \to 0+$$, функции $$x_k$$ являются $$\delta_k$$-решениями дифференциального включения $$\ref{1}$$ на отрезке $$[a,b]$$, а последовательность функций $$\{x_k\}$$ равномерно сходится к функции $$x(\cdot)$$, причем $$(x(t),t) \in G ~\forall t \in [a,b]$$. Тогда предельная функция $$x(\cdot)$$ является решением $$\ref{1}$$ на отрезке $$[a,b]$$.

'''Доказательство:'''

Функция $$x(\cdot)$$ непрерывна как равномерный предел непрерывных функций. Зафиксируем произвольное $$\tau \in [a,b]$$ и возьмем любое $$\epsilon > 0$$. По условию $$F$$ полунепрерывно сверху. Поэтому существует такое $$\eta > 0$$, что
\begin{equation}
\label{4}
F(x,t) \subset A^\epsilon ~\forall (x,t) \in G_0,
\end{equation}
где
\[
G_0 = \{(x,t): |t-\tau| \leqslant 2\eta, |x-x(\tau)| \leqslant 3\eta\},~ A = F(x(\tau), \tau).
\]
В силу непрерывности функции $$x(\cdot)$$ существуют такие $$\gamma \in (0, \eta)$$ и номер $$k_0$$, что
\[
\delta_k < min\{\eta,\epsilon\}, |x_k(t) - x(t)| \leqslant \eta, |x(t) - x(\tau)| \leqslant \eta
\]
для всех $$t$$ таких, что $$|t-\tau|<\gamma$$, и всех $$k<k_0$$. Отсюда и из $$\ref{4}$$ при $$\delta = \delta_k, k > k_0, |t-\tau|<\gamma<\eta$$ имеем:
\[
t^\delta \subset \tau^{2\eta}, (x_k(t))^\delta \subset (x(t))^{3\eta} \Rightarrow F((x_k(t))^\delta, t^\delta) \subset a^\epsilon
\]
Поскольку функция $$x_k$$ является $$\delta_k$$-решением, а множество $$A$$ выпукло, то для почти всех $$t$$ выполняется
\[
\dot{x_k}(t) \in (convF(x_k(t)^{\delta},t^{\delta}))^{\delta} \subset (convA^\epsilon)^\delta \subset A^{2\epsilon}.
\]
Поэтому в силу леммы 2 на множестве $$\{t:|t-\tau|<\gamma\}$$ функция $$x(\cdot)$$ абсолютно непрерывна и для почти всех $$t$$ из этого множества $$\dot{x}(t) \in A^{2\epsilon}$$.

Таким образом, доказано, что для любого $$\tau$$ из отрезка $$[a,b]$$ существует такой интервал, содержащий содержащий точку $$\tau$$, что на пересечении отрезка $$[a,b]$$ с этим интервалом функция $$x(\cdot)$$ абсолютно непрерывна. Выбирая из этого покрытия отрезка $$[a,b]$$ открытыми интервалами конечное подпокрытие, получаем, что функция $$x(\cdot)$$ абсолютно непрерывна на $$[a,b]$$. Кроме того, доказано, что для любого $$\tau \in (a,b)$$, при котором функция $$x(\cdot)$$ дифференцируема в точке $$\tau$$, имеет место $$\dot{x}(\tau) \in F(x(\tau),\tau)^{2\epsilon}$$ для произвольного $$\epsilon > 0$$. Переходя в этом дифференциальном включении к пределу при $$\epsilon \to 0$$, в силу замкнутости множества $$F(x(\tau), \tau)$$ получаем, что $$\dot{x}(\tau) \in F(x(\tau), \tau)$$. Таким образом, $$x(\cdot)$$ является решением $$\ref{1}$$.

== Доказательство теоремы 1 ==
Проведем доказательство методом ломаных Эйлера. Для $$k = 1,2,...$$ положим:
\[
h_k = \frac{d}{k}, t_{k,i} = t_0 + ih_k, i = 0,1,...,k.
\]
Построим ломаную $$x_k(t)$$. Положим $$x_k(t_{k,0}) = x_0$$. Если для некоторого $$i$$ значение $$x_k(t_{k,i})$$ уже определено и
\begin{equation}
\label{5}
|x_k(t_{k,i}) - x_0| \leqslant m|t_{k,i} - t_0|,
\end{equation}
то при $$t \in (t_{k,i}, t_{k,i+1}]$$ определим $$x_k(t)$$ по формуле
\begin{equation}
\label{6}
x_k(t) = x_k(t_{k,i}) + (t - t_{k,i})v_{k,i},
\end{equation}
взяв любое $$v_{k,i} \in F(x_k(t_{k,i}), t_{k,i}).$$

Поскольку в силу $$\ref{5} (x_k(t_{k,i}),t_{k,i}) \in Z$$, то $$|v_{k,i}| \leqslant m$$, и из $$\ref{5}, \ref{6}$$ имеем
\begin{equation}
\label{7}
|x_k(t) - x_0| \leqslant |x_k(t) - x_k(t_{k,i})| + |x_k(t_{k,i}) - x_0| \leqslant m|t-t_0| ~\forall t \in (t_{k,i},t_{k,i+1}].
\end{equation}
При этом справедливо неравенство, полученное из $$\ref{5}$$ заменой $$i$$ на $$i+1$$.
Таким образом, ломаная $$x_k$$ последовательно строится на отрезках $$[t_{k,i}, t_{k,i+1}]$$ при $$i = 0,1,...,k-1$$. В силу $$\ref{7} (x_k(t),t) \in Z ~\forall t \in [t_0,t_0+d]$$. В силу $$\ref{6}$$ функция $$x_k$$ абсолютно непрерывна и $$|\dot{x_k}(t) \leqslant m| ~\forall t \neq t_{k,i}$$. Поскольку
\begin{equation}
\dot{x_k}(t) = v_{k,i} \in F(x_k(t_{k,i}),t_{k,i}), |x_k(t) - x_k(t_{k,i})| \leqslant mh_k ~\forall t \in [x_k(t_{k,i}), x_k(t_{k,i}) + h_k],
\end{equation}
то $$x_k$$ является $$\sigma_k$$-решением включения $$\ref{2}$$ при $$\sigma_k = h_kmax\{1,m\}$$, причем $$\sigma_k \to 0, k \to \infty$$.

В силу $$\ref{7}$$ последовательность функций $$\{x_k\}$$ равномерно ограничена, а в силу оценки $$|\dot{x_k}| \leqslant m$$ она равностепенно непрерывна. Поэтому по теореме Арцела из этой последовательности можно выбрать равномерно сходящуюся подпоследовательность. По лемме 3 ее предел $$x(\cdot)$$ является решением $$\ref{1}$$. Из того, что $$x_k(t_0) = x_0$$ при всех $$k$$^ имеем $$x(t_0) = x_0$$.

Теорема доказана.
== Список литературы ==
1) Арутюнов А. В. "Лекции по выпуклому и многозначному анализу", М.: ФИЗМАТЛИТ, 2014.