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

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

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

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

Пусть $$(X, \rho) - $$ метрическое пространство. Тогда множество $$K \subset X$$ называется компактом, если из любой последовательности элементов из $$K$$ можно выделить подпоследовательность, сходящуюся по метрике $$\rho$$ к какому-то элементу из $$K$$.

Субградиентом функции $$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)$$.

Заметим, что функция $$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, \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 \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$$

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

$$\text{int A} -$$ внутренность множества$$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$$). Оно выпукло, замкнуто, и $$(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$$

Лемма 1. Пусть $$f -$$ собственная выпуклая функция и $$x \in \text{int}(\text{dom }f)$$. Тогда существует $$c > 0$$ такое, что \[ |f'(x,y)| \leqslant c|y|~~\forall y. \]

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

По теореме о липшицевости выпуклой функции существует такая окрестность $$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)$$.

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

По теореме 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$$

Лемма 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 -$$ произвольное нормированное пространство, а заданная на нем выпуклая функция $$f$$ конечна в точке $$x_0$$, принадлежащей границе эффективного множества $$\text{dom }f$$, и, кроме того, внутренность эффективного множества $$\text{int(dom }f)$$ непуста. Тогда в этой точке субдифференциал $$\partial f(x_0)$$ либо пуст, либо содержит бесконечно много точек.

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

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

Лемма 6. Для любых функций $$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_1(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$$

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

Теорема 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