Субдифференциалы выпуклых функций: различия между версиями

Материал из sawiki
Перейти к навигации Перейти к поиску
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
  
 
__TOC__
 
__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 = \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$$ называется ''собственной'', если dom $$f \neq \varnothing$$ и $$f(x) > -\infty~~\forall x$$, где $$\text{dom f} = \{x \in X: f(x) < +\infty\} -$$ эффективное множество функции $$f$$.
 
Пусть $$(X, \rho) - $$ [https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%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 метрическое пространство]. Тогда множество $$K \subset X$$ называется ''компактом'', если из любой последовательности элементов из $$K$$ можно выделить подпоследовательность, [http://mathemlib.ru/books/item/f00/s00/z0000017/st013.shtml сходящуюся по метрике] $$\rho$$ к какому-то элементу из $$K$$.
 
  
 
''Субградиентом функции $$f$$ в точке $$x$$'' называется вектор $$x^* \in X$$ такой, что $$f(y) \geqslant f(x) + \langle x^*,y - x \rangle~~\forall y \in X$$. Это неравенство называется субградиентным неравенством.
 
''Субградиентом функции $$f$$ в точке $$x$$'' называется вектор $$x^* \in X$$ такой, что $$f(y) \geqslant f(x) + \langle x^*,y - x \rangle~~\forall y \in X$$. Это неравенство называется субградиентным неравенством.
Строка 13: Строка 21:
 
== Определение субдифференциала==
 
== Определение субдифференциала==
  
''Субдифференциалом функции $$f$$ в точке $$x$$'' называется множество всех субградиентов функции $$f$$ в этой точке. Субдифференциал обозначается $$\partial f(x)$$.
+
''Субдифференциалом функции $$f$$ в точке $$x$$'' называется множество всех субградиентов функции $$f$$ в этой точке. Субдифференциал обозначается $$\partial f(x)$$.
 +
 
 +
Например, на графике выше $$\partial f(0) = [-1,1]$$.
  
 
Заметим, что функция $$f$$ достигает в точке $$x$$ минимума тогда и только тогда, когда $$0 \in \partial f(x)$$.
 
Заметим, что функция $$f$$ достигает в точке $$x$$ минимума тогда и только тогда, когда $$0 \in \partial f(x)$$.
  
==  Свойства ==
+
==  Вспомогательные утверждения ==
 
'''Теорема 1.'''
 
'''Теорема 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$$ [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) = \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,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.
 
f'(x,0) = 0, -f'(x, -y) \leqslant f'(x,y)~~\forall y.
Строка 30: Строка 40:
 
'''Доказательство:'''
 
'''Доказательство:'''
  
Для удобства будем считать, что $$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).$$
+
Для удобства будем считать, что $$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$$ по определению.  
 
Пусть дано $$\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$$ по определению.  
Строка 46: Строка 56:
  
 
Значит, функция $$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$$
 
Значит, функция $$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$$
 
'''Теорема 2.'''
 
Пусть $$f -$$ выпуклая собственная функция и $$x \in \text{int}(\text{dom }f)$$. Тогда субдифференциал $$\partial f(x)$$ в точке $$x$$ является непустым компактом.
 
 
$$\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$$,
 
 
'''Доказательство:'''
 
 
Вначале докажем, что $$\partial f(x) \neq \varnothing.$$ Рассмотрим множество $$\text{cl epi }f (\text{cl }A -$$ замыкание множества $$A$$; $$\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$$
 
  
 
'''Лемма 1.'''
 
'''Лемма 1.'''
 
Пусть $$f -$$ собственная выпуклая функция и $$x \in \text{int}(\text{dom }f)$$. Тогда существует $$c > 0$$ такое, что  
 
Пусть $$f -$$ собственная выпуклая функция и $$x \in \text{int}(\text{dom }f)$$. Тогда существует $$c > 0$$ такое, что  
 
\[
 
\[
|f'(x,y)| \leqslant c|y|~~\forall y.
+
|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$$.
  
 
'''Доказательство:'''
 
'''Доказательство:'''
Строка 110: Строка 93:
  
 
'''Лемма 3.'''
 
'''Лемма 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)$$.
+
Пусть функция $$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$$
+
По теореме 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$$ конечна в точке $$x_0$$, принадлежащей границе эффективного множества $$\text{dom }f$$. Тогда в этой точке субдифференциал $$\partial f(x_0)$$ либо пуст, либо содержит бесконечно много точек.
+
'''Лемма 4.'''
 +
Для любых функций $$f_1,...,f_k$$ имеет место
 +
\[
 +
\partial (f_1+...+f_k)(x) \supseteq \partial f_1(x) +...+ \partial f_k(x)~~\forall x \in X.
 +
\]
  
 
'''Доказательство:'''
 
'''Доказательство:'''
  
В силу выпуклости субдифференциала $$\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$$.
+
Пусть $$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$$
  
В силу сказанного выше $$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)$$ либо пуст, либо содержит бесконечно много точек.
+
'''Теорема 2.'''
 +
