sawiki - Вклад участника [ru]

Теория двойственности Фенхеля-Моро

2022-12-30T14:10:18Z

Nazim22:

== Определения ==
Пусть $$X$$ — [https://ru.wikipedia.org/wiki/Гильбертово_пространство гильбертово] пространство.
 
Через $$\overline{\mathbb{R}}$$ будем обозначать расширенную вещественную прямую, $$\overline{\mathbb{R}} = \mathbb{R} \cup \left\{ -\infty; +\infty \right\}$$.
 
Будем рассматривать функции $$f: X \to \overline{\mathbb{R}}$$.
 
'''Определение 1.'''
''Надграфиком'' функции $$f$$ называется множество
\[
\text{epi} \, f = \left\{ \left( x,\alpha \right) \in X\times \mathbb{R} : f(x) \leqslant \alpha\right\}.
\]
 
'''Определение 2.'''
''Эффективным множеством'' функции $$f$$ называется множество
\[
\text{dom} \, f = \left\{ x \in X : f(x) \lt +\infty \right\}.
\]
 
'''Определение 3.'''
Функция $$f$$ называется ''собственной'', если $$\text{dom} \, f \neq \varnothing$$ и $$f(x) \gt -\infty \; \forall x$$.
 
'''Определение 4.'''
Функция $$f$$ называется ''[https://sawiki.cs.msu.ru/index.php?title=Выпуклая_функция_и_ее_свойства&action=edit&redlink=1 выпуклой]'', если ее надграфик $$\text{epi} \, f$$ является выпуклым множеством.
 
'''Определение 5.'''
Функция $$f$$ называется ''замкнутой'', если ее надграфик $$\text{epi} \, f$$ замкнут.
== Сопряженная функция ==
'''Определение.'''
Функцией, ''сопряженной'' к $$f$$, называется функция, определенная формулой
\[
f^*(x^*) = \underset{x \in X}{\text{sup}}\left( \left\langle x^*,x \right\rangle - f(x) \right),
\]
где $$x^*$$ — обозначение для аргумента сопряженной функции.
 
Из определения сопряженной функции вытекает '''неравенство Юнга-Фенхеля'''
\[
f^*(x^*) + f(x) \geqslant \left\langle x, x^* \right\rangle \; \forall x,x^* \in X.
\]
''Вторая сопряженная'' функция $$f^{**}$$ определяется по формуле $$f^{**}=(f^*)^*$$.
 
'''Пример 1.'''
Для аффинной функции $$f(x) = \left\langle a,x \right\rangle + b$$ сопряженная функция вычисляется по формуле
\[
f^*(x^*) =
\begin{cases}
-b, &x^* = a;\\
+\infty, &x^* \neq a.
\end{cases}
\]
 
'''Пример 2.'''
Для произвольной выпуклой функции $$f$$ умножение на положительный скаляр $$\lambda \gt 0$$ определяется соотношением
\[
\left( \lambda f \right)(x) = \lambda f(x), \; \forall x \in X.
\]
Непосредственно вычисляется, что
\[
\left( \lambda f \right)^*(x^*) \equiv \lambda f^*(x^*/\lambda), \; x^* \in X.
\]
'''Пример 3.'''
Пусть $$M$$ — [https://ru.wikipedia.org/wiki/Евклидово_пространство евклидово] пространство, и пусть $$f: M \to \mathbb{R}$$ — функция $$f(x) = \left\langle a,x \right\rangle$$, где $$a \in M$$. Поскольку
\[
\underset{x\in M}{\text{sup}}\left\{ \left\langle s,x \right\rangle - \left\langle a,x \right\rangle \right\} = \underset{x\in M}{\text{sup}} \left\langle s-a,x \right\rangle =
\begin{cases}
0, &s = a;\\
+\infty, &s \neq a.
\end{cases}
\]
для всех $$s \in M$$, то сопряженная функция $$f^*$$ — [https://ru.wikipedia.org/wiki/Индикатор_(математика) индикаторная функция] $$\delta_\left\{ a \right\}$$ одноэлементного множества $$\left\{ a \right\}$$.
== Вспомогательная лемма ==
'''Лемма.'''
Пусть функция $$f$$ — выпуклая, замкнутая, собственная. Тогда $$f^*$$ — также собственная функция.
==== Доказательство ====
Докажем, что $$f^∗(x^∗) \gt -\infty$$ $$\forall x^∗ \in X$$. Возьмем $$x_0 \in \text{dom} \, f \neq \varnothing$$. Тогда $$f^∗(x^∗) \geqslant \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$$. Следовательно, по [https://sawiki.cs.msu.ru/index.php?title=Отделимость_множеств&action=edit&redlink=1 теореме об отделимости] ее можно строго отделить от выпуклого замкнутого множества $$\text{epi} \, f$$. Поэтому существуют $$y^∗ \in X$$ и $$\beta \in \mathbb{R}$$ такие, что
\begin{equation}
\label{1}
\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.
\end{equation}
Докажем, что $$\beta \lt 0$$. Действительно, предположим обратное. Случай $$\beta \gt 0$$ невозможен, так как $$(x_0, \alpha) \in \text{epi} \, f\;$$ $$\forall \alpha
\geqslant f(x_0) \neq +\infty$$ и, значит, при $$\beta \gt 0$$ имеет место $$\underset{(x_0,\alpha) \in \text{epi} \, f}{\text{sup}}\beta \alpha = +\infty$$, что противоречит неравенству ($$\ref{1}$$).
 
Пусть теперь $$\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 \geqslant \left\langle y^*, x_0 \right\rangle.
\]
Полученное противоречие доказывает, что $$\beta \lt 0$$. Поэтому, в силу положительной однородности неравенства ($$\ref{1}$$) по переменной $$(y^∗, \beta)$$,
не теряя общности, будем считать, что $$\beta = -1$$.
 
В силу ($$\ref{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^*$$ является собственной.$$\;\;\blacksquare$$
== Теорема Фенхеля-Моро ==
'''Теорема.'''
Пусть функция $$f$$ — выпуклая, замкнутая, собственная. Тогда $$f^{**} = f$$.
==== Доказательство ====
Покажем, что $$f^{**} \leqslant f$$. В силу неравенства Юнга-Фенхеля $$\forall x \in X$$ имеем
\[
f(x) \geqslant \left\langle x, x^* \right\rangle - f^*(x^*) \; \forall x^* \in X \implies f(x) \geqslant \underset{x^*}{\text{sup}}\left\{ \left\langle x, x^* \right\rangle - f^*(x^*) \right\} = f^{**}(x).
\]
Остается показать, что $$f^{**} \geqslant 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}$$ такие, что
\begin{equation}
\label{2}
\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).
\end{equation}
Докажем, что $$\beta \lt 0$$. Действительно, случай $$\beta \gt 0$$ невозможен, что обосновывается так же, как и при доказательстве вспомогательной леммы, с учетом того, что $$\text{dom} \, f \neq \varnothing$$.
 
Пусть теперь $$\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 \varnothing$$. Для $$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) \leqslant \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) \geqslant \left\langle y^*_1 + ty^*, x_0 \right\rangle - f^*(y^*_1 + ty^*) \geqslant \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$$. В силу неравенства ($$\ref{2}$$) имеем
\[
-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^{**} \geqslant f$$ и, значит, $$f^{∗∗} = f$$. $$\;\;\blacksquare$$
== Приложения теории двойственности ==
=== Связь опорной и индикаторной функций множества ===
Определим [https://sawiki.cs.msu.ru/index.php/Опорная_функция_множества опорную функцию] множества $$A \subset X$$ на $$X$$ соотношением
\begin{equation}
\label{3}
\rho(x^*|A) = \underset{y \in A}{\text{sup}} \left\langle x^*, y \right\rangle, x^* \in X.
\end{equation}
Введем индикаторную функцию следующим образом
\[
\delta_A(x) =
\begin{cases}
0, &x \in A;\\
+\infty, &x \notin A.
\end{cases}
\]
'''Предложение 1.''' Пусть $$\delta_A(\cdot)$$ — индикаторная функция выпуклого замкнутого множества $$A$$. Тогда $$\rho^*(\cdot|A) = \delta_A(\cdot)$$.
 
'''Доказательство'''
 
Функция $$\delta_A$$ является выпуклой, замкнутой и собственной. Поэтому по теореме Фенхеля-Моро $$\delta_A^{**} = \delta_A$$. Кроме того, для произвольного $$x^*$$ имеем
\[
\delta_A^*(x^*) = \underset{x}{\text{sup}}\left\{ \left\langle x, x^* \right\rangle - \delta_A(x)\right\} = \underset{x \in A}{\text{sup}} \left\{ \left\langle x, x^* \right\rangle \right\} = \rho(x^*| A).
\]
Следовательно, $$\delta_A = \delta_A^{**} = \rho^*(\cdot|A)$$. $$\;\;\blacksquare$$
=== Евклидово расстояние от точки до множества ===
Для [https://translated.turbopages.org/proxy_u/en-ru.ru.a3199e6e-63adda8c-2d9f628d-74722d776562/https/en.wikipedia.org/wiki/Euclidean_metric#Properties евклидова расстояния]
$$d(x,ℳ) = \underset{y \in ℳ}{\text{min}} \left\| x -y \right\|$$ от точки $$x$$ до множества $$ℳ$$, $$ℳ \in \text{conv} \;\mathbb{R}^n$$ — выпуклый компакт, справедливы следующие соотношения двойственности
\[
d(x,ℳ) = \underset{\left\| l \right\| \leqslant 1}{\text{max}} \left\{ \left( l,x \right) - \rho\left( l|ℳ \right) \right\},
\]
\[
d^2(x,ℳ) = \underset{l}{\text{max}} \left\{ \left( l,x \right) - \rho\left( l|ℳ \right) - \frac{1}{4} \left( l,l \right) \right\},
\]
где $$\rho\left( l|ℳ \right)$$ — [https://sawiki.cs.msu.ru/index.php/Опорная_функция_множества опорная функция] множества $$ℳ$$.
 
Покажем справедливость второго соотношения.
 
Имеем функцию $$\varphi(x) = d^2(x,ℳ) = \underset{y \in ℳ}{\text{min}}\left( x-y, x-y \right)$$. Поскольку функция $$\varphi$$ является выпуклой, замкнутой и собственной, по теореме Фенхеля-Моро $$\varphi^{**} = \varphi$$.
 
Найдем сопряженную функцию к $$\varphi(x)$$
\[
\varphi^*(l) = \underset{x}{\text{sup}}\left\{ \left( l,x \right) - \varphi(x) \right\} = \underset{x}{\text{sup}}\;\underset{y \in ℳ}{\text{max}} \left\{ \left( l,x \right) - \left( x-y,x-y \right)\right\} = \underset{y \in ℳ}{\text{max}} \;\underset{x}{\text{sup}} \left\{ \left( l,x \right) - \left( x-y,x-y \right)\right\} = \underset{y \in ℳ}{\text{max}} \left(\left( l, \frac{l}{2} + y \right) - \frac{1}{4}\left( l,l \right)\right)= \rho\left( l|ℳ \right) + \frac{1}{4}\left( l,l \right),
\]
откуда, очевидно, следует второе соотношение. $$\;\;\blacksquare$$
=== Расстояние по Хаусдорфу между двумя компактами ===
Пусть $$X = \mathbb{R}^n$$, $$A$$ и $$B$$ — выпуклые компакты.
 
'''Лемма 1.'''
\[
h\left( A, B \right) = \underset{\left\| l \right\| \leqslant 1}{\text{max}}\left| \rho\left( l|A \right) - \rho\left( l|B \right)\right|,
\]
где $$h\left( A, B \right)$$ — [https://sawiki.cs.msu.ru/index.php/Метрика_Хаусдорфа расстояние по Хаусдорфу] между множествами $$A$$ и $$B$$.
 
'''Замечание 1.''' $$d\left( x, B \right) = h\left( x, B \right) = \underset{\left\| l \right\| \leqslant 1}{\text{max}}\left| \left( l,x \right) - \rho\left( l|B \right)\right|$$.
=== Опорная функция пересечения множеств ===
Приведем три вспомогательных утверждения без доказательства $$^{[1]}$$.
 
'''Лемма 2.''' Для любых функций $$f_1,{...},f_n$$ имеет место
\[
\left( f_1 \oplus f_2 \oplus {...} \oplus f_n \right)^* = f_1^* + f_2^* + {...} + f_n^*.
\]
'''Предложение 2.''' Пусть $$f$$ — выпуклая собственная функция и $$X = \mathbb{R}^n$$. Тогда ее [https://ru.wikipedia.org/wiki/Замыкание_(анализ) замыкание] $$\text{cl} \, f$$ также является собственной функцией.
 
'''Предложение 3.''' Для выпуклой функции $$f$$ имеет место
\[
(\text{cl} \, f)^* = f^*.
\]
 
Определим опорную функцию соотношением ($$\ref{3}$$).
 
'''Предложение 4.''' Пусть $$A, B$$ — выпуклые ограниченные подмножества $$\mathbb{R}^n$$ и $$\text{int} \, A \cap \text{int} \, B \neq \varnothing$$. Тогда
\[
\rho\left( \cdot | A\cap B \right) = \text{cl}\left( \rho\left( \cdot |A \right) \oplus \rho\left( \cdot |B \right) \right).
\]
'''Доказательство'''
 
Для ограниченного множества опорная функция выпукла и непрерывна на $$\mathbb{R}^n$$. Поэтому в силу леммы 2 и предложения 1 для произвольного $$x$$ имеем
\[
\left( \rho\left( \cdot |A \right) \oplus \rho\left( \cdot |B \right) \right)^*(x) = \rho^*(x| A) + \rho^*(x| B) =
\delta_A(x) + \delta_B(x) = \delta_{A\cap B}(x) = \rho^*( x | A\cap B ),
\]
откуда в силу предложения 3 имеем
\begin{equation}
\label{4}
(\text{cl} \, \varphi)^* = \rho^*( \cdot | A\cap B ),
\end{equation}
где функция $$\varphi$$ определяется соотношением $$\varphi(x) = \left( \rho\left( \cdot |A \right) \oplus \rho\left( \cdot |B \right) \right)(x)$$. Здесь мы использовали легко проверяемое свойство индикаторных функций, а именно, что для любых двух множеств $$A, B$$ выполняется $$\delta_A + \delta_B = \delta_{A\cap B}$$. Функция $$\varphi$$ является собственной, так как она сама не равна тождественно $$+\infty$$, и в силу доказанного выше сопряженная к ней функция также не равна тождественно $$+\infty$$. Поэтому в силу предложения 2 функция $$\text{cl} \, \varphi$$ также является собственной. Применяя к равенству ($$\ref{4}$$) теорему Фенхеля-Моро, имеем $$\rho\left( \cdot | A\cap B \right) = \text{cl}\left( \rho\left( \cdot |A \right) \oplus \rho\left( \cdot |B \right) \right).$$ $$\;\;\blacksquare$$
== Список литературы ==
# Арутюнов А. В. "Лекции по выпуклому и многозначному анализу", М.: ФИЗМАТЛИТ, 2014.
# Востриков И.В. "Лекции по динамическому программированию и процессам управления", 2022.

Теория двойственности Фенхеля-Моро

2022-12-29T22:17:40Z

Nazim22:

== Определения ==
Пусть $$X$$ — [https://ru.wikipedia.org/wiki/Гильбертово_пространство гильбертово] пространство.
 
Через $$\overline{\mathbb{R}}$$ будем обозначать расширенную вещественную прямую, $$\overline{\mathbb{R}} = \mathbb{R} \cup \left\{ -\infty; +\infty \right\}$$.
 
Будем рассматривать функции $$f: X \to \overline{\mathbb{R}}$$.
 
'''Определение 1.'''
''Надграфиком'' функции $$f$$ называется множество
\[
\text{epi} \, f = \left\{ \left( x,\alpha \right) \in X\times \mathbb{R} : f(x) \leqslant \alpha\right\}.
\]
 
'''Определение 2.'''
''Эффективным множеством'' функции $$f$$ называется множество
\[
\text{dom} \, f = \left\{ x \in X : f(x) \lt +\infty \right\}.
\]
 
'''Определение 3.'''
Функция $$f$$ называется ''собственной'', если $$\text{dom} \, f \neq \varnothing$$ и $$f(x) \gt -\infty \; \forall x$$.
 
'''Определение 4.'''
Функция $$f$$ называется ''[https://sawiki.cs.msu.ru/index.php?title=Выпуклая_функция_и_ее_свойства&action=edit&redlink=1 выпуклой]'', если ее надграфик $$\text{epi} \, f$$ является выпуклым множеством.
 
'''Определение 5.'''
Функция $$f$$ называется ''замкнутой'', если ее надграфик $$\text{epi} \, f$$ замкнут.
== Сопряженная функция ==
'''Определение.'''
Функцией, ''сопряженной'' к $$f$$, называется функция, определенная формулой
\[
f^*(x^*) = \underset{x \in X}{\text{sup}}\left( \left\langle x^*,x \right\rangle - f(x) \right),
\]
где $$x^*$$ — обозначение для аргумента сопряженной функции.
 
Из определения сопряженной функции вытекает '''неравенство Юнга-Фенхеля'''
\[
f^*(x^*) + f(x) \geqslant \left\langle x, x^* \right\rangle \; \forall x,x^* \in X.
\]
''Вторая сопряженная'' функция $$f^{**}$$ определяется по формуле $$f^{**}=(f^*)^*$$.
 
'''Пример 1.'''
Для аффинной функции $$f(x) = \left\langle a,x \right\rangle + b$$ сопряженная функция вычисляется по формуле
\[
f^*(x^*) =
\begin{cases}
-b, &x^* = a;\\
+\infty, &x^* \neq a.
\end{cases}
\]
 
'''Пример 2.'''
Для произвольной выпуклой функции $$f$$ умножение на положительный скаляр $$\lambda \gt 0$$ определяется соотношением
\[
\left( \lambda f \right)(x) = \lambda f(x), \; \forall x \in X.
\]
Непосредственно вычисляется, что
\[
\left( \lambda f \right)^*(x^*) \equiv \lambda f^*(x^*/\lambda), \; x^* \in X.
\]
'''Пример 3.'''
Пусть $$M$$ — [https://ru.wikipedia.org/wiki/Евклидово_пространство евклидово] пространство, и пусть $$f: M \to \mathbb{R}$$ — функция $$f(x) = \left\langle a,x \right\rangle$$, где $$a \in M$$. Поскольку
\[
\underset{x\in M}{\text{sup}}\left\{ \left\langle s,x \right\rangle - \left\langle a,x \right\rangle \right\} = \underset{x\in M}{\text{sup}} \left\langle s-a,x \right\rangle =
\begin{cases}
0, &s = a;\\
+\infty, &s \neq a.
\end{cases}
\]
для всех $$s \in M$$, то сопряженная функция $$f^*$$ — [https://ru.wikipedia.org/wiki/Индикатор_(математика) индикаторная функция] $$\delta_\left\{ a \right\}$$ одноэлементного множества $$\left\{ a \right\}$$.
== Вспомогательная лемма ==
'''Лемма.'''
Пусть функция $$f$$ — выпуклая, замкнутая, собственная. Тогда $$f^*$$ — также собственная функция.
==== Доказательство ====
Докажем, что $$f^∗(x^∗) \gt -\infty$$ $$\forall x^∗ \in X$$. Возьмем $$x_0 \in \text{dom} \, f \neq \varnothing$$. Тогда $$f^∗(x^∗) \geqslant \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$$. Следовательно, по [https://sawiki.cs.msu.ru/index.php?title=Отделимость_множеств&action=edit&redlink=1 теореме об отделимости] ее можно строго отделить от выпуклого замкнутого множества $$\text{epi} \, f$$. Поэтому существуют $$y^∗ \in X$$ и $$\beta \in \mathbb{R}$$ такие, что
\begin{equation}
\label{1}
\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.
\end{equation}
Докажем, что $$\beta \lt 0$$. Действительно, предположим обратное. Случай $$\beta \gt 0$$ невозможен, так как $$(x_0, \alpha) \in \text{epi} \, f\;$$ $$\forall \alpha
\geqslant f(x_0) \neq +\infty$$ и, значит, при $$\beta \gt 0$$ имеет место $$\underset{(x_0,\alpha) \in \text{epi} \, f}{\text{sup}}\beta \alpha = +\infty$$, что противоречит неравенству ($$\ref{1}$$).
 
Пусть теперь $$\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 \geqslant \left\langle y^*, x_0 \right\rangle.
\]
Полученное противоречие доказывает, что $$\beta \lt 0$$. Поэтому, в силу положительной однородности неравенства ($$\ref{1}$$) по переменной $$(y^∗, \beta)$$,
не теряя общности, будем считать, что $$\beta = -1$$.
 
В силу ($$\ref{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^*$$ является собственной.$$\;\;\blacksquare$$
== Теорема Фенхеля-Моро ==
'''Теорема.'''
Пусть функция $$f$$ — выпуклая, замкнутая, собственная. Тогда $$f^{**} = f$$.
==== Доказательство ====
Покажем, что $$f^{**} \leqslant f$$. В силу неравенства Юнга-Фенхеля $$\forall x \in X$$ имеем
\[
f(x) \geqslant \left\langle x, x^* \right\rangle - f^*(x^*) \; \forall x^* \in X \implies f(x) \geqslant \underset{x^*}{\text{sup}}\left\{ \left\langle x, x^* \right\rangle - f^*(x^*) \right\} = f^{**}(x).
\]
Остается показать, что $$f^{**} \geqslant 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}$$ такие, что
\begin{equation}
\label{2}
\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).
\end{equation}
Докажем, что $$\beta \lt 0$$. Действительно, случай $$\beta \gt 0$$ невозможен, что обосновывается так же, как и при доказательстве вспомогательной леммы, с учетом того, что $$\text{dom} \, f \neq \varnothing$$.
 
Пусть теперь $$\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 \varnothing$$. Для $$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) \leqslant \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) \geqslant \left\langle y^*_1 + ty^*, x_0 \right\rangle - f^*(y^*_1 + ty^*) \geqslant \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$$. В силу неравенства ($$\ref{2}$$) имеем
\[
-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^{**} \geqslant f$$ и, значит, $$f^{∗∗} = f$$. $$\;\;\blacksquare$$
== Приложения теории двойственности ==
=== Связь опорной и индикаторной функций множества ===
Определим [https://sawiki.cs.msu.ru/index.php/Опорная_функция_множества опорную функцию] множества $$A \subset X$$ на $$X$$ соотношением
\begin{equation}
\label{3}
c(x^*,A) = \underset{y \in A}{\text{sup}} \left\langle x^*, y \right\rangle, x^* \in X.
\end{equation}
Введем индикаторную функцию следующим образом
\[
\delta_A(x) =
\begin{cases}
0, &x \in A;\\
+\infty, &x \notin A.
\end{cases}
\]
'''Предложение 1.''' Пусть $$\delta_A(\cdot)$$ — индикаторная функция выпуклого замкнутого множества $$A$$. Тогда $$c^*(\cdot,A) = \delta_A(\cdot)$$.
 
'''Доказательство'''
 
Функция $$\delta_A$$ является выпуклой, замкнутой и собственной. Поэтому по теореме Фенхеля-Моро $$\delta_A^{**} = \delta_A$$. Кроме того, для произвольного $$x^*$$ имеем
\[
\delta_A^*(x^*) = \underset{x}{\text{sup}}\left\{ \left\langle x, x^* \right\rangle - \delta_A(x)\right\} = \underset{x \in A}{\text{sup}} \left\{ \left\langle x, x^* \right\rangle \right\} = c(x^*, A).
\]
Следовательно, $$\delta_A = \delta_A^{**} = c^*(\cdot,A)$$. $$\;\;\blacksquare$$
=== Евклидово расстояние от точки до множества ===
Для [https://translated.turbopages.org/proxy_u/en-ru.ru.a3199e6e-63adda8c-2d9f628d-74722d776562/https/en.wikipedia.org/wiki/Euclidean_metric#Properties евклидова расстояния]
$$d(x,ℳ) = \underset{y \in ℳ}{\text{min}} \left\| x -y \right\|$$ от точки $$x$$ до множества $$ℳ$$, $$ℳ \in \text{conv} \;\mathbb{R}^n$$ — выпуклый компакт, справедливы следующие соотношения двойственности
\[
d(x,ℳ) = \underset{\left\| l \right\| \leqslant 1}{\text{max}} \left\{ \left( l,x \right) - \rho\left( l|ℳ \right) \right\},
\]
\[
d^2(x,ℳ) = \underset{l}{\text{max}} \left\{ \left( l,x \right) - \rho\left( l|ℳ \right) - \frac{1}{4} \left( l,l \right) \right\},
\]
где $$\rho\left( l|ℳ \right)$$ — [https://sawiki.cs.msu.ru/index.php/Опорная_функция_множества опорная функция] множества $$ℳ$$.
 
Покажем справедливость второго соотношения.
 
Имеем функцию $$\varphi(x) = d^2(x,ℳ) = \underset{y \in ℳ}{\text{min}}\left( x-y, x-y \right)$$. Поскольку функция $$\varphi$$ является выпуклой, замкнутой и собственной, по теореме Фенхеля-Моро $$\varphi^{**} = \varphi$$.
 
Найдем сопряженную функцию к $$\varphi(x)$$
\[
\varphi^*(l) = \underset{x}{\text{sup}}\left\{ \left( l,x \right) - \varphi(x) \right\} = \underset{x}{\text{sup}}\;\underset{y \in ℳ}{\text{max}} \left\{ \left( l,x \right) - \left( x-y,x-y \right)\right\} = \underset{y \in ℳ}{\text{max}} \;\underset{x}{\text{sup}} \left\{ \left( l,x \right) - \left( x-y,x-y \right)\right\} = \underset{y \in ℳ}{\text{max}} \left(\left( l, \frac{l}{2} + y \right) - \frac{1}{4}\left( l,l \right)\right)= \rho\left( l|ℳ \right) + \frac{1}{4}\left( l,l \right),
\]
откуда, очевидно, следует второе соотношение. $$\;\;\blacksquare$$
=== Расстояние по Хаусдорфу между двумя компактами ===
Пусть $$X = \mathbb{R}^n$$, $$A$$ и $$B$$ — выпуклые компакты.
 
'''Лемма 1.'''
\[
h\left( A, B \right) = \underset{\left\| l \right\| \leqslant 1}{\text{max}}\left| \rho\left( l|A \right) - \rho\left( l|B \right)\right|,
\]
где $$h\left( A, B \right)$$ — [https://sawiki.cs.msu.ru/index.php/Метрика_Хаусдорфа расстояние по Хаусдорфу] между множествами $$A$$ и $$B$$.
 
'''Замечание 1.''' $$d\left( x, B \right) = h\left( x, B \right) = \underset{\left\| l \right\| \leqslant 1}{\text{max}}\left| \left( l,x \right) - \rho\left( l|B \right)\right|$$.
=== Опорная функция пересечения множеств ===
Приведем три вспомогательных утверждения без доказательства $$^{[1]}$$.
 
'''Лемма 2.''' Для любых функций $$f_1,{...},f_n$$ имеет место
\[
\left( f_1 \oplus f_2 \oplus {...} \oplus f_n \right)^* = f_1^* + f_2^* + {...} + f_n^*.
\]
'''Предложение 2.''' Пусть $$f$$ — выпуклая собственная функция и $$X = \mathbb{R}^n$$. Тогда ее [https://ru.wikipedia.org/wiki/Замыкание_(анализ) замыкание] $$\text{cl} \, f$$ также является собственной функцией.
 
'''Предложение 3.''' Для выпуклой функции $$f$$ имеет место
\[
(\text{cl} \, f)^* = f^*.
\]
 
Определим опорную функцию соотношением ($$\ref{3}$$).
 
'''Предложение 4.''' Пусть $$A, B$$ — выпуклые ограниченные подмножества $$\mathbb{R}^n$$ и $$\text{int} \, A \cap \text{int} \, B \neq \varnothing$$. Тогда
\[
c\left( \cdot , A\cap B \right) = \text{cl}\left( c\left( \cdot ,A \right) \oplus c\left( \cdot ,B \right) \right).
\]
'''Доказательство'''
 
Для ограниченного множества опорная функция выпукла и непрерывна на $$\mathbb{R}^n$$. Поэтому в силу леммы 2 и предложения 1 для произвольного $$x$$ имеем
\[
\left( c\left( \cdot ,A \right) \oplus c\left( \cdot ,B \right) \right)^*(x) = c^*(x, A) + c^*(x, B) =
\delta_A(x) + \delta_B(x) = \delta_{A\cap B}(x) = c^*( x , A\cap B ),
\]
откуда в силу предложения 3 имеем
\begin{equation}
\label{4}
(\text{cl} \, \varphi)^* = c^*( \cdot , A\cap B ),
\end{equation}
где функция $$\varphi$$ определяется соотношением $$\varphi(x) = \left( c\left( \cdot ,A \right) \oplus c\left( \cdot ,B \right) \right)(x)$$. Здесь мы использовали легко проверяемое свойство индикаторных функций, а именно, что для любых двух множеств $$A, B$$ выполняется $$\delta_A + \delta_B = \delta_{A\cap B}$$. Функция $$\varphi$$ является собственной, так как она сама не равна тождественно $$+\infty$$, и в силу доказанного выше сопряженная к ней функция также не равна тождественно $$+\infty$$. Поэтому в силу предложения 2 функция $$\text{cl} \, \varphi$$ также является собственной. Применяя к равенству ($$\ref{4}$$) теорему Фенхеля-Моро, имеем $$c\left( \cdot , A\cap B \right) = \text{cl}\left( c\left( \cdot ,A \right) \oplus c\left( \cdot ,B \right) \right).$$ $$\;\;\blacksquare$$
== Список литературы ==
# Арутюнов А. В. "Лекции по выпуклому и многозначному анализу", М.: ФИЗМАТЛИТ, 2014.
# Востриков И.В. "Лекции по динамическому программированию и процессам управления", 2022.

Теория двойственности Фенхеля-Моро

2022-12-07T09:29:53Z

Nazim22:

Теория двойственности Фенхеля-Моро

2022-12-06T20:23:00Z

Nazim22:

Теория двойственности Фенхеля-Моро

2022-12-06T19:07:00Z

Nazim22:

Теория двойственности Фенхеля-Моро

2022-12-06T16:33:09Z

Nazim22:

Теория двойственности Фенхеля-Моро

2022-12-04T21:03:59Z

Nazim22:

== Определения ==
Пусть $$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$$. Следовательно, по [https://sawiki.cs.msu.ru/index.php?title=Отделимость_множеств&action=edit&redlink=1 теореме об отделимости] ее можно строго отделить от выпуклого замкнутого множества $$\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$$. $$\;\;$$ ∎
== Список литературы ==
# Арутюнов А. В. "Лекции по выпуклому и многозначному анализу", М.: ФИЗМАТЛИТ, 2014.

Теория двойственности Фенхеля-Моро

2022-12-04T20:36:40Z

Nazim22:

== Определения ==
Пусть $$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$$. Следовательно, по [https://sawiki.cs.msu.ru/index.php?title=Отделимость_множеств&action=edit&redlink=1 теореме об отделимости] ее можно строго отделить от выпуклого замкнутого множества $$\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^*$$ вытекает
\[
(заполнить).
\]
Получили противоречие, так как $$\gamma \gt 0$$ и, значит, при больших $$t$$ значение $$t\gamma$$ может быть сделано как угодно большим и, следовательно, при достаточно больших $$t \gt 0$$ последнее неравенство выполняться не может.
 
Таким образом, доказано, что $$\beta \lt 0$$; значит, не теряя общности рассуждений, будем считать, что $$\beta = -1$$. В силу неравенства $$(♦)$$ имеем
\[
(заполнить),
\]
откуда $$\left\langle y^*, x_0 \right\rangle \gt f^*(y^*) + f^{**}(x_0)$$, что противоречит неравенству Юнга–Фенхеля для функции $$f^∗$$. Полученное противоречие доказывает, что $$f^{**} \ge f$$ и, значит, $$f^{∗∗} = f$$. $$\;\;$$ ∎
== Список литературы ==
# Арутюнов А. В. "Лекции по выпуклому и многозначному анализу", М.: ФИЗМАТЛИТ, 2014.

Теория двойственности Фенхеля-Моро

2022-12-04T16:44:52Z

Nazim22:

== Определения ==
Пусть $$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$$. Следовательно, по [https://sawiki.cs.msu.ru/index.php?title=Отделимость_множеств&action=edit&redlink=1 теореме об отделимости] ее можно строго отделить от выпуклого замкнутого множества $$\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^*$$ вытекает
(заполнить).
Получили противоречие, так как $$\gamma \gt 0$$ и, значит, при больших $$t$$ значение $$t\gamma$$ может быть сделано как угодно большим и, следовательно, при достаточно больших $$t \gt 0$$ последнее неравенство выполняться не может.
 
Таким образом, доказано, что $$\beta \lt 0$$; значит, не теряя общности рассуждений, будем считать, что $$\beta = -1$$. В силу неравенства $$(♦)$$ имеем
(заполнить),
откуда $$\left\langle y^*, x_0 \right\rangle \gt f^*(y^*) + f^{**}(x_0)$$, что противоречит неравенству Юнга–Фенхеля для функции $$f^∗$$. Полученное противоречие доказывает, что $$f^{**} \ge f$$ и, значит, $$f^{∗∗} = f$$. $$\;\;$$ ∎
== Список литературы ==
# Арутюнов А. В. "Лекции по выпуклому и многозначному анализу", М.: ФИЗМАТЛИТ, 2014.

Теория двойственности Фенхеля-Моро

2022-12-04T13:24:38Z

Nazim22:

Теория двойственности Фенхеля-Моро

2022-12-04T13:21:32Z

Nazim22:

Теория двойственности Фенхеля-Моро

2022-12-02T18:06:19Z

Nazim22: Новая страница: «== Определения == Пусть $$X$$ — вещественное линейное пространство. Через $$\overline{\mathbb{R}}$$ б...»