Теория двойственности Фенхеля-Моро: различия между версиями

Материал из sawiki
Перейти к навигации Перейти к поиску
Строка 15: Строка 15:
 
называемые соответственно '''надграфиком функции''' $$f$$ и ее '''эффективным множеством'''.
 
называемые соответственно '''надграфиком функции''' $$f$$ и ее '''эффективным множеством'''.
 
==== Определение 1 ====
 
==== Определение 1 ====
Функция $$f$$ называется '''собственной''', если $$\text{dom} \; f \neq \emptyset$$ и $$f(x) \gt -\infty$$ $$\forall x$$.
+
Функция $$f$$ называется '''собственной''', если $$\text{dom} \; f \neq \emptyset$$ и $$f(x) \gt -\infty \; \forall x$$.
 
==== Определение 2 ====
 
==== Определение 2 ====
 
Функция $$f$$ называется '''выпуклой''', если ее надграфик $$\text{epi} \; f$$ является выпуклым множеством.
 
Функция $$f$$ называется '''выпуклой''', если ее надграфик $$\text{epi} \; f$$ является выпуклым множеством.
Строка 73: Строка 73:
 
\beta f^{**}(x_0) + \left\langle y^*,x_0 \right\rangle \gt \underset{(y,\alpha) \in \text{epi} f}{\text{sup}}\left( \beta\alpha + \left\langle y^*,y \right\rangle \right). \;\;\; (♦)
 
\beta f^{**}(x_0) + \left\langle y^*,x_0 \right\rangle \gt \underset{(y,\alpha) \in \text{epi} f}{\text{sup}}\left( \beta\alpha + \left\langle y^*,y \right\rangle \right). \;\;\; (♦)
 
\]
 
\]
Докажем, что $$\beta \lt 0$$. Действительно, случай $$\beta \gt 0$$ невозможен, что обосновывается так же, как и при доказательстве вспомогательной леммы, с учетом того, что $$\text{dom} \: f \neq \emptyset$$. Пусть теперь $$\beta = 0$$. Тогда $$\gamma = \left\langle y^*, x_0 \right\rangle - \underset{y \in \text{dom} f}{\text{sup}} \left\langle y^*, y \right\rangle \gt 0$$. В силу леммы функция $$f^*$$ является собственной. Поэтому существует $$y^*_1 \in \text{dom} \: f^* \neq \emptyset$$. Для $$t \gt 0$$ имеем
+
Докажем, что $$\beta \lt 0$$. Действительно, случай $$\beta \gt 0$$ невозможен, что обосновывается так же, как и при доказательстве вспомогательной леммы, с учетом того, что $$\text{dom} \: f \neq \emptyset$$.
 +
<br>
 +
Пусть теперь $$\beta = 0$$. Тогда  
 +
\[
 +
\gamma = \left\langle y^*, x_0 \right\rangle - \underset{y \in \text{dom} f}{\text{sup}} \left\langle y^*, y \right\rangle \gt 0.
 +
\]
 +
В силу леммы функция $$f^*$$ является собственной. Поэтому существует $$y^*_1 \in \text{dom} \: f^* \neq \emptyset$$. Для $$t \gt 0$$ имеем
 
\[
 
\[
(заполнить).
+
f^*(y^*_1+ty^*) = \underset{y \in \text{dom} f}{\text{sup}} \left( \left\langle y^*_1 + ty^*, y \right\rangle - f(y) \right) \le \underset{y \in \text{dom} f}{\text{sup}} \left( \left\langle y^*_1, y \right\rangle - f(y) \right) + t \underset{y \in \text{dom} f}{\text{sup}} \left\langle y^*, y \right\rangle = f^*(y^*_1) + t \underset{y \in \text{dom} f}{\text{sup}} \left\langle y^*, y \right\rangle.
 
\]
 
\]
 
Отсюда в силу неравенства Юнга-Фенхеля для функции $$f^*$$ вытекает
 
Отсюда в силу неравенства Юнга-Фенхеля для функции $$f^*$$ вытекает
 