Пусть $$f -$$ выпуклая собственная функция и $$x \in \text{int}(\text{dom }f)$$. Тогда субдифференциал $$\partial f(x)$$ в точке $$x$$ является непустым компактом.
  
 
'''Доказательство:'''
 
'''Доказательство:'''
  
Доказательство этой леммы аналогично доказательству предыдущей, но вместо теоремы о конечномерной отделимости следует использовать теорему отделимости. $$\blacksquare$$
+
Вначале докажем, что $$\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)$$.
  
'''Лемма 6.'''
+
Осталось доказать выпуклость множества $$\partial f(x)$$. Пусть $$x_1^*, x_2^* \in \partial f(x), \alpha \geqslant 0, \beta \geqslant 0, \alpha + \beta = 1$$. Тогда:
Для любых функций $$f_1,...,f_k$$ имеет место
 
 
\[
 
\[
\partial(f_1 +...+ f_k)(x) \supseteq \partial f_1(x) +...+ \partial f_k(x)~~\forall x \in X.
+
  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)$$ либо пуст, либо содержит бесконечно много точек.
  
 
'''Доказательство:'''
 
'''Доказательство:'''
  
Пусть $$x^* \in \partial f_1(x) +...+ \partial f_k(x)$$. Тогда $$x^* = x^*_1 +...+x^*_k$$, где $$x_i^* \in \partial f_i(x)$$. Поэтому
+
В силу выпуклости субдифференциала $$\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$$.
\[
+
 
f_1(y) \geqslant f_1(x) + \langle x_1^*, y - x \rangle,..., f_1(y) \geqslant f_k(x) + \langle x_k^*, y - x \rangle~~\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$$
\]
+
 
Складывая при каждом фиксированном $$y$$ все эти неравенства, получаем, что $$x^* \in \partial(f_1 +...+ f_k)(x).$$ $$\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==
 
==Пример к теореме 2==
Строка 155: Строка 167:
 
Эта функция субдифференцируема (и даже дифференцируема) во всех точках $$x \in \text{int}(\text{dom }f) = (-1,1)$$. Однако в точках $$x = 1, -1$$, составляющих границу $$\text{dom }f$$, ее субдифференциал пуст.
 
Эта функция субдифференцируема (и даже дифференцируема) во всех точках $$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$$
 +
 
 +
==Критерий дифференцируемости==  
  
'''Теорема 3.'''
+
'''Теорема 4.'''
 
Пусть выпуклая функция $$f$$ конечна в точке $$x_0$$. Если $$f$$ дифференцируема в точке $$x_0$$, то субдифференциал $$\partial f(x_0)$$ содержит единственный элемент $$f'(x_0)$$ и, в частности,  
 
Пусть выпуклая функция $$f$$ конечна в точке $$x_0$$. Если $$f$$ дифференцируема в точке $$x_0$$, то субдифференциал $$\partial f(x_0)$$ содержит единственный элемент $$f'(x_0)$$ и, в частности,  
 
\[
 
\[
Строка 176: Строка 254:
 
Но если линейный функционал неотрицателен на всем пространстве, то он равен нулю и, следовательно, $$x^* = f'(x_0)~~\forall x^* \in \partial f(x_0)$$, т.е. субдифференциал $$\partial f(x_0)$$ состоит из единственной точки $$f'(x_0)$$.
 
Но если линейный функционал неотрицателен на всем пространстве, то он равен нулю и, следовательно, $$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$$.
+
Пусть теперь $$\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$$. Следовательно,  
 
Итак, $$0 \in \text{int}(\text{dom }h)$$, а $$h -$$ собственная выпуклая функция. Поэтому в силу леммы 1 выпуклая функция $$h'(0,\cdot)$$ принимает лишь конечные значения и, следовательно, она непрерывна на $$\mathbb{R}^n$$. Поэтому в силу доказанного выше $$h'(0,y) \equiv 0$$. Следовательно,  

Текущая версия на 00:21, 13 декабря 2022

$$f(x) = |x|$$

Пусть $$X = \mathbb{R}^n$$ и $$f -$$ собственная выпуклая функция

На графике приведен пример выпуклой функции, которая недифференцируема в точке $$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$$ выпукла и конечна в точке $$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)$$ выпукла, положительно однородна и \[ 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} -$$ внутренность множества$$A -$$ множество всех внутренних точек множества $$A$$.

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

По теореме о липшицевости выпуклой функции существует такая окрестность $$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 опорной функцией множества $$\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$$). Оно выпукло, замкнуто, и $$(x, f(x)) \notin \text{int}(\text{cl epi }f).$$ Здесь несложно показать, что последнее утверждение вытекает из непрерывности на $$\text{int}(\text{dom }f)$$ определенной на $$\mathbb{R}^n$$ выпуклой собственной функции. Поэтому по теореме отделимости существуют $$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 -$$ произвольное нормированное пространство, а заданная на нем выпуклая функция $$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