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

Материал из sawiki
Перейти к навигации Перейти к поиску
Строка 126: Строка 126:
 
Иными словами, несобственная выпуклая функция бесконечна во всех точках, кроме, быть может, точек относительной границы своего эффективного множества.  
 
Иными словами, несобственная выпуклая функция бесконечна во всех точках, кроме, быть может, точек относительной границы своего эффективного множества.  
  
'''Лемма 2'''. Пусть $$f$$ - выпуклая функция и $$X \in \R^n$$. Тогда $$a \in \R^n$$, ,$$b \in \R$$ что:  
+
'''Лемма 2'''. Пусть $$f$$ - выпуклая функция и $$X \in \R^n$$. Тогда $$a \in \R^n$$, $$b \in \R$$ что:  
 
\begin{gather*}
 
\begin{gather*}
 
f(x) \geqslant \langle a, x\rangle+b \; \forall x \in X.
 
f(x) \geqslant \langle a, x\rangle+b \; \forall x \in X.

Версия 20:23, 7 сентября 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$$.

Доказательство. Докажем по индукции.

1. База при $$n = 2$$ верна в силу $$\eqref{eq1}$$.

2. Пусть это верно для $$n$$. Докажем, что это верно для $$n + 1$$.

По условию $$\sum_{k=1}^{n+1}\alpha_k = 1$$. Обозначим $$s_n =\sum_{k=1}^{n}\alpha_k$$.

$$\beta_k = \alpha_k/s_n$$. Тогда $$\sum_{k=1}^{n}\beta_k = \dfrac{1}{s_n}\sum_{k=1}^{n}\alpha_k = \dfrac{s_n}{s_n} = 1$$.

\begin{gather*} \sum_{k=1}^{n+1}\alpha_k f(x_k) = s_n \sum_{k=1}^{n}\beta_k f(x_k) + \alpha_{n+1}f(x_{n+1}) \leqslant \text{(по предположению индукции)}\leqslant \\ \leqslant s_n f \left( \sum_{k=1}^{n}\beta_k x_k \right) + \alpha_{n+1}f(x_{n+1}) \leqslant \text{(так как } s_n + \alpha_{n+1} ) \leqslant f \left( \sum_{k=1}^{n+1}\alpha_k x_k \right) \end{gather*} $$\blacksquare$$

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


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

Доказательство. Докажем по индукции, что для $$\forall \alpha = \dfrac{m}{2^k}\in (0,1)$$ выполняется неравенство Йенсена $$f(\alpha x + (1- \alpha)y) \leqslant \alpha f(x) + (1-\alpha) f(y)$$.

1. Подставим $$\alpha_1 = 3/4$$ и $$\alpha_2 = 1/4$$ в неравенство Йенсена $$\eqref{eq2}$$. \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*} Аналогично выполняется для $$\alpha_1 = 1/4$$ и $$\alpha_2 = 3/4$$: \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*}

