Выпуклые функции

Определения

Будем рассматривать отрезок [math][a; b][/math], набор чисел [math]x_1, x_2, x_3, \ldots x_n \in [a; b][/math] и коэффициенты [math]\alpha_1, \alpha_2, \ldots, \alpha_n \ge 0[/math] такие, что [math]\sum\limits_{i = 1}^n \alpha_i = 1[/math].

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

Выпуклая комбинация чисел [math]x_k[/math] — это [math]\bar x = \sum\limits_{i = 1}^n \alpha_kx_k[/math]

Частный случай — [math]\alpha_k = \frac1n[/math]. В этом случае [math]\bar x[/math] — среднее арифметическое.

Обозначим за [math]x_* = \min \{x_1; x_2; \ldots x_n \}[/math], а [math]x^* = \max \{x_1; x_2; \ldots x_n \}[/math]. Тогда [math]x_* \leq \bar x \leq x^*[/math], а так как [math]x_* \in [a; b][/math] и [math]x^* \in [a; b]$, то $\bar x \in [a; b][/math].

В этом смысле отрезок — выпуклое множество, так как он содержит выпуклую комбинацию любых своих чисел.

(типа определение) Выпуклое множество вместе с парой своих точек содержит отрезок, их соединяющий.

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

Пусть [math]f(x)[/math] задана на [math][a; b][/math]. Тогда она выпукла вверх на этом отрезке, если [math]\forall x_1, x_2 \in [a; b] \forall \alpha \in [0; 1] \quad \alpha f(x_1) + (1 - \alpha) f(x_2) \leq f(\alpha x_1 + (1 - \alpha)x_2)[/math]. Если же всё время неравенство противоположно, то функция называется выпуклой вниз.

В силу того, что было сказано о выпуклой комбинации, определение корректно: [math]\alpha x_1 + (1 - \alpha)x_2 \in [a; b][/math].

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

Замечание: если [math]f(x)[/math] выпукла вниз, то [math]-f(x)[/math] выпукла вверх.

Неравенство Йенсена

Теорема (Неравенство Йенсена):

Пусть [math]f(x)[/math] выпукла вверх на [math][a; b][/math]. Тогда [math]\forall x_1, x_2 \ldots x_n \in [a; b][/math] и их выпуклой комбинации выполнено неравенство [math]\sum\limits_{k = 1}^n \alpha_k f(x_k) \leq f\left(\sum\limits_{k = 1}^n \alpha_k x_k\right)[/math].

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

[math]\triangleright[/math]

Докажем по индукции. База: [math]n = 2[/math]. Неравенство превращается в определение выпуклой вверх функции, для которой это, очевидно, выполняется. Переход. Пусть это верно для [math]n[/math]. Докажем, что это верно для [math]n + 1[/math]: [math]\sum\limits_{k = 1}^{n + 1} \alpha_k = 1[/math], обозначим за [math]s_n = \sum\limits_{k = 1}^n \alpha_k[/math] Пусть [math]\beta_k = \frac{\alpha_k}{s_n}[/math]. Тогда получаем: [math]\sum\limits_{k = 1}^{n} \beta_k = 1[/math]. [math] \sum\limits_{k = 1}^{n + 1} \alpha_k f(x_k) = s_n \sum\limits_{k = 1}^n \beta_k f(x_k) + \alpha_{n + 1}f(x_{n + 1}) \leq[/math] (по предположению индукции) [math] s_n f\left(\sum\limits_{k = 1}^n \beta_k x_k \right) + \alpha_{n + 1}f(x_{n + 1}) \leq [/math] (так как [math]s_n + \alpha_{n + 1} = 1[/math]) [math] f\left(\sum\limits_{k = 1}^{n + 1} \alpha_k x_k\right)[/math] Значит, шаг индукции проделан, неравенство доказано для произвольного [math]n[/math].

[math]\triangleleft[/math]

Связь выпуклости и дифференцируемости

Применим линейную интерполяцию (в случае [math]2[/math] узлов) чтобы выяснить связь между выпуклостью и дифференцируемостью функции [math]f[/math]. Будем считать, что [math]f[/math] дифференцируема столько раз, сколько нам нужно. Имея [math]2[/math] узла на [math]\langle a; b\rangle[/math] и [math]y_0 = f(x_0)[/math], [math]y_1 = f(x_1)[/math], составим [math]L_n(x)[/math]:

[math]L_n(x) = y_0 \frac{x - x_1}{x_0 - x_1} + y_1\frac{x - x_0}{x_1 - x_0}[/math] — прямая, проходящая через точки [math](x_0, y_0)[/math] и [math](x_1, y_1)[/math]. Значит, между [math]x_0[/math] и [math]x_1[/math] получаем хорду, соединяющую две точки графика.

В вопросе о выпуклости надо проверять знак такой разности: [math]f(x) - L_n(x) = \frac{f^{(2)}(c_x)}{2!}(x - x_0)(x - x_1)[/math], [math]x_0 \leq x \leq x_1[/math].

Если [math]f^{(2)} \leq 0[/math] на [math]\langle a; b\rangle[/math] то правая часть будет неотрицательная, так как [math]x \in [x_0; x_1][/math], поэтому [math]f(x) - L_n(x) \geq 0[/math], и т. к. [math]x_0[/math] и [math]x_1[/math] произвольны, то [math]f[/math] выпукла вверх.

Итак, [math]f^{(2)} \leq 0 \Rightarrow f [/math] — выпукла вверх.

Пусть [math]f[/math] выпукла вверх. Будем считать, что [math]f^{(2)}[/math] — непрерывна. [math]x \in \langle a; b\rangle[/math].

Пусть [math]x_0 = x - \Delta x[/math], [math]x_1 = x + \Delta x[/math], где [math]\Delta x[/math] — малое положительное число. Рассмотрим полином Лагранжа [math]L_n[/math] для системы узлов [math](x_0, x_1)[/math] :

[math]f(t) - L_n(t) = \frac{f^{(2)}(c_t)}{2!} (t - x_0)(t - x_1) \geq 0, \, (t - x_0)(t - x_1) \lt 0 \Rightarrow f^{(2)}(c_t) \leq 0[/math]

[math]c_t \in \langle x - \Delta x; x + \Delta x \rangle[/math]

[math]\Delta x \to 0 : c_t \to x : f^{(2)}(x) \leq 0[/math]

Итак, если [math]f[/math] выпукла вверх, то [math]f^{(2)} \leq 0[/math].

Пример

В качестве примера рассмотрим [math]y = \ln x[/math], [math]y'' = \frac{-1}{x^2} \leq 0 \Rightarrow \ln x[/math] выпукла вверх. Это мы применим в следующем параграфе.