\[
 
\[
(заполнить).
+
f^{**}(x_0) \ge \left\langle y^*_1 + ty^*, x_0 \right\rangle - f^*(y^*_1 + ty^*) \ge \left\langle y^*_1, x_0 \right\rangle + t \left\langle y^*, x_0 \right\rangle - f^*(y^*_1) - t \underset{y \in \text{dom} f}{\text{sup}} \left\langle y^*, y \right\rangle = \left\langle y^*_1, x_0 \right\rangle - f^*(y^*_1) + t\gamma, \;\forall t\gt 0.
 
\]
 
\]
 
Получили противоречие, так как $$\gamma \gt 0$$  и, значит, при больших $$t$$ значение $$t\gamma$$ может быть сделано как угодно большим и, следовательно, при достаточно больших $$t \gt 0$$ последнее неравенство выполняться не может.
 
Получили противоречие, так как $$\gamma \gt 0$$  и, значит, при больших $$t$$ значение $$t\gamma$$ может быть сделано как угодно большим и, следовательно, при достаточно больших $$t \gt 0$$ последнее неравенство выполняться не может.
Строка 85: Строка 91:
 
Таким образом, доказано, что $$\beta \lt 0$$; значит, не теряя общности рассуждений, будем считать, что $$\beta = -1$$. В силу неравенства $$(♦)$$ имеем
 
Таким образом, доказано, что $$\beta \lt 0$$; значит, не теряя общности рассуждений, будем считать, что $$\beta = -1$$. В силу неравенства $$(♦)$$ имеем
 
\[
 
\[
(заполнить),
+
-f^{**}(x_0) + \left\langle y^*, x_0 \right\rangle \gt \underset{y \in \text{dom} f}{\text{sup}} \left( -f(y) + \left\langle y^*,y \right\rangle\right) = f^*(y^*),
 +
\]
 +
откуда
 +
\[
 +
\left\langle y^*, x_0 \right\rangle \gt f^*(y^*) + f^{**}(x_0),
 
\]
 
\]
откуда $$\left\langle y^*, x_0 \right\rangle \gt f^*(y^*) + f^{**}(x_0)$$, что противоречит неравенству Юнга–Фенхеля для функции $$f^∗$$. Полученное противоречие доказывает, что $$f^{**} \ge f$$ и, значит, $$f^{∗∗} = f$$. $$\;\;$$ ∎
+
что противоречит неравенству Юнга–Фенхеля для функции $$f^∗$$. Полученное противоречие доказывает, что $$f^{**} \ge f$$ и, значит, $$f^{∗∗} = f$$. $$\;\;$$ ∎
 
== Список литературы ==
 
== Список литературы ==
 
# Арутюнов А. В. "Лекции по выпуклому и многозначному анализу", М.: ФИЗМАТЛИТ, 2014.
 
# Арутюнов А. В. "Лекции по выпуклому и многозначному анализу", М.: ФИЗМАТЛИТ, 2014.

Версия 00:03, 5 декабря 2022

Определения

Пусть $$X$$ — вещественное линейное пространство.
Через $$\overline{\mathbb{R}}$$ будем обозначать расширенную вещественную прямую, $$\overline{\mathbb{R}} = \mathbb{R} \cup \left\{ -\infty; +\infty \right\}$$.
Будем рассматривать функции $$f: X \to \overline{\mathbb{R}}$$.
С каждой такой функцией $$f$$ можно связать множества \[ \text{epi} \; f = \left\{ \left( x,\alpha \right) \in X\times \mathbb{R} : f(x) \le \alpha\right\}, \] \[ \text{dom} \; f = \left\{ x \in X : f(x) \lt +\infty \right\}, \] называемые соответственно надграфиком функции $$f$$ и ее эффективным множеством.

Определение 1

Функция $$f$$ называется собственной, если $$\text{dom} \; f \neq \emptyset$$ и $$f(x) \gt -\infty \; \forall x$$.

Определение 2

Функция $$f$$ называется выпуклой, если ее надграфик $$\text{epi} \; f$$ является выпуклым множеством.

Определение 3

Функция $$f$$ называется замкнутой, если ее надграфик $$\text{epi} \; f$$ замкнут.