2. Пусть неравенство верно для $$\alpha_1, \alpha_2 \in (0,1)$$. Тогда \begin{gather*} f \left( \dfrac{1}{2}( \alpha_1 x + (1 - \alpha_1)y + \alpha_2 x + (1 - \alpha_2)y)\right) \leqslant \dfrac{1}{2}\left( f(\alpha_1 x + (1 - \alpha_1)y) + f(\alpha_2 x + (1-\alpha_2)y \right) \leqslant \\ \leqslant \dfrac{\alpha_1 + \alpha_2}{2}f(x) + \dfrac{(1-\alpha_1) + (1-\alpha_2)}{2} f(y). \end{gather*}

3. Докажем, что функция $$f$$ выпукла, т. е. неравенство Йенсена выполняетсядля произвольных $$\alpha, \beta \in [0, 1]$$, $$\alpha + \beta = 1$$. Выберем $$\{\alpha_n, \beta_n\}$$ вида $$\alpha_n = \dfrac{m}{2^k}$$ так, что $$\{\alpha_n, \beta_n\} \to \{\alpha, \beta\}$$ при $$n \to \infty$$. Из непрерывности $$f$$ $$f(\alpha_n x + \beta_n y) \to f(\alpha x + \beta y)$$ при $$n \to \infty$$.

В силу доказанного в п. 2 для $$\forall n$$: \begin{gather*} f ( \alpha_n x + \beta_n y) \leqslant \alpha_n f(x) + \beta_n f(y). \end{gather*}

В силу произвольности $$n$$ при $$n \to\infty$$ получаем \begin{gather*} f ( \alpha x + \beta y) \leqslant \alpha f(x) + \beta f(y). \end{gather*} $$\blacksquare$$

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



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

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

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

Критерий выпуклости

Аффинной оболочкой множества $$A \subset X$$ ($$\operatorname{aff} A$$) называется множество всевозможных аффинных комбинаций точек из $$A$$, то есть \begin{gather*} \operatorname{aff} A = \left\{ x: x = \sum_{i = 1}^n \alpha_i x_i \mid n \in \N, \; \sum_{i=1}^n \alpha_i = 1, \; x_i \in A \right\}. \end{gather*}

Пусть $$X$$ - нормированное пространство, и $$A \subset X$$. Относительной внутренностью выпуклого множества $$A$$ ($$\operatorname{ri} A$$) называется внутренность $$A$$ относительно $$\operatorname{aff} A$$. А именно, точка $$x_0 \in \operatorname{ri} A$$, если $$\exists ε > 0$$ такое, что \begin{gather*} O(x_0, ε) \cap \operatorname{aff A} \subset A. \end{gather*}

Теорема. Пусть множество $$A \subset \R^n$$ выпукло. Тогда его относительная внутрость $$\operatorname{ri} A$$ непуста.

Лемма 1. Пусть выпуклая функция $$f$$ не является собственной. Тогда \begin{gather*} f(x) = - \infty \; \forall x \in \operatorname{ri}(\operatorname{dom}f). \end{gather*} Иными словами, несобственная выпуклая функция бесконечна во всех точках, кроме, быть может, точек относительной границы своего эффективного множества.

Лемма 2. Пусть $$f$$ - выпуклая функция и $$X \in \R^n$$. Тогда $$a \in \R^n$$, $$b \in \R$$ что: \begin{gather*} f(x) \geqslant \langle a, x\rangle+b \; \forall x \in X. \end{gather*}

Теорема (критерий выпуклости). Пусть $$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 $$.

Доказательство. Необходимость. Обозначим $$ \dfrac{\partial^2 f(x)}{\partial x^2} = f''(x)$$. Предположим, функци $$f$$ выпукла. Фиксируем произвольные $$x, y \in X$$. В силу определения выпуклости $$\forall \lambda \in [0, 1]$$ \begin{gather*} f(\lambda x + (1-\lambda)y) \leqslant \lambda f(x) + (1 - \lambda)f(y), \end{gather*} откуда \begin{gather}\label{eq4} \lambda f(x) \geqslant \lambda f(y) + [f(y + \lambda(x-y)) - f(y)]. \end{gather} Для каждого фиксированного $$\lambda \in [0, 1]$$ определим скалярную функцию $$φ_{\lambda} : [0, 1] \to \R$$ по формуле $$φ_{\lambda}(θ) = f(y + θλ(x-y))$$. По формуле конечных приращений Лагранжа $$\forall \lambda \in [0, 1]$$ $$\exists θ_λ \in [0,1]$$, такое, что $$φ_{\lambda}(1) - φ_{\lambda}(0) = φ_{\lambda}'(θ_λ)$$. Поэтому, вычисляя производную $$φ_{\lambda}$$ как производную сложной функции, получаем \begin{gather*} f(y + λ(x-y)) - f(y) = \langle f'(y + θ_λλ(x-y)), λ(x-y)\rangle. \end{gather*} Подставляя это выражение в неравенство $$\eqref{eq4}$$, получаем $$\forall \in [0, 1]$$ $$\exists θ_λ \in [0,1]$$: \begin{gather*} λf(x) \geqslant λf(y) + \langle f'(y + θ_λλ(x-y)), λ(x-y)\rangle. \end{gather*} Делим обечасти неравенства на $$λ > 0$$, при $$\lambda \to 0+$$ имеем \begin{gather*} f(x) \geqslant f(y) + \langle f'(y), x-y\rangle. \end{gather*} Меняем $$x$$ и $$y$$ местами, получаем \begin{gather*} f(y) \geqslant f(x) + \langle f'(x), y-x\rangle. \end{gather*} Складываем получаенные неравенства. \begin{gather*} \langle f'(y) - f'(x), y-x\rangle \geqslant 0 \; \forall x, y. \end{gather*} Пусть $$y=x+\epsilon h$$ и $$\epsilon > 0$$. Повторяя рассуждения, основанные на применении формулы конечных приращений Лагранжа, получаем, что для $$\forall \epsilon > 0$$ $$\exists \overline{θ_ε} \in [0,1]$$ такое, что \begin{gather*} \langle f''(x + εh)εh, εh\rangle \geqslant 0. \end{gather*} Делим обе части этого равенства на $$ε^2 > 0$$ при $$ε \to 0+$$ получаем $$\langle f''(x)h, h\rangle \geqslant 0$$ $$\forall h \in X$$, что и доказывает $$\eqref{eq3}$$, Достаточность. Пусть выполняется $$\eqref{eq3}$$. Зафиксируем произвольные $$x, y \in X$$. Рассматриваем скалярную функцию $$φ(\alpha) = \langle f'(x + \alpha(y-x)), y-x\rangle$$, $$\alpha \in [0,1]$$. Применяя к этой функции формулу конечных приращений Лагранжа, получаем, что $$\exists θ \in [0, 1]$$, что \begin{gather*} \langle f'(y) - f'(x), y-x\rangle = \langle f''(x + θ(y-x))(y-x) - f'(x), y-x\rangle\geqslant 0. \end{gather*} Пусть $$\lambda \in [0, 1]$$. Положим $$z = \lambda x + (1- \lambda)y$$. Тогда $$x-z = (1-\lambda)(x-y)$$, $$y-z = \lambda(y-x)$$. В силу формулы Ньютона - Лейбница имеем \begin{gather*} λf(x) + (1-λ)f(y) - f(λx + (1-λ)y) = λ(f*x( - f(z)) + (1-λ)(f(y) - f(z)) = \\ = λ \int_0^1 \langle f'(z + t(x-z)), x-z\rangle dt + (1-λ)\int_0^1 \langle f'(z + t(y-z)), y-z\rangle dt = \\ = λ(1-λ)\int_0^1 \langle f'(z + t(x-z)) - f'(z + t(y-z)), x-y\rangle dt. \end{gather*} Сделаем замену $$u = z + t(x-z)$$, $$v = z+t(y-z)$$. В силу $$\eqref{eq3}$$ \begin{gather*} \langle f'(u) - f'(v), u-v\rangle \geqslant 0. \end{gather*} Отсюда получаем: \begin{gather*} \langle f'(z+t(x-z)) - f'(z + t(y-z)), x-y\rangle = \geqslant 0 \; \forall t \in [0,1] \end{gather*} и, следовательно, $$λf(x) + (1-λ)f(y) - f(λx + (1-λ)y) \geqslant 0$$, что завершает доказательство выпуклости функции $$f$$. $$\blacksquare$$

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


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

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

Будем считать, что $$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.