‹-- Назад

Выпуклые множества и функции

Выше мы дали определение выпуклого множества: напомним, что множество $ {\Omega}\sbs\mathbb{R}^n$  -- выпуклое, если вместе с любыми двумя точками $ x^0,\ x^1\in{\Omega}$ множеству $ {\Omega}$ принадлежат все точки $ x^t$ отрезка, соединяющего в пространстве $ \mathbb{R}^n$ точку $ x^0$ с точкой $ x^1$ . Заметим, что отрезок, состоящий из точек $ x^t$ , можно параметризовать следующим образом: $ x^t={\gamma}(t)=x^0+t(x^1-x^0).$ Тогда при $ t=0$ будет получаться точка $ {\gamma}(0)=x^0$ , при $ t=1$  -- точка $ {\gamma}(t)=x^1$ , а при $ t\in(0;1)$  -- промежуточные точки отрезка, так что обозначения точек отрезка как $ x^t$ будут согласованы с обозначениями его концов.

На следующем рисунке изображены два множества на плоскости $ \mathbb{R}^2$ : одно выпуклое, а другое нет.

Рис.7.17.



Выпуклыми в пространстве $ \mathbb{R}^n$ являются, например, такие множества: всё пространство $ \mathbb{R}^n$ , его положительный октант $ \{x=(x_1;\dots;x_n):x_i>0,\ i=1,\dots,n\}$ и неотрицательный октант $ \mathbb{R}^n_+=\{x=(x_1;\dots;x_n):x_i\geqslant 0,\ i=1,\dots,n\}$ , любой шар, как открытый $ {B^{x^0}_r=\{x\in\mathbb{R}^n:\vert x-x^0\vert<r\}}$ , так и замкнутый $ \{x\in\mathbb{R}^n:\vert x-x^0\vert\leqslant r\}$ , любая гиперплоскость $ \Pi$ (заданная некоторым уравнением вида $ c_1x_1+\dots+c_nx_n+d=0$ , а также открытое и замкнутое полупространства, заданные, соответственно, условиями $ c_1x_1+\dots+c_nx_n+d>0$ и $ c_1x_1+\dots+c_nx_n+d\geqslant 0$ .

        Упражнение 7.8   Докажите утверждения о выпуклости всех перечисленных множеств.     

Заметим также, что, согласно определению, выпуклы также все одноточечные множества $ \{x^0\}$ и пустое множество $ \varnothing $ .

        Теорема 7.15   Если все множества $ {\Omega}_{{\alpha}}\sbs\mathbb{R}^n$ некоторого семейства $ \{{\Omega}_{{\alpha}}\}$ выпуклы, то выпукло и их пересечение

$\displaystyle {\Omega}=\bigcap_{{\alpha}}{\Omega}_{{\alpha}}.$

        Доказательство.     Пусть точки $ x^0$ и $ x^1$ принадлежат $ {\Omega}$ ; тогда обе они принадлежат каждому из множеств $ {\Omega}_{{\alpha}}$ . Значит, если $ x^t$  -- произвольная точка отрезка, соединяющего $ x^0$ и $ x^1$ , то она принадлежит $ {\Omega}_{{\alpha}}$ , поскольку $ {\Omega}_{{\alpha}}$ выпукло. Но так как $ x^t\in{\Omega}_{{\alpha}}$ для всех $ {\alpha}$ , то $ x^t\in\bigcap\limits_{{\alpha}}{\Omega}_{{\alpha}}={\Omega}$ , что и требовалось доказать.     

Из этой теоремы следует, например, что прямая в $ n$ -мерном пространстве (её можно задать как векторным уравнением: $ x=a+bt$ , где $ a,b\in\mathbb{R}^n$  -- фиксированные векторы, а $ t\in\mathbb{R}$  -- параметр, так и в виде пересечения гиперплоскостей $ \Pi_1,\dots,\Pi_{n-1}$ ) является выпуклым множеством. Действительно, каждая гиперплоскость $ \Pi_j$  -- выпуклое множество.

Проколотая окрестность любой точки $ x^*$ , то есть множество $ B^{x^*}_{{\delta}}\diagdown \{x^*\}$ ( $ {\delta}>0$ ), не является выпуклым. Чтобы показать это, достаточно выбрать любой ненулевой вектор $ d\in\mathbb{R}^n$ длины меньше $ {\delta}$ и рассмотреть точки проколотой окрестности $ x^0=x^*-d$ и $ x^1=x^*+d$ , расположенные симметрично относительно точки $ x^*$ . Тогда середина отрезка, соединяющего $ x^0$ с $ x^1$ , то есть точка $ x^{\frac{1}{2}}$ , совпадает с $ x^*$ и, следовательно, не лежит в проколотой окрестности точки $ x^*$ .

Если $ n=1$ , то есть речь идёт о подмножествах прямой $ \mathbb{R}=\mathbb{R}^1$ , то выпуклые множества можно описать полностью: это а) пустое множество; б) все одноточечные множества; в) все интервалы вида $ (a;b)$ (где $ a$ может равняться $ -\infty$ , а $ b$ может равняться $ +\infty$ ); г) все полуинтервалы вида $ (a;b]$ (где $ a$ может равняться $ -\infty$ ) и $ [a;b)$ (где $ b$ может равняться $ +\infty$ ); наконец, д) все отрезки вида $ [a;b]$ . Никаких других выпуклых множеств на прямой нет.

        Упражнение 7.9   Докажите утверждение о виде всех выпуклых множеств на прямой.     