Далее предполагаем, что $$X$$ — гильбертово пространство.

Определение 4

Функцией, сопряженной к $$f$$, называется функция, определенная формулой $$f^*(x^*) = \underset{x \in X}{\text{sup}}\left( \left\langle x^*,x \right\rangle - f(x) \right)$$.

Из определения сопряженной функции вытекает неравенство Юнга-Фенхеля \[ f^*(x^*) + f(x) \ge \left\langle x, x^* \right\rangle \; \forall x,x^* \in X. \] Вторая сопряженная функция $$f^{**}$$ определяется по формуле $$f^{**}=(f^*)^*$$.

Теорема Фенхеля-Моро

Пусть функция $$f$$ — выпуклая, замкнутая, собственная. Тогда $$f^{**} = f$$.

Вспомогательная лемма

Пусть функция $$f$$ — выпуклая, замкнутая, собственная. Тогда $$f^*$$ — также собственная функция.

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

Докажем, что $$f^∗(x^∗) \gt -\infty$$ $$\forall x^∗ \in X$$. Возьмем $$x_0 \in \text{dom}$$ $$f \neq \emptyset$$. Тогда $$f^∗(x^∗) \ge \left\langle x_0, x∗\right\rangle − f(x_0) \gt -\infty$$, так как $$f(x_0) \lt +\infty$$.
Остается доказать существование вектора $$y^∗ \in X$$, для которого $$f^∗(y^∗) \lt +\infty$$.
Очевидно, точка $$(x_0, f(x_0) − 1)$$ не принадлежит замкнутому выпуклому множеству $$\text{epi}$$ $$f$$. Следовательно, по теореме об отделимости ее можно строго отделить от выпуклого замкнутого множества $$\text{epi}$$ $$f$$. Поэтому существуют $$y^∗ \in X$$ и $$\beta \in \mathbb{R}$$ такие, что \[ \underset{(x,\alpha) \in \text{epi} f}{\text{sup}}\left\{ \beta\alpha + \left\langle y^*,x \right\rangle \right\} \lt \beta (f(x_0) - 1) + \left\langle y^*, x_0 \right\rangle. \;\;\; (*) \] Докажем, что $$\beta \lt 0$$. Действительно, предположим обратное. Случай $$\beta \gt 0$$ невозможен, так как $$(x_0, \alpha) \in \text{epi}$$ $$f\;$$ $$\forall \alpha \ge f(x_0) \neq +\infty$$ и, значит, при $$\beta \gt 0$$ имеет место $$\underset{(x_0,\alpha) \in \text{epi} f}{\text{sup}}\beta \alpha = +\infty$$, что противоречит неравенству $$(*)$$.
Пусть теперь $$\beta = 0$$. Тогда \[ \underset{(x,\alpha) \in \text{epi} f}{\text{sup}} \left\langle y^*, x \right\rangle \lt \left\langle y^*, x_0 \right\rangle, \] хотя \[ (x_0, f(x_0)) \in \text{epi} f \implies \underset{(x,\alpha) \in \text{epi} f}{\text{sup}} \left\langle y^*, x \right\rangle \ge \left\langle y^*, x_0 \right\rangle. \] Полученное противоречие доказывает, что $$\beta \lt 0$$. Поэтому, в силу положительной однородности неравенства $$(*)$$ по переменной $$(y^∗, \beta)$$, не теряя общности, будем считать, что $$\beta = -1$$.
В силу $$(*)$$ имеем \[ f^*(y^*) = \underset{x}{\text{sup}} \left\{ -f(x) + \left\langle y^*,x \right\rangle \right\} = \underset{(x,\alpha) \in \text{epi} f}{\text{sup}} \left\{ -\alpha + \left\langle y^*,x \right\rangle \right\} \lt -(f(x_0) - 1) + \left\langle y^*, x_0 \right\rangle \implies f^*(y^*) \lt +\infty. \] Значит, функция $$f^*$$ является собственной.$$\;\;$$ ∎

Доказательство теоремы Фенхеля-Моро

Покажем, что $$f^{**} \le f$$. В силу неравенства Юнга-Фенхеля $$\forall x \in X$$ имеем \[ f(x) \ge \left\langle x, x^* \right\rangle - f^*(x^*) \; \forall x^* \in X \implies f(x) \ge \underset{x^*}{\text{sup}}\left\{ \left\langle x, x^* \right\rangle - f^*(x^*) \right\} = f^{**}(x). \] Остается показать, что $$f^{**} \ge f$$. Предположим противное. Тогда существует $$x_0 \in X$$, для которого $$f^{∗∗}(x_0) \lt f(x_0)$$. Поэтому точка $$(x_0, f^{∗∗}(x_0))$$ строго отделима от выпуклого замкнутого множества $$\text{epi} \: f$$. Значит, существуют $$y^∗ \in X$$ и $$\beta \in \mathbb{R}$$ такие, что \[ \beta f^{**}(x_0) + \left\langle y^*,x_0 \right\rangle \gt \underset{(y,\alpha) \in \text{epi} f}{\text{sup}}\left( \beta\alpha + \left\langle y^*,y \right\rangle \right). \;\;\; (♦) \] Докажем, что $$\beta \lt 0$$. Действительно, случай $$\beta \gt 0$$ невозможен, что обосновывается так же, как и при доказательстве вспомогательной леммы, с учетом того, что $$\text{dom} \: f \neq \emptyset$$.
Пусть теперь $$\beta = 0$$. Тогда \[ \gamma = \left\langle y^*, x_0 \right\rangle - \underset{y \in \text{dom} f}{\text{sup}} \left\langle y^*, y \right\rangle \gt 0. \] В силу леммы функция $$f^*$$ является собственной. Поэтому существует $$y^*_1 \in \text{dom} \: f^* \neq \emptyset$$. Для $$t \gt 0$$ имеем \[ f^*(y^*_1+ty^*) = \underset{y \in \text{dom} f}{\text{sup}} \left( \left\langle y^*_1 + ty^*, y \right\rangle - f(y) \right) \le \underset{y \in \text{dom} f}{\text{sup}} \left( \left\langle y^*_1, y \right\rangle - f(y) \right) + t \underset{y \in \text{dom} f}{\text{sup}} \left\langle y^*, y \right\rangle = f^*(y^*_1) + t \underset{y \in \text{dom} f}{\text{sup}} \left\langle y^*, y \right\rangle. \] Отсюда в силу неравенства Юнга-Фенхеля для функции $$f^*$$ вытекает \[ f^{**}(x_0) \ge \left\langle y^*_1 + ty^*, x_0 \right\rangle - f^*(y^*_1 + ty^*) \ge \left\langle y^*_1, x_0 \right\rangle + t \left\langle y^*, x_0 \right\rangle - f^*(y^*_1) - t \underset{y \in \text{dom} f}{\text{sup}} \left\langle y^*, y \right\rangle = \left\langle y^*_1, x_0 \right\rangle - f^*(y^*_1) + t\gamma, \;\forall t\gt 0. \] Получили противоречие, так как $$\gamma \gt 0$$ и, значит, при больших $$t$$ значение $$t\gamma$$ может быть сделано как угодно большим и, следовательно, при достаточно больших $$t \gt 0$$ последнее неравенство выполняться не может.
Таким образом, доказано, что $$\beta \lt 0$$; значит, не теряя общности рассуждений, будем считать, что $$\beta = -1$$. В силу неравенства $$(♦)$$ имеем \[ -f^{**}(x_0) + \left\langle y^*, x_0 \right\rangle \gt \underset{y \in \text{dom} f}{\text{sup}} \left( -f(y) + \left\langle y^*,y \right\rangle\right) = f^*(y^*), \] откуда \[ \left\langle y^*, x_0 \right\rangle \gt f^*(y^*) + f^{**}(x_0), \] что противоречит неравенству Юнга–Фенхеля для функции $$f^∗$$. Полученное противоречие доказывает, что $$f^{**} \ge f$$ и, значит, $$f^{∗∗} = f$$. $$\;\;$$ ∎

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

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