Выпуклая функция и ее свойства: различия между версиями

Материал из sawiki
Перейти к навигации Перейти к поиску
Строка 2: Строка 2:
 
[[Файл:New_ellips.png|200px|thumb|frame|right|Пример выпуклого множества.]]
 
[[Файл:New_ellips.png|200px|thumb|frame|right|Пример выпуклого множества.]]
  
'''Выпуклая функция''' - функция $$f: X \to \overline{\R}$$, действующая из вещественного линейного пространства $$X \in \overline{\mathbb{R}}$$ в вещественную расширенную прямую $$\overline{\R} = \{ -\infty\} \cup \R \cup \{ +\infty\}$$, надграфик которой является [[Выпуклое множество и его свойства|выпуклым множеством]].
+
'''Выпуклая''' (или '''выпуклая вниз''') функция - функция $$f: X \to \overline{\R}$$, действующая из вещественного линейного пространства $$X \in \overline{\mathbb{R}}$$ в вещественную расширенную прямую $$\overline{\R} = \{ -\infty\} \cup \R \cup \{ +\infty\}$$, надграфик которой является [[Выпуклое множество и его свойства|выпуклым множеством]].
  
 
== Определение выпуклой, собственной функции ==
 
== Определение выпуклой, собственной функции ==
Строка 13: Строка 13:
 
называемые соответственно ''надграфиком'' функции $$f$$ и её ''эффективным множеством''.
 
называемые соответственно ''надграфиком'' функции $$f$$ и её ''эффективным множеством''.
  
2. Функция $$f$$ называется '''выпуклой''', если ее надграфик $$\operatorname{epi} f$$ является выпуклым множеством. Функция $$f$$ называется '''вогнутой''', если функция $$(−f)$$ является выпуклой.
+
2. Функция $$f$$ называется '''выпуклой''' ('''строго выпуклой'''), если ее надграфик $$\operatorname{epi} f$$ является (строго выпуклым), выпуклым множеством. Функция $$f$$ называется '''вогнутой''' или '''выпуклой вверх''' ('''строго вогнутой'''), если функция $$(−f)$$ является выпуклой (строго выпуклой).
  
 
3. Функция $$f$$ называется '''собственной''', если $$\operatorname{dom} f \not= \varnothing$$ и $$f(x) > -\infty$$ для $$\forall x$$. Функция, не являющаяся собственной, называется '''несобственной'''.
 
3. Функция $$f$$ называется '''собственной''', если $$\operatorname{dom} f \not= \varnothing$$ и $$f(x) > -\infty$$ для $$\forall x$$. Функция, не являющаяся собственной, называется '''несобственной'''.
Строка 24: Строка 24:
 
f(\alpha x_1 + (1-\alpha)x_2) \leqslant \alpha f(x_1) + (1-\alpha)f(x_2).
 
f(\alpha x_1 + (1-\alpha)x_2) \leqslant \alpha f(x_1) + (1-\alpha)f(x_2).
 
\end{gather}
 
\end{gather}
 +
Если это неравенство является строгим для $$\forall \alpha \in [0,1]$$, функция строго выпуклая; если выполняется обратное неравенство, функция вогнутая.
  
По индукции получаем, что $$\eqref{eq1}$$, а значит, и выпуклость собственной функции $$f$$, равносильны тому, что для $$\forall n \in \N$$ имеет место '''неравенство Йенсена''':
+
'''Теорема (неравенство Йенсена)'''. Равенство $$\eqref{eq1}$$, а значит, и выпуклость собственной функции $$f$$, равносильны тому, что для $$\forall n \in \N$$ имеет место неравенство:
 
\begin{gather}\label{eq2}
 
\begin{gather}\label{eq2}
 
     f\Big(\sum_{i=1}^n\alpha_i x_i\Big) \leqslant \sum_{i=1}^n\alpha_i f(x_i) \;
 
     f\Big(\sum_{i=1}^n\alpha_i x_i\Big) \leqslant \sum_{i=1}^n\alpha_i f(x_i) \;
Строка 33: Строка 34:
 
\end{gather}
 
\end{gather}
 
для любых точек $$x_1, ..., x_n$$.
 
для любых точек $$x_1, ..., x_n$$.
 +
 +
Пусть $$X$$  - нормированное пространство, функция $$f: X \to \R$$, непрерывна и
 +
\begin{gather}
 +
f \left( \dfrac{x+y}{2} \right) \leqslant \frac{f \left( x \right) + f \left( y \right)} /' \forall x, y \in X,
 +