Напомним изученное в первом семестре определение выпуклой функции одного вещественного переменного.

        Определение 7.12   Функция $ g(t)$ , заданная на отрезке $ [a;b]$ , называется выпуклой (или выпуклой книзу) на этом отрезке, если для всех $ t_0,t_1\in[a;b]$ и $ {\theta}\in[0;1]$ выполняется неравенство


и вогнутой (или выпуклой кверху), если выполняется неравенство


(То есть функция $ g(t)$ вогнута в том и только том случае, если функция $ -g(t)$ выпукла.)     

В левой части этого неравенства стоит значение функции $ g$ в производной точке

$\displaystyle t_{{\theta}}=(1-{\theta})t_0+{\theta}t_1=t_0+{\theta}(t_1-t_0)$

отрезка между $ t_0$ и $ t_1$ (будем для простоты считать, что $ t_0\leqslant t_1$ ), а в правой части неравенства -- значение линейной функции $ l(t)$ , такой что $ l(t_0)=g(t_0)$ и $ l(t_1)=g(t_1)$ (см. рис.).

Рис.7.18.



Если $ t_0=0$ и $ t_1=1$ , то неравенство, означающее выпуклость функции $ g(t)$ , превращается в такое:

$\displaystyle g({\theta})\leqslant (1-{\theta})g(0)+{\theta}g(1),$

при всех $ {\theta}\in[0;1]$ .

Дадим теперь определение выпуклой функции многих переменных.

        Определение 7.13   Пусть $ {\Omega}\sbs\mathbb{R}^n$  -- выпуклое множество, на котором задана функция $ f(x)$ . Функция $ f(x)$ называется выпуклой (или выпуклой книзу) на множестве $ {\Omega}$ , если для любых двух точек $ x^0,\ x^1\in{\Omega}$ функция $ g(t)=f(x^t)$ , служащая ограничением функции $ f(x)$ на отрезок, соединяющий точки $ x^0$ и $ x^1$ , является выпуклой (книзу) функцией одного переменного $ t\in[0;1]$ (здесь, как и выше, $ x^t=x^0+t(x^1-x^0)$ ).

Рис.7.19.



Функция $ f(x)$ называется вогнутой (или выпуклой кверху) в $ {\Omega}$ , если функция $ g(t)=f(x^t)$ вогнута.

Таким образом, функция $ f(x)$ вогнута в том и только том случае, когда функция $ -f(x)$ выпукла.     

Выпуклость функции $ f(x)$ в $ {\Omega}$ означает, что для любого отрезка $ I\sbs{\Omega}$ с концами $ x^0$ и $ x^1$ параметризация этого отрезка в виде $ {\gamma}(t)=x^t=x^0+t(x^1-x^0)=(1-t)x^0+tx^1$ задаёт композицию $ f({\gamma}(t))$ , являющуюся выпуклой функцией параметра $ t\in[0;1]$ . Ввиду выпуклости области $ {\Omega}$ , любые точки $ x^{{\theta}_0}$ и $ x^{{\theta}_1}$ отрезка $ I$ лежат в $ {\Omega}$ , и их снова можно взять в качестве концов отрезка. Поэтому для выпуклости функции $ f$ в области $ {\Omega}$ необходимо и достаточно, чтобы неравенство

$\displaystyle f((1-t)x^0+tx^1)\leqslant (1-t)f(x^0)+tf(x^1)$

выполнялось при всех $ x^0,\ x^1\in{\Omega}$ и $ t\in[0;1]$ .

Если при этом при всех $ x^0,\ x^1\in{\Omega}$ и $ t\in(0;1)$ выполняется строгое неравенство

$\displaystyle f((1-t)x^0+tx^1)<(1-t)f(x^0)+tf(x^1),$

то функцию $ f$ будем называть строго выпуклой в $ {\Omega}$ .

Наконец, функция $ f(x)$ называется строго вогнутой, если функция $ -f(x)$ строго выпукла; это означает выполнение строгого неравенства

$\displaystyle f((1-t)x^0+tx^1)>(1-t)f(x^0)+tf(x^1)$

при всех $ x^0,\ x^1\in{\Omega}$ и $ t\in(0;1)$ .

Геометрически (в случае $ n=2$ ) строгая выпуклость означает, что для любой хорды графика $ y=f(x)$ точки дуги графика с теми же концами, что у хорды, лежащие в вертикальном сечении, проходящем через эту хорду, располагаются ниже точек хорды. Строгая вогутость означает, что в любом вертикальном сечении график проходит выше любого отрезка, соединяющего две точки графика.

Рис.7.20.



Заметим, что понятия выпуклой и вогнутой функций (а также строго выпуклой и строго вогнутой функций) в области $ {\Omega}$ определены только для выпуклых областей $ {\Omega}$ .

Дадим теперь такое алгебраическое определение.

        Определение 7.14   Пусть дана квадратная матрица $ A$ размера $ n\times n$ . Она называется неотрицательно определённой, если $ Ax\cdot x\geqslant 0$ для любого вектора-столбца $ x\in\mathbb{R}^n$ (точкой обозначено скалярное произведение в $ \mathbb{R}^n$ ). Матрица $ A$ называется положительно определённой, если $ Ax\cdot x>0$ для всех $ x\ne0$ .     

Заметим, что выражение $ Ax\cdot x$ можно записать в виде $ {}^txAx$ , где $ {}^tx$  -- это матрица-строка, равная транспонированному столбцу $ x$ . Вообще, верхний левый индекс $ {}^t$ мы будем применять для обозначения транспонированной матрицы.

        Определение 7.15   Квадратная матрица $ A=(a_{ij})$ называется симметричной, если при всех $ i,j$ имеет место равенство $ a_{ij}=a_{ji}$ , то есть если $ {}^tA=A$ .     

У симметричной матрицы равны друг другу элементы, расположенные симметрично друг другу относительно главной диагонали матрицы.

        Теорема 7.16   Пусть $ A=(a_{ij})$  -- симметричная неотрицательно определённая матрица размера $ n\times n$ . Тогда квадратичная функция (она же называется квадратичной формой, заданной матрицей $ A$ )

$\displaystyle f_A(x)={}^txAx=\sum_{i=1}^n\sum_{j=1}^na_{ij}x_ix_j$

является выпуклой функцией (во всем пространстве, то есть при $ {\Omega}=\mathbb{R}^n$ ).

Если же симметричная матрица $ A$  -- положительно определённая, то заданная ею квадратичная форма $ f_A(x)$ является строго выпуклой.

        Доказательство.     Пусть $ x^0$ и $ x^1$  -- две произвольные точки $ \mathbb{R}^n$ и $ x^{{\theta}}=(1-{\theta})x^0+{\theta}x^1$ , где $ {\theta}\in[0;1]$ , -- точка отрезка, соединяющего $ x^0$ с $ x^1$ .

Предположим, что матрица $ A$ неотрицательно определена. Элементарные преобразования позволяют записать $ f_A(x^{{\theta}})$ в виде

$\displaystyle f_A(x^{{\theta}})=f_A((1-{\theta})x^0+{\theta}x^1)=
 {\theta}^2\;{}^tx^1Ax^1+2{\theta}(1-{\theta})\;{}^tx^1Ax^0+(1-{\theta})^2\;{}^tx^0Ax^0=$    
$\displaystyle =(1-{\theta})f_A(x^0)+{\theta}f_A(x^1)-{\theta}(1-{\theta})\;{}^t(x^1-x^0)A(x^1-x^0).$    

Поскольку матрица $ A$ неотрицательно определена, имеет место неравенство

$\displaystyle {}^t(x^1-x^0)A(x^1-x^0)\geqslant 0,$

откуда сразу следует, что

$\displaystyle (1-{\theta})f_A(x^0)+{\theta}f_A(x^1)\geqslant 0,$

а это неравенство означает выпуклость функции $ f_A$ .

Доказательство строгой выпуклости в случае положительно определённой матрицы проводится с помощью очевидных изменений приведённого доказательства.     

Другой пример выпуклой функции даёт линейная функция:

        Пример 7.21   Линейная функция

$\displaystyle l(x)=c_1x_1+c_2x_2+\ldots+c_nx_n+d,$

где $ c_1, c_2,\dots,c_n,d$  -- постоянные, является выпуклой функцией во всём пространстве $ \mathbb{R}^n$ (но не является строго выпуклой функцией). Действительно, как легко проверить, при всех $ x^0,x^1\in\mathbb{R}^n$ и $ {\theta}\in[0;1]$ имеем

$\displaystyle l(x^{{\theta}})=l((1-{\theta})x^0+{\theta}x^1)=(1-{\theta})l(x^0)+{\theta}l(x^1).$

Поскольку функция $ -l(x)$ , очевидно, также линейна, линейная функция $ l(x)$ является одновременно и вогнутой (но не строго вогнутой).     

Если о некоторых функциях известно, что они выпуклы в области $ {\Omega}$ , то из них можно сконструировать другие выпуклые функции, используя следующие свойства выпуклых функций.

        Теорема 7.17   Пусть $ {\Omega}$  -- выпуклая область и функции $ f(x)$ и $ g(x)$ выпуклы в $ {\Omega}$ . Тогда сумма этих функций $ h(x)=f(x)+g(x)$ также выпукла в $ {\Omega}$ .

        Доказательство.     Пусть $ x^0,\ x^1\in{\Omega}$ и $ x^{{\theta}}=(1-{\theta})x^0+{\theta}x^1$ , где $ {\theta}\in[0;1]$ . Тогда

$\displaystyle h(x^{{\theta}})=f(x^{{\theta}})+g(x^{{\theta}})\leqslant 
 (1-{\theta})f(x^0)+{\theta}f(x^1)+
 (1-{\theta})g(x^0)+{\theta}g(x^1)=$    
$\displaystyle =(1-{\theta})(f(x^0)+g(x^0))+{\theta}(f(x^1)+g(x^1))=(1-{\theta})h(x^0)+{\theta}h(x^1),$    

что и означает выпуклость функции $ h$ .     

Поскольку, как мы доказали выше, квадратичная функция $ f_A(x)$ с неотрицательно определённой матрицей $ A$ и линейная функция $ l(x)$ выпуклы, то и их сумма, согласно доказанному свойству, -- выпуклая функция. В качестве упражнения докажите, однако, ещё одно утверждение, не вытекающее из теоремы 7.17:

        Упражнение 7.10   Докажите, что если $ f_A(x)$  -- квадратичная форма, заданная симметричной положительно определённой матрицей $ A$ , а $ l(x)$  -- линейная функция, то функция $ Q(x)=f_A(x)+l(x)$ строго выпукла.

Указание: по сути дела, нужно повторить доказательство теоремы 7.16, с очевидными изменениями.     

        Теорема 7.18   Если функция $ f(x)$ выпукла в области $ {\Omega}$ , то функция $ f_+(x)$ , заданная в $ {\Omega}$ равенством

$\displaystyle f_+(x)=\max\{f(x);0\}=\left\{\begin{array}{ll}
f(x),&\text{ если }f(x)\geqslant 0;\\
0&\text{ если }f(x)\leqslant 0,
\end{array}\right.$

тоже выпукла в $ {\Omega}$ .

        Доказательство.     Пусть снова $ x^0,\ x^1\in{\Omega}$ и $ x^{{\theta}}=(1-{\theta})x^0+{\theta}x^1$ , где $ {\theta}\in[0;1]$ . Тогда

$\displaystyle f_+(x^{{\theta}})=\max\{f(x^{{\theta}});0\}\leqslant 
 \max\{(1-{\theta})f(x^0)+{\theta}f(x^1);0\}\leqslant$ (7.11*)
$\displaystyle \leqslant (1-{\theta})\max\{f(x^0);0\}+{\theta}\max\{f(x^1);0\}=
 (1-{\theta})f_+(x^0)+{\theta}f_+(x^1),$ (7.12)

что и означает выпуклость функции $ f_+$ . Первое неравенство в (7.11*) следует из того, что функция $ f$ выпукла, а второе -- из того, что при всех $ a,b$ имеет место неравенство:

$\displaystyle \max\{a+b;0\}\leqslant \max\{a;0\}+\max\{b;0\},$

а при всех $ {\lambda}\geqslant 0$  -- равенство

$\displaystyle \max\{{\lambda}a;0\}={\lambda}\max\{a;0\}.$

(Проверьте, что последние два утверждения действительно верны.)     

        Теорема 7.19   Если функция $ f(x)$ выпукла в области $ {\Omega}$ , то функция $ g(x)=f^2(x)$ также выпукла в $ {\Omega}$ .

        Доказательство.     Пусть снова $ x^0,\ x^1\in{\Omega}$ и $ x^{{\theta}}=(1-{\theta})x^0+{\theta}x^1$ , где $ {\theta}\in[0;1]$ . Тогда, ввиду того что $ g(x)=(f(x))^2\geqslant 0$ , получаем:

$\displaystyle g(x^{{\theta}})=(f(x^{{\theta}}))^2\leqslant 
 (1-{\theta})^2(f(x^0))^2+2{\theta}(1-{\theta})f(x^0)f(x^1)+{\theta}^2(f(x^1))^2=$    
$\displaystyle =(1-{\theta})(f(x^0))^2+{\theta}(f(x^1))^2-{\theta}(1-{\theta})(f(x^0)-f(x^1))^2\leqslant$    
$\displaystyle \leqslant (1-{\theta})(f(x^0))^2+{\theta}(f(x^1))^2=
 (1-{\theta})g(x^0)+{\theta}g(x^1).$    

Последнее неравенство следует из того, что $ {\theta}(1-{\theta})\geqslant 0$ при $ {\theta}\in[0;1]$ .     

Следующие три утверждения остаются читателю для самостоятельного доказательства в качестве упражнения.

        Теорема 7.20   Если функции $ f(x)$ и $ g(x)$ выпуклы в области $ {\Omega}$ и $ C_1\geqslant 0,\ C_2\geqslant 0$ , то функция $ h(x)=C_1f(x)+C_2g(x)$ также выпукла в $ {\Omega}$ .

Если функции $ f(x)$ и $ g(x)$ выпуклы в области $ {\Omega}$ , то функция $ h(x)=\max\{f(x);g(x)\}$ также выпукла в $ {\Omega}$ .

Если функция $ f(x)$ выпукла в области $ {\Omega}$ , а функция одного переменного $ {\varphi}(z)$ выпукла на интервале $ I\sbs\mathbb{R}_z$ , содержащем множество значений функции $ f(x)$ при всех $ x\in{\Omega}$ , и $ {\varphi}$ возрастает всюду на интервале $ I$ или убывает всюду на $ I$ , то композиция $ h(x)={\varphi}(f(x))$ выпукла в $ {\Omega}$ . (Например, если функция $ f(x)$ выпукла в $ {\Omega}$ , то функция $ h(x)=e^{f(x)}$ также будет выпуклой в $ {\Omega}$ .)     

Выпуклые функции интересны такой своей особенностью: они не могут иметь нескольких локальных минимумов с разными значениями.

Сначала дадим такое определение.

        Определение 7.16   Пусть $ {\Omega}$  -- некоторая область в $ \mathbb{R}^n$ .

Точка $ x^0\in{\Omega}$ называется точкой локального минимума функции $ f(x)$ , если существует такая окрестность $ B^{x^0}_{{\delta}}$ , $ {\delta}>0$ , что $ f(x)\geqslant f(x^0)$ при всех $ x\in B^{x^0}_{{\delta}}$ . Если при этом $ f(x)>f(x^0)$ при всех $ x\in B^{x^0}_{{\delta}}$ , не совпадающих с $ x^0$ , то точка $ x^0$ называется точкой строгого локального минимума. И в том и в другом случае значение $ f(x^0)$ называется локальным минимумом функции $ f(x)$ .

Точка $ x^0\in{\Omega}$ называется точкой локального максимума функции $ f(x)$ , если существует такая окрестность $ B^{x^0}_{{\delta}}$ , $ {\delta}>0$ , что $ f(x)\leqslant f(x^0)$ при всех $ x\in B^{x^0}_{{\delta}}$ . Если при этом $ f(x)<f(x^0)$ при всех $ x\in B^{x^0}_{{\delta}}$ , не совпадающих с $ x^0$ , то точка $ x^0$ называется точкой строгого локального максимума. И в том и в другом случае значение $ f(x^0)$ называется локальным максимумом функции $ f(x)$ .     

        Теорема 7.21   Любая точка локального минимума функции $ f(x)$ , выпуклой в области $ {\Omega}$ , даёт наименьшее значение функции $ f$ во всей области $ {\Omega}$ ;
любая точка локального максимума функции $ f(x)$ , выпуклой в области $ {\Omega}$ , даёт наибольшее значение функции $ f$ во всей области $ {\Omega}$ .

        Доказательство.     Очевидно, что достаточно доказать лишь первое утверждение: второе следует из него сменой знака функции.

Пусть $ x^0$  -- точка локального минимума, а в некоторой другой точке $ x^1$ функция имеет меньшее значение: $ f(x^1)<f(x^0)$ . Тогда в точках отрезка, соединяющего $ x^0$ с $ x^1$ , то есть точках $ x^{{\theta}}=(1-{\theta})x^0+{\theta}x^1$ , при всех $ {\theta}>0$ значения функции будут меньше, чем в точке $ x^0$ :

$\displaystyle f(x^{{\theta}})=f((1-{\theta})x^0+{\theta}x^1)\leqslant
(1-{\theta})f(x^0)+{\theta}f(x^1)<
(1-{\theta})f(x^0)+{\theta}f(x^0)=f(x^0).$

Но точки $ x^{{\theta}}$ с $ {\theta}>0$ имеются в любой, сколь угодно малой, окрестности точки $ x^0$ , что противоречит предположению о том, что $ x^0$  -- точка локального минимума. Значит, неравенство $ f(x^1)<f(x^0)$ невозможно, и $ f(x^1)\geqslant f(x^0)$ для любой точки $ x^1\in{\Omega}$ . Это означает, что значение функции в точке локального минимума $ x^0$  -- наименьшее во всей области $ {\Omega}$ .     

Практическая ценность этого утверждения в том, что при поиске наименьшего значения выпуклой функции в области $ {\Omega}$ достаточно найти любую точку локального минимума; во всех остальных точках локального минимуцма (если они существуют) значение функции будет точно такое же. Для невыпуклых функций это, конечно, не так, как видно на следующем рисунке:

Рис.7.21.



Имеет место также следующая

        Теорема 7.22   Eсли функция $ f(x)$ строго выпукла в области $ {\Omega}$ , то её точка минимума в $ {\Omega}$  -- единственная.

        Доказательство.     Пусть в двух разных точках $ x^0$ и $ x^1$ функция $ f(x)$ принимает одно и то же значение $ m=\min\limits_{x\in{\Omega}}f(x).$ Поскольку функция строго выпукла, то в точках $ x^{{\theta}}=(1-{\theta})x^0+{\theta}x^1$ , не совпадающих с $ x^0$ и с $ x^1$ , должно выполняться неравенство

$\displaystyle f(x^{{\theta}})<(1-{\theta})f(x^0)+{\theta}f(x^1)=(1-{\theta})m+{\theta}m=m.$

Но это означает, что в точках $ x^{{\theta}}$ , например, в середине отрезка $ x^{\frac{1}{2}}\in{\Omega}$ , значение меньше $ m$ , что противоречит предположению о том, что значение $ m$  -- наименьшее во всей области. Значит, второй точки $ x^1\ne x^0$ с тем же минимальным значением $ m$ нет.