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

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

Определение

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

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

Свойства

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

$$\text{int A} -$$ внутренность множества$$A -$$ множество всех внутренних точек множества $$A$$,

$$\text{dom f} = \{x \in X: f(x) < +\infty\} -$$ эффективное множество функции $$f$$.

Доказательство. Вначале докажем, что $$\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_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$$

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

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

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

Список литературы

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