\end{gather}
 +
т. е. неравенство Йенсена выполняется лишь при $$\alpha = 1/2$$. Тогда функция $$f$$ выпукла.
 +
''Доказательство''.
 +
\begin{gather}
 +
    f \left( \dfrac{3}{4}x + \dfrac{1}{4}y \right) \leqslant
 +
\dfrac{1}{2}\left( f(x) + f \left( \dfrac{x+y}{2} \right)\right) \leqslant
 +
\dfrac{3}{4} f(x) + \dfrac{1}{4} f(y).
 +
\end{gather}
 +
Аналогично
 +
\begin{gather}
 +
    f \left( \dfrac{1}{4}x + \dfrac{3}{4}y \right) \leqslant
 +
\dfrac{1}{4} f(x) + \dfrac{3}{4} f(y).
 +
\end{gather}
  
 
Если функция (не обязательно собственная) выпукла, то $$\eqref{eq2}$$ выполняется для любого набора точек $$x_1,...,x_n$$, для которых $$-\infty < f(x_i) < +\infty$$, $$i = \overline{1, n}$$.
 
Если функция (не обязательно собственная) выпукла, то $$\eqref{eq2}$$ выполняется для любого набора точек $$x_1,...,x_n$$, для которых $$-\infty < f(x_i) < +\infty$$, $$i = \overline{1, n}$$.
Строка 38: Строка 56:
 
Из $$\eqref{eq2}$$ вытекает, что эффективное множество выпуклой функции выпукло.
 
Из $$\eqref{eq2}$$ вытекает, что эффективное множество выпуклой функции выпукло.
  
 +
Если функции $$f$$, $$g$$ выпуклы, то любая их линейная комбинация $$af+bg$$ с положительными коэффициентами $$a, b \in \R$$ также выпукла.
 +
 +
Локальный минимум выпуклой функции является также глобальным минимумом (соответственно, для выпуклых вверх функций локальный максимум является глобальным максимумом).
  
 
Далее считаем, что $$X$$ - нормированное пространство.
 
Далее считаем, что $$X$$ - нормированное пространство.
Строка 46: Строка 67:
 
\end{gather}
 
\end{gather}
 
Здесь неотрицательность квадратичной формы $$Q = \frac{\partial^2 f(x)}{\partial x^2}$$ означает, что $$\langle Qξ, ξ\rangle \geqslant 0 \forall ξ \in X $$.
 
Здесь неотрицательность квадратичной формы $$Q = \frac{\partial^2 f(x)}{\partial x^2}$$ означает, что $$\langle Qξ, ξ\rangle \geqslant 0 \forall ξ \in X $$.
 +
 +
''Замечание''. Обратное неверно. Например, функция $$f(x)=x^4$$ строго выпукла на $$[-1,1]$$, но её производная в точке $$x=0$$ равна нулю.
  
 
''' Следствие'''. Если функция $$f$$ выпукла и дважды непрерывно дифференцируема в некоторой окрестности точки $$x_0 \in X$$, то  
 
''' Следствие'''. Если функция $$f$$ выпукла и дважды непрерывно дифференцируема в некоторой окрестности точки $$x_0 \in X$$, то  
Строка 89: Строка 112:
 
== Список литературы ==
 
== Список литературы ==
 
1. Арутюнов А. В. "Лекции по выпуклому и многозначному анализу", М.: ФИЗМАТЛИТ, 2004.
 
1. Арутюнов А. В. "Лекции по выпуклому и многозначному анализу", М.: ФИЗМАТЛИТ, 2004.
 +
2.  Фих­тен­гольц Г. М. "Курс диф­фе­рен­ци­аль­но­го и ин­те­граль­но­го ис­чис­ле­ния." 8-е изд. М.; СПб., 2001;
 +
3. Иль­ин В. А., По­зняк Э. Г. "Ос­но­вы ма­те­ма­ти­че­ско­го ана­ли­за." 6-е изд. М., 2001. Т. 1.

Версия 19:00, 5 сентября 2023

Пример выпуклого множества.

Выпуклая (или выпуклая вниз) функция - функция $$f: X \to \overline{\R}$$, действующая из вещественного линейного пространства $$X \in \overline{\mathbb{R}}$$ в вещественную расширенную прямую $$\overline{\R} = \{ -\infty\} \cup \R \cup \{ +\infty\}$$, надграфик которой является выпуклым множеством.

Определение выпуклой, собственной функции

1. Пусть $$\overline{\R} = \{ -\infty\} \cup \R \cup \{ +\infty\}$$ - расширенная вещественная прямая, $$X \in \overline{\mathbb{R}}$$ - вещественное линейное пространство. С каждой функцией $$f: X \to \overline{\R}$$ можно связать множества \begin{gather*} \operatorname{epi} f \equiv \bigl\{(x,\alpha) \in X \times \overline{\R} \mid f(x) \leqslant \alpha\bigr\},\\ \operatorname{dom} f \equiv \bigl\{x \in X \mid f(x) \leqslant +\infty\bigr\}, \end{gather*} называемые соответственно надграфиком функции $$f$$ и её эффективным множеством.

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

3. Функция $$f$$ называется собственной, если $$\operatorname{dom} f \not= \varnothing$$ и $$f(x) > -\infty$$ для $$\forall x$$. Функция, не являющаяся собственной, называется несобственной.

Свойства выпуклой функции

Необходимое и достаточное условие выпуклости

Собственная функция $$f$$ является выпуклой $$\Leftrightarrow $$ для $$\forall \alpha \in [0,1]$$, $$\forall x_1, x_2$$ выполняется: \begin{gather}\label{eq1} f(\alpha x_1 + (1-\alpha)x_2) \leqslant \alpha f(x_1) + (1-\alpha)f(x_2). \end{gather} Если это неравенство является строгим для $$\forall \alpha \in [0,1]$$, функция строго выпуклая; если выполняется обратное неравенство, функция вогнутая.

Теорема (неравенство Йенсена). Равенство $$\eqref{eq1}$$, а значит, и выпуклость собственной функции $$f$$, равносильны тому, что для $$\forall n \in \N$$ имеет место неравенство: \begin{gather}\label{eq2} f\Big(\sum_{i=1}^n\alpha_i x_i\Big) \leqslant \sum_{i=1}^n\alpha_i f(x_i) \; \forall (\alpha_1,..., \alpha_n): \: \sum_{i=1}^n\alpha_i = 1, \: \alpha_i \leqslant 0, \end{gather} для любых точек $$x_1, ..., x_n$$.

Пусть $$X$$ - нормированное пространство, функция $$f: X \to \R$$, непрерывна и \begin{gather} f \left( \dfrac{x+y}{2} \right) \leqslant \frac{f \left( x \right) + f \left( y \right)} /' \forall x, y \in X, \end{gather} т. е. неравенство Йенсена выполняется лишь при $$\alpha = 1/2$$. Тогда функция $$f$$ выпукла. Доказательство. \begin{gather} f \left( \dfrac{3}{4}x + \dfrac{1}{4}y \right) \leqslant \dfrac{1}{2}\left( f(x) + f \left( \dfrac{x+y}{2} \right)\right) \leqslant \dfrac{3}{4} f(x) + \dfrac{1}{4} f(y). \end{gather} Аналогично \begin{gather} f \left( \dfrac{1}{4}x + \dfrac{3}{4}y \right) \leqslant \dfrac{1}{4} f(x) + \dfrac{3}{4} f(y). \end{gather}

Если функция (не обязательно собственная) выпукла, то $$\eqref{eq2}$$ выполняется для любого набора точек $$x_1,...,x_n$$, для которых $$-\infty < f(x_i) < +\infty$$, $$i = \overline{1, n}$$.

Из $$\eqref{eq2}$$ вытекает, что эффективное множество выпуклой функции выпукло.

Если функции $$f$$, $$g$$ выпуклы, то любая их линейная комбинация $$af+bg$$ с положительными коэффициентами $$a, b \in \R$$ также выпукла.

Локальный минимум выпуклой функции является также глобальным минимумом (соответственно, для выпуклых вверх функций локальный максимум является глобальным максимумом).

Далее считаем, что $$X$$ - нормированное пространство.

Теорема (критерий выпуклости)

Пусть $$X$$ - евклидово пространство и функция $$f$$ дважды непрерывно дифференцируема на $$X$$. Тогда функция $$f$$ выпукла $$\Leftrightarrow $$ для $$\forall x \in X$$ выполняется: \begin{gather}\label{eq3} \dfrac{\partial^2 f(x)}{\partial x^2} \geqslant 0 \; \end{gather} Здесь неотрицательность квадратичной формы $$Q = \frac{\partial^2 f(x)}{\partial x^2}$$ означает, что $$\langle Qξ, ξ\rangle \geqslant 0 \forall ξ \in X $$.

Замечание. Обратное неверно. Например, функция $$f(x)=x^4$$ строго выпукла на $$[-1,1]$$, но её производная в точке $$x=0$$ равна нулю.

Следствие. Если функция $$f$$ выпукла и дважды непрерывно дифференцируема в некоторой окрестности точки $$x_0 \in X$$, то \begin{gather} \dfrac{\partial^2 f}{\partial x^2}(x_0) \geqslant 0. \end{gather}

Замкнутость, ограниченность, непрерывность и липшицевость выпуклых функций

Будем считать, что $$X$$ - нормированное пространство. Функция $$f: X \to \overline{\R}$$ непрерывна в точке $$x_0 \in X$$, если для любой сходящейся к ней последовательности $$\bigl\{x_i\bigr\}$$ имеет место $$f(x_i) \rightarrow f(x_0)$$ при $$i \rightarrow \infty$$.

Определенная на $$X$$ функция $$f$$ называется полунепрерывной снизу в точке $$x_0$$, если $$\underline{\lim}_{x_i \rightarrow x_0} f(x_i) \geqslant f(x_0)$$. Функция $$f$$ называется полунепрерывной сверху в точке $$x_0$$, если функция $$-f$$ полунепрерывна снизу. Функция полунепрерывна снизу (сверху), если она полунепрерывна снизу (сверху) во всех точках.

Функция называется замкнутой, если её надграфик замкнут.

Утв 1. Пусть $$f$$ - выпуклая собственная функция и $$X = \overline{\R}^n$$. Тогда её замыкание $$\operatorname{cl} f$$ также является собственной функцией.

Необходимое и достаточное условие полунепрерывности снизу

Функция $$f$$ полунепрерывна снизу $$\Leftrightarrow$$, когда для $$\forall a \in \R$$ ее множество Лебега $$\mathcal{L}_a f$$ замкнуто.

Необходимое и достаточное условие замкнутости

Для замкнутости функции необходимо и достаточно, чтобы она была полунепрерывна снизу.

Полунепрерывность сверху

Пусть $$f: \R^n \to \overline{\R}$$ - выпуклая функция и $$M \subset \operatorname{dom} f$$ - симплектическое множество. Тогда сужение $$f$$ на $$M$$ полунепрерывно сверху. То есть, если последовательность $$$$ $$M$$ $$x_0$$, то верхний предел $$f(x_i)$$ не превышает $$f(x_0)$$.

Теорема о непрерывности в окрестности точки

Пусть выпуклая собственная функция $$f: X \to \overline{\R}$$ ограничена сверху в некоторой окрестности заданной точки $$x_0$$. Тогда $$f$$ непрерывна в этой окрестности точки $$x_0$$.

Следствие (липшицевость в окрестности). Пусть для выпуклой собственной функции $$f: X \to \overline{\R}$$ и точки $$x_0 \in X$$ $$\exists c > 0$$, $$\delta >0$$, что $$f(x) \leqslant c$$ $$\forall x \in O(x_0, 2\delta)$$. Тогда на множестве $$O(x_0, 2\delta)$$ функция $$f$$ удовлетворяет условию Липшица с константой $$c$$: окрестности точки $$x_0 \in X$$, то \begin{gather} \mid f(x_2) - f(x_1)\mid \leqslant c \mid \mid x_2 - x_1 \mid \mid \; \forall x_1, x_2 \in O(x_0, \delta). \end{gather}

Следствие. Пусть выпуклая собственная функция $$f: X \to \overline{\R}$$ ограничена сверху на некотором непустом открытом множестве. Тогда она непрерывна на множестве $$\operatorname{int}(\operatorname{dom f}) \not = \varnothing$$.

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

Теорема о липшицевости на выпуклом компакте

Пусть $$f: \R^n \to \overline{\R}$$ - собственная выпуклая функция, $$S$$ - выпуклый компакт и $$S \subset \operatorname{int}(\operatorname{dom f})$$. Тогда на множестве $$S$$ функция $$f$$ удовлетворяет условию Липшица.

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

1. Арутюнов А. В. "Лекции по выпуклому и многозначному анализу", М.: ФИЗМАТЛИТ, 2004. 2. Фих­тен­гольц Г. М. "Курс диф­фе­рен­ци­аль­но­го и ин­те­граль­но­го ис­чис­ле­ния." 8-е изд. М.; СПб., 2001; 3. Иль­ин В. А., По­зняк Э. Г. "Ос­но­вы ма­те­ма­ти­че­ско­го ана­ли­за." 6-е изд. М., 2001. Т. 1.