\documentclass[a4paper,draft,oneside]{amsbook} \usepackage{amsmath,amsthm,array} \usepackage[T2A]{fontenc} \usepackage[cp1251]{inputenc} \usepackage[english,russian]{babel} \usepackage{amsfonts} \usepackage{latexsym} %\usepackage[final]{hyperref} \tolerance 5200 \renewcommand*{\proofname}{Доказательство} \newcommand*{\ld}{L_2(\mathbb R^d)} \newcommand*{\Rd}{\mathbb R^d} \newcommand*{\RR}{\mathbb R} \newcommand*{\lf}{L_2^{\varphi}(\mathbb R^d)} \newcommand*{\cd}{(\cdot)} \newcommand*{\Ds}{\Delta_\sigma} \newcommand*{\lT}{L_2([0,2\pi])} \newcommand*{\wa}{\widehat\alpha} \newcommand*{\wb}{\widetilde b} \newcommand*{\wix}{\widetilde x} \newcommand*{\wiy}{\widetilde y} \newcommand*{\wal}{\widetilde\alpha} \newcommand*{\ws}{\widehat\sigma} \newcommand*{\wxi}{\widehat\xi} \newcommand*{\wm}{\widehat m} \newcommand*{\wx}{\widehat x} \newcommand*{\wz}{\widehat z} \newcommand*{\wu}{\widehat u} \newcommand*{\wL}{\widehat L} \newcommand*{\wJ}{\widehat J} \newcommand*{\wh}{\widehat h} %\newcommand*{\co}{\rm co} \newcommand*{\cone}{\rm cone} \newcommand*{\wy}{\widehat y} \newcommand*{\why}{\widehat y} \newcommand*{\wpp}{\widehat p} \newcommand*{\wl}{\widehat l} \newcommand*{\ov}{\overline} \newcommand*{\wt}{\widehat\tau} \newcommand*{\wv}{\widehat\varphi} \newcommand*{\wM}{\widehat M} \newcommand*{\Wt}{W_2^2([0,2\pi])} \newcommand*{\wf}{\widehat f} %\newcommand*{\intt}{\rm int} %\newcommand*{\cl}{\rm cl} %\newcommand*{\spa}{\rm span} \newcommand*{\la}{\langle} \newcommand*{\ra}{\rangle} \newcommand*{\LL}{\mathcal L} \newcommand*{\sjn}{\sum_{j=1}^n} \renewcommand{\labelenumi}{\theenumi.} \newcommand*{\wwa}{\widehat a} {\theoremstyle{remark}\newtheorem{example}{\bf Пример}[section]} \newtheorem{lemma}{Лемма} \newtheorem{theorem}{Теорема} \newtheorem{corollary}{Следствие} \newtheorem{proposition}{Предложение} \DeclareMathOperator*{\extr}{extr} \DeclareMathOperator*{\infp}{inf\vphantom p} \DeclareMathOperator*{\intt}{int} \DeclareMathOperator*{\cl}{cl} \DeclareMathOperator*{\spa}{span} \DeclareMathOperator*{\co}{co} \DeclareMathOperator*{\dom}{dom} \DeclareMathOperator*{\epi}{epi} \DeclareMathOperator*{\IM}{Im} \DeclareMathOperator*{\Ker}{Ker} \DeclareMathOperator*{\const}{const} \DeclareMathOperator*{\aff}{aff} \DeclareMathOperator*{\sign}{sign} \DeclareMathOperator*{\con}{cone} \DeclareMathOperator*{\lin}{lin} \DeclareMathOperator*{\rg}{rg} \DeclareMathOperator*{\ri}{ri} \begin{document} \title[Выпуклый анализ]{Выпуклый анализ} \author{К.~Ю.~Осипенко} \maketitle \tableofcontents \newpage \section*{Предисловие} Курс выпуклого анализа читается студентам третьего курса факультета управления и прикладной математики МФТИ в осеннем семестре. Он является первой частью курса оптимизации, который продолжает читаться в последующих семестрах. Свойство выпуклости позволяет проще решать оптимизационные задачи. Этим объясняется появление этой темы в самом начале рассмотрения задач оптимизации. Более того, на примере выпуклых задач ярко демонстрируется принцип двойственности, при котором каждой оптимизационной задаче ставится в соответствие некоторая другая, называемая двойственной. Рассмотрение совместно этих двух задач позволяет глубже изучить их свойства и получить решения, как правило, и той, и другой. Оптимизационные выпуклые задачи находят много применений на практике, в частности, в экономике. Поэтому в читаемом курсе уделяется достаточно внимания задачам линейного программирования. В основе предлагаемого пособия лежат лекции, который автор читал на механико-математическом факультете МГУ и на факультете управления и прикладной математики МФТИ. Автор существенно использовал в пособии книги своих коллег Г.~Г.~Магарил-Ильяева, В.~М.~Тихомирова \cite{MT} и Э.~М.~Галеева \cite{G}, которым автор глубоко благодарен за ценные обсуждения и советы. \chapter{Общая теория} \section{Введение} Выпуклый анализ --- раздел математики, в котором изучаются выпуклые множества, выпуклые функции и выпуклые экстремальные задачи. Выпуклый анализ имеет весьма разнообразные приложения в технике и экономике. Многие приложения связаны с задачами оптимизации, которые при наличии выпуклости могут решаться более просто. Пристальное внимание к выпуклости было привлечено в сороковых годах прошлого столетия. Оно было связано с появлением такого раздела, как линейное программирование. Первые нетривиальные задачи в этом направлении были решены Леонидом Витальевичем Канторовмчем. В 1939 году вышла его книга ``Математические методы организации и планирования производства''. Затем в пятидесятых годах мощное развитие линейного программирования, а потом и выпуклой оптимизации началось в США. Это было вызвано проблемами экономики и различными приложениями в военных областях. В 1975 году Канторовичу и Купмансу (американскому экономисту) была присуждена Нобелевская премия по экономике за вклад в теорию оптимального распределения ресурсов. Следует упомянуть американского математика-прикладника Данцига, которому принадлежит замечательный алгоритм решения задач линейного программирования, называемый симплекс-метод. В 1970 году американский математик Рокафеллар опубликовал монографию, которая называлась ``Выпуклый анализ''. Тогда впервые и появилось это словосочетание. Сам Рокафеллар пишет, что это название предложил ему профессор Принстонского университета Таккер. С тех пор термин ``выпуклый анализ'' стал общеупотребительным. \section{Выпуклые множества} Пусть $X$ --- линейное пространство. Если $x,y\in X$, то множество $$[x,y]=\{\,z\in X:z=(1-\alpha)x+\alpha y,\ 0\le\alpha\le1\,\}$$ называется {\it отрезком\/} (соединяющим точки $x$ и $y$). Непустое множество $A$ называется {\it выпуклым,} если для любых $x,y\in A$ \ $[x,y]\in A$. Пустое множество считается выпуклым по определению. Пусть $x_1,\ldots,x_n\in X$. Точка \begin{equation}\label{xx} x=\sjn\alpha_jx_j,\quad\alpha_j\ge0,\quad\sjn\alpha_j=1, \end{equation} называется {\it выпуклой комбинацией точек\/} $x_1,\ldots,x_n$. \begin{proposition}\label{P1} Если $A$ --- выпуклое множество, то любая выпуклая комбинация точек $x_1,\ldots,x_n\in A$ принадлежит $A$. \end{proposition} \begin{proof} Доказательство проведем индукцией по числу точек. При $n=1$ утверждение очевидно. Предположим, что утверждение верно для любой выпуклой комбинации из не более, чем $n-1$ точек. Пусть имеется точка $x$ вида \eqref{xx}. Если $\alpha_1=1$, то $x=x_1\in A$. Если $\alpha_1<1$, положим $$\wal_j=\frac{\alpha_j}{1-\alpha_1},\quad j=2,\ldots,n.$$ В силу того, что $$\sum_{j=2}^n\wal_j=1,$$ из предположения индукции вытекает, что $$\wix=\sum_{j=2}^n\wal_jx_j\in A.$$ Тогда из выпуклости $A$ следует, что $$x=\sjn\alpha_jx_j=\alpha_1x_1+(1-\alpha_1)\sum_{j=2}^n \frac{\alpha_j}{1-\alpha_1}x_j=\alpha_1x_1+(1-\alpha_1)\wix\in A.$$ \end{proof} {\it Выпуклой оболочкой\/} $\co A$ {\it множества\/} $A\subset X$ называется множество всех выпуклых комбинаций его точек \begin{multline*} \co A=\biggl\{\,x\in X:x=\sjn\alpha_jx_j,\ x_1,\ldots,x_n\in A,\ \alpha_j\ge0,\\ \sjn\alpha_j=1,\ n\in\mathbb N\,\biggr\}. \end{multline*} Среди всех выпуклых множеств, содержащих данное множество $A\subset X$, существует наименьшее, т.е. то, которое содержится в любом выпуклом множестве, содержащем $A$. Действительно, семейство всех выпуклых множеств, содержащих $A$, не пусто (в него входит, например, все пространство $X$). Пересечение всех множеств этого семейства будет выпуклым (т.к. пересечение любого семейства выпуклых множеств --- выпукло), содержащим $A$ и наименьшим. Докажем, что это множество совпадает с $\co A$. \begin{proposition} Множество $\co A$ является наименьшим выпуклым множеством, содержащим $A$. \end{proposition} \begin{proof} Из предложения~\ref{P1} вытекает, что если некоторое выпуклое множество содержит $A$, то оно содержит любую выпуклую комбинацию точек из $A$, а значит, оно содержит $\co A$. Следовательно, пересечение всех выпуклых множеств содержит $\co A$. Осталось показать что $\co A$ выпукло, в этом случае оно совпадет с пересечением всех выпуклых множеств, содержащих $A$. Рассмотрим две произвольные точки $\co A$ $$x=\sjn\alpha_jx_j,\quad y=\sum_{j=1}^m\beta_jy_j.$$ Для любого $\alpha\in[0,1]$ имеем $$(1-\alpha)x+\alpha y=\sjn(1-\alpha)\alpha_jx_j+\sum_{j=1}^m\alpha\beta_jy_j.$$ Так как $$\sjn(1-\alpha)\alpha_j+\sum_{j=1}^m\alpha\beta_j=(1-\alpha)+\alpha=1,$$ то мы получили выпуклую комбинацию точек $x_1,\ldots,x_n,y_1,\ldots,y_m$, которая принадлежит $\co A$. \end{proof} \begin{corollary} Множество $A$ является выпуклым в том и только в том случае, если $A=\co A$. \end{corollary} \begin{proposition}\label{P3} Если $A$ и $B$ --- выпуклые множества, то $$\co(A\cup B)=\{\,x\in X:x=(1-\alpha)a+\alpha b,\ a\in A,\ b\in B,\ \alpha\in[0,1]\,\}.$$ \end{proposition} \begin{proof} Из определения выпуклой оболочки вытекает, что $(1-\alpha)a+\alpha b\in\co(A\cup B)$ для всех $a\in A$, $b\in B$ и $\alpha\in[0,1]$. Пусть $x\in\co(A\cup B)$. Тогда $$x=\sjn\alpha_jx_j+\sum_{j=1}^m\beta_jy_j,$$ где $x_1,\ldots,x_n\in A$, $y_1,\ldots,y_m\in B$, $\alpha_1,\ldots,\alpha_n\ge0$, $\beta_1,\ldots,\beta_m\ge0$ и $$\sjn\alpha_j+\sum_{j=1}^m\beta_j=1.$$ Положим $$\alpha=\sum_{j=1}^m\beta_j.$$ Предположим, что $0<\alpha<1$. Тогда $x=(1-\alpha)a+\alpha b$, где $$a=\sjn\frac{\alpha_j}{1-\alpha}x_j,\quad b=\sum_{j=1}^m\frac{\beta_j}\alpha y_j.$$ В силу того, что $$\sjn\frac{\alpha_j}{1-\alpha}=\sum_{j=1}^m\frac{\beta_j}\alpha=1,$$ $a\in A$, а $b\in B$. При $\alpha=1$ или $\alpha=0$ можно непосредственно убедиться, что справедливо то же представление. \end{proof} \section{Аффинные подпространства} Подмножество $Y\subset X$ называется {\it аффинным подпространством\/} $X$, если для любых $x,y\in Y$ точка $(1-\alpha)x+\alpha y\in Y$ при всех $\alpha\in\mathbb R$. {\it Аффинной комбинацией точек\/} $x_1,\ldots,x_n$ называется точка \begin{equation}\label{xx1} x=\sjn\alpha_jx_j,\quad\sjn\alpha_j=1,\quad\alpha_1,\ldots,\alpha_n \in\mathbb R. \end{equation} \begin{proposition}\label{PA} Если $Y$ --- аффинное подпространство, то любая аффинная комбинация точек $x_1,\ldots,x_n\in Y$ принадлежит $Y$. \end{proposition} \begin{proof} Доказательство проведем индукцией по числу точек. При $n=1$ утверждение очевидно. Предположим, что утверждение верно для любой аффинной комбинации из не более, чем $n-1$ точек. Пусть имеется точка $x$ вида \eqref{xx1} и $n>1$. Среди $\alpha_1,\ldots,\alpha_n$ найдется отличное от единицы. Без ограничения общности можно считать, что $\alpha_1\ne1$. Положим $$\wal_j=\frac{\alpha_j}{1-\alpha_1},\quad j=2,\ldots,n.$$ В силу того, что $$\sum_{j=2}^n\wal_j=1,$$ из предположения индукции вытекает, что $$\wix=\sum_{j=2}^n\wal_jx_j\in Y.$$ Тогда из того, что $Y$ аффинное подпространство следует, что $$x=\sjn\alpha_jx_j=\alpha_1x_1+(1-\alpha_1)\wix\in Y.$$ \end{proof} Множество всех аффинных комбинаций точек из множества $A$ называется {\it аффинной оболочкой\/} $\aff A$ {\it множества\/} $A$ $$\aff A=\biggl\{\,x\in X:x=\sjn\alpha_jx_j,\ x_1,\ldots,x_n\in A,\ \sjn\alpha_j=1,\ n\in\mathbb N\,\biggr\}.$$ Среди всех аффинных подпространств, содержащих данное множество $A\subset X$, существует наименьшее, т.е. то, которое содержится в любом аффинном подпространстве, содержащем $A$. Действительно, семейство всех аффинных подпространств, содержащих $A$, не пусто (в него входит, например, все пространство $X$). Пересечение всех множеств этого семейства будет аффинным подпространством (т.к. пересечение любого семейства аффинных подпространств --- аффинное подпространство), содержащим $A$ и наименьшим. Докажем, что это множество совпадает с $\aff A$. \begin{proposition} Множество $\aff A$ является наименьшим аффинным подпространством, содержащим $A$. \end{proposition} \begin{proof} Из предложения~\ref{PA} вытекает, что если некоторое аффинное подпространство содержит $A$, то оно содержит любую аффинную комбинацию точек из $A$, а значит, оно содержит $\aff A$. Следовательно, пересечение всех аффинных подпространств содержит $\aff A$. Осталось показать что $\aff A$ является аффинным подпространством, в этом случае оно совпадет с пересечением всех аффинных подпространств, содержащих $A$. Рассмотрим две произвольные точки $\aff A$ $$x=\sjn\alpha_jx_j,\quad y=\sum_{j=1}^m\beta_jy_j.$$ Для любого $\alpha\in\mathbb R$ имеем $$(1-\alpha)x+\alpha y=\sjn(1-\alpha)\alpha_jx_j+\sum_{j=1}^m\alpha\beta_jy_j.$$ Так как $$\sjn(1-\alpha)\alpha_j+\sum_{j=1}^m\alpha\beta_j=(1-\alpha)+\alpha=1,$$ то мы получили аффинную комбинацию точек $x_1,\ldots,x_n,y_1,\ldots,y_m$, которая принадлежит $\aff A$. \end{proof} \begin{corollary} Множество $A$ является аффинным подпространством в том и только в том случае, если $A=\aff A$. \end{corollary} \begin{proposition}\label{P5} Каждое аффинное подпространство $Y\subset X$ представляется в виде $Y=a+L_Y$, где $a$ --- произвольная точка из $Y$, а $L_Y$ --- линейное подпространство из $X$, причем $L_Y$ определено однозначно (не зависит от $a$). \end{proposition} \begin{proof} Пусть $a\in Y$. Положим $$L_Y=\{\,x\in X:x=y-a,\quad y\in Y\,\}.$$ Докажем, что $L_Y$ --- линейное подпространство $X$. Пусть $x\in L_Y$. Тогда $x=y-a$, где $y\in Y$. Для любого $\lambda\in\mathbb R$ в силу того, что $\lambda y+(1-\lambda)a\in Y$, имеем $$\lambda x=\lambda(y-a)=\lambda y+(1-\lambda)a-a\in L_Y.$$ Пусть теперь $x_1,x_2\in L_Y$ и $x_1=y_1-a$, а $x_2=y_2-a$, где $y_1,y_2\in Y$. Так как $(y_1+y_2)/2\in Y$, то $$\frac{x_1+x_2}2=\frac{y_1+y_2}2-a\in L_Y.$$ Из доказанного выше, положив $\lambda=2$, получаем, что $x_1+x_2\in L_Y$. Положим $$M_Y=\{\,x\in X:x=y-b,\quad y\in Y\,\},$$ где $b\in Y$. В силу того, что $b-a\in L_Y$, имеем $$b+L_Y=a+(b-a)+L_Y=a+L_Y=Y.$$ Следовательно, $M_Y=L_Y$. \end{proof} {\it Размерностью аффинного подпространства\/} $Y$ называется размерность соответствующего линейного подпространства $L_Y$: $$\dim Y=\dim L_Y.$$ {\it Размерностью произвольного множества\/} $A$ называется размерность его аффинной оболочки $\aff A$: $$\dim A=\dim\aff A.$$ Поскольку $\co A\subset\aff A$, то $$\dim A=\dim\co A=\dim\aff A.$$ \section{Теорема Каратеодори} \begin{theorem}[Каратеодори] Если $\dim\co A=d$, то любой элемент множества $\co A$ представляется в виде выпуклой комбинации не более, чем $d+1$ элемента множества $A$. \end{theorem} \begin{proof} Положим $Y=\aff A$. Тогда $\dim Y=d$. Пусть $$x=\sjn\alpha_jx_j,\quad\alpha_j\ge0,\quad\sjn\alpha_j=1,\quad n\ge d+2,\quad x_j\in A.$$ Тогда элементы $x_2-x_1,\ldots,x_n-x_1$ принадлежат линейному пространству $L_Y$ (см. предложение~\ref{P5}), размерность которого $d$. Следовательно, они линейно зависимы. Тем самым существуют $\beta_2,\ldots,\beta_n$, не все равные нулю, для которых $$\sum_{j=2}^n\beta_j(x_j-x_1)=0.$$ Положим $$\gamma_1=-\sum_{j=2}^n\beta_j,\quad\gamma_j=\beta_j,\quad j=2,\ldots,n.$$ Тогда $$\sjn\gamma_jx_j=0,\quad\sjn\gamma_j=0,$$ причем $\gamma_1,\ldots,\gamma_n$ не все равны нулю. Следовательно, среди чисел $\gamma_1,\ldots,\gamma_n$ существуют отрицательные числа. Пусть $$a=\min\left\{\,-\frac{\alpha_j}{\gamma_j}:\gamma_j<0\,\right\}= -\frac{\alpha_k}{\gamma_k}.$$ Тогда $\alpha_j+a\gamma_j\ge0$ для всех $j=1,\ldots,n$. Кроме того, $$x=\sjn(\alpha_j+a\gamma_j)x_j,\quad\sjn(\alpha_j+a\gamma_j)=1.$$ Так как $\alpha_k+a\gamma_k=0$, то $x$ представляется в виде выпуклой комбинации из $n-1$ точки. Если $n-1>d+1$, то продолжая этот процесс придем к тому, что $x$ представляется в виде выпуклой комбинации не более, чем $d+1$ элемента множества $A$. \end{proof} Пусть $X$ --- линейное нормированное пространство. \begin{theorem} Выпуклая оболочка компакта в конечномерном пространстве $X$ является компактом. \end{theorem} \begin{proof} Пусть $\dim X=d$, $A\subset X$ --- компакт. Докажем, что $\co A$ --- компакт. Для этого достаточно доказать, что из любой последовательности $\{x_k\}\subset\co A$ можно выбрать подпоследовательность, сходящуюся к некоторой точке из $\co A$. По теореме Каратеодори $$x_k=\sum_{j=1}^{d+1}\alpha_{kj}x_{kj},\quad x_{kj}\in A,\quad\alpha_{kj}\ge0,\quad\sum_{j=1}^{d+1}\alpha_{kj}=1.$$ Так как $A$ --- компакт, то в последовательности $\{x_{k1}\}$ существует подпоследовательность, сходящаяся к некоторой точке $y_1\in A$, а в этой подпоследовательности в $\{\alpha_{k1}\}$ существует подпоследовательность, сходящаяся к некоторому числу $\alpha_1\in[0,1]$. Не ограничивая общности, можно считать, что $x_{k1}\to y_1$ и $\alpha_{k1}\to\alpha_1$ при $k\to\infty$. Аналогично, переходя к подпоследовательностям, можно считать, что $x_{kj}\to y_j$ и $\alpha_{kj}\to\alpha_j$ при $k\to\infty$ для любого $j=2,\ldots,d+1$. При этом $$x_k\to\sum_{j=1}^{d+1}\alpha_jy_j,\quad\alpha_j\ge0,\quad \sum_{j=1}^{d+1}\alpha_j=1.$$ Это означает, что предельная точка принадлежит $\co A$. \end{proof} {\it Конической комбинацией точек\/} $x_1,\ldots,x_n$ называется точка $$x=\sjn\alpha_jx_j,\quad\alpha_1,\ldots,\alpha_n\ge0.$$ Множество всех конических комбинаций точек из множества $A$ называется {\it конической оболочкой\/} $\con A$ {\it множества\/} $A$ $$\con A=\biggl\{\,x\in X:x=\sjn\alpha_jx_j,\ x_1,\ldots,x_n\in A,\ \alpha_j\ge0,\ n\in\mathbb N\,\biggr\}.$$ Напомним, что {\it линейной оболочкой множества\/} $A$ называется множество всех линейных комбинаций элементов из множества $A$: $$\lin A=\biggl\{\,x\in X:x=\sjn\alpha_jx_j,\ x_1,\ldots,x_n\in A,\ \alpha_j\in\mathbb R,\ n\in\mathbb N\,\biggr\}.$$ \begin{theorem}[Каратеодори для конической оболочки]\label{Kcone} Если $\dim\lin A=d$, то любой элемент множества $\con A$ представляется в виде конической комбинации не более, чем $d$ линейно независимых элементов множества $A$. \end{theorem} \begin{proof} Пусть $$x=\sjn\alpha_jx_j,\quad\alpha_1,\ldots,\alpha_n\ge0.$$ Если $x_1,\ldots,x_n$ линейно независимы, то $n\le d$ и все доказано. Если элементы $x_1,\ldots,x_n$ линейно зависимы, то найдутся не все равные нулю $\gamma_1,\ldots,\gamma_n$ такие, что $$\sjn\gamma_jx_j=0.$$ Без ограничения общности можно считать, что среди $\gamma_1,\ldots,\gamma_n$ есть отрицательные числа (если они все положительные, то можно рассматривать $-\gamma_1,\ldots,-\gamma_n$). Пусть $$a=\min\left\{\,-\frac{\alpha_j}{\gamma_j}:\gamma_j<0\,\right\}= -\frac{\alpha_k}{\gamma_k}.$$ Тогда $\alpha_j+a\gamma_j\ge0$ для всех $j=1,\ldots,n$ и $$x=\sjn(\alpha_j+a\gamma_j)x_j.$$ Так как $\alpha_k+a\gamma_k=0$, то $x$ представляется в виде конической комбинации из $n-1$ точки. Если эти элементы линейно зависимы, то продолжая этот процесс придем к тому, что $x$ представляется в виде конической комбинации не более, чем $d$ линейно независимых элементов множества $A$. \end{proof} \section{Теоремы Радона и Хелли} \begin{theorem}[Радона] Пусть $X$ --- линейное пространство и $\dim X=d$. Тогда любое конечное множество из $X$, содержащее не менее $d+2$ точек, может быть разбито на два непересекающихся множества, выпуклые оболочки которых пересекаются. \end{theorem} \begin{proof} Пусть даны точки $x_1,\ldots,x_n$, $n\ge d+2$. Векторы $x_2-x_1,\ldots,x_n-x_1$ --- линейно зависимы, т.к. их не менее $d+1$. Следовательно, существуют $\alpha_2,\ldots,\alpha_n$, не все равные нулю, такие, что $$\sum_{j=2}^n\alpha_j(x_j-x_1)=0.$$ Положим $$\beta_1=-\sum_{j=2}^n\alpha_j,\quad\beta_j=\alpha_j,\quad j=2,\ldots,n.$$ Имеем $$\sjn\beta_jx_j=0,\quad\sjn\beta_j=0,$$ причем $\beta_1,\ldots,\beta_n$ не все равны нулю. Поменяем нумерацию и будем считать, что $\beta_1,\ldots,\beta_m\ge0$, а $\beta_{m+1},\ldots,\beta_n<0$. Положим $$\beta=\sum_{j=1}^m\beta_j=-\sum_{j=m+1}^n\beta_j,\quad A=\{x_1,\ldots,x_m\},\quad B=\{x_{m+1},\ldots,x_n\}.$$ Тогда \begin{equation}\label{vk} \sum_{j=1}^m\gamma_jx_j=\sum_{j=m+1}^n\gamma_jx_j, \end{equation} где $\gamma_j=\beta_j/\beta$, $j=1,\ldots,m$, и $\gamma_j=-\beta_j/\beta$, $j=m+1,\ldots,n$. Причем $$\sum_{j=1}^m\gamma_j=\sum_{j=m+1}^n\gamma_j=1.$$ Таким образом, выпуклая комбинация в левой части равенства \eqref{vk} лежит в $\co A$, а выпуклая комбинация в правой части равенства \eqref{vk} лежит в $\co B$. Тем самым $\co A\cap\co B\ne\emptyset$. \end{proof} \begin{theorem}[Хелли] \ $1$. Если $\dim X=d$ и в $X$ имеются $n\ge d+1$ выпуклых множеств, любые $d+1$ из которых имеют общую точку, то и все эти множества имеют общую точку. $2$. Пусть $X$ --- линейное нормированное пространство, $\dim X=d$, $\mathcal I$ --- некоторое бесконечное множество индексов и $\{A_\alpha\}_{\alpha\in\mathcal I}$ --- семейство замкнутых выпуклых подмножеств $X$, по крайней мере одно из которых компактно. Тогда если любое подсемейство из $d+1$ множеств имеет общую точку, то и все семейство имеет общую точку. \end{theorem} \begin{proof} 1. Будем доказывать утверждение индукцией по числу множеств $n$. При $n=d+1$ утверждение очевидно. Пусть $n\ge d+2$ и теорема доказана для любых $n-1$ выпуклых множеств. Обозначим данные множества через $A_j$, $j=1,\ldots,n$. Для каждого $k=1,\ldots,n$ возьмем произвольную точку $$x_k\in\bigcap_{\substack{j=1\\j\ne k}}^nA_j$$ (по предположению индукции эти пересечения не пусты). Так как $n\ge d+2$, то к точкам $x_1,\ldots,x_n$ применима теорема Радона. С возможной перенумерацией точек получаем, что существует натуральное число $m\le n-1$, для которого множества $\co\{x_1,\ldots,x_m\}$ и $\co\{x_{m+1},\ldots,x_n\}$ имеют общую точку $x$. Точка $x_j$ при всех $j=1,\ldots,m$ принадлежит каждому из множеств $A_{m+1},\ldots,A_n$. В силу выпуклости этих множеств каждое из них содержит $\co\{x_1,\ldots,x_m\}$. Следовательно, каждое из этих множеств содержит точку $x$. Аналогично доказывается, что каждое из множеств $A_1,\ldots,A_m$ содержит точку $x$. Тем самым доказано, что у всех множеств $A_1,\ldots,A_n$ имеется общая точка. 2. Пусть $A_{\alpha_0}$ --- компактное множество. Из 1 следует, что любое конечное семейство из множества замкнутых подмножеств $B_\alpha=A_\alpha\cap A_{\alpha_0}$, $\alpha\in\mathcal I$, содержащихся в $A_{\alpha_0}$ имеет общую точку. Предположим, что все семейство не имеет общей точки. Тогда множества $\{X\setminus B_\alpha\}_{\alpha\in\mathcal I}$ --- открытые и образуют покрытие компактного множества $A_{\alpha_0}$. В силу компактности из этого покрытия можно выбрать конечное покрытие $\{X\setminus B_\alpha\}_{\alpha\in\mathcal I_n}$. Но тогда конечное семейство $\{B_\alpha\}_{\alpha\in\mathcal I_n}$ не может иметь общей точки. Полученное противоречие доказывает утверждение 2. \end{proof} \section{Теоремы отделимости} Пусть $A$ и $B$ --- непустые подмножества нормированного пространства $X$. Говорят, что ненулевой функционал $x^*\in X^*$ {\it отделяет множества\/} $A$ {\it и\/} $B$, если $$\sup_{x\in A}\la x^*,x\ra\le\inf_{x\in B}\la x^*,x\ra.$$ Если неравенство строгое, то говорят, что $x^*$ {\it строго отделяет\/} $A$ {\it и\/} $B$. Пусть число $\gamma\in\mathbb R$ таково, что $$\sup_{x\in A}\la x^*,x\ra\le\gamma\le\inf_{x\in B}\la x^*,x\ra.$$ Тогда, геометрически, отделимость множеств $A$ и $B$ означает, что они расположены по разные стороны от гиперплоскости $$\{\,x\in X:\la x^*,x\ra=\gamma\,\}.$$ Пусть $X$ --- нормированное пространство, $\wx\in X$ и $r>0$. Положим $$B_r(\wx)=\{\,x\in X:\|x-\wx\|_X0$, что $B_\varepsilon(\wx)\subset A$. Множество внутренних точек $A$ обозначается через $\intt A$. Напомним формулировку первой теоремы отделимости (см. \cite[стр. 243]{KF}). \begin{theorem}[Первая теорема отделимости]\label{FTO} Пусть $A$ и $B$ --- непустые выпуклые подмножества нормированного пространства $X$, причем $\intt A\ne\emptyset$ и $B\cap\intt A=\emptyset$. Тогда множества $A$ и $B$ отделимы. \end{theorem} Отсюда следует \begin{theorem}[Вторая теорема отделимости] Пусть $A$ --- непустое замкнутое выпуклое подмножество нормированного пространства $X$ и $\wx\notin A$. Тогда множества $A$ и $\wx$ строго отделимы. \end{theorem} \begin{proof} Так как $A$ замкнуто, то дополнение к $A$ открыто и поэтому существует такое $r>0$, что открытый шар $B_r(\wx)$ не пересекается с $A$. Тогда по первой теореме отделимости существует ненулевой функционал $x^*\in X^*$ такой, что $$\sup_{x\in A}\la x^*,x\ra\le\inf_{x\in B_r(\wx)}\la x^*,x\ra.$$ Но $$\inf_{x\in B_r(\wx)}\la x^*,x\ra<\la x^*,\wx\ra,$$ так как ненулевой линейный непрерывный функционал не может достигать точной нижней грани во внутренней точке. Следовательно, множества $A$ и $\wx$ строго отделимы. \end{proof} \section{Вторая теорема отделимости в конечномерном случае} В этом разделе мы сформулируем и докажем теоремы отделимости в конечномерном случае. Начнем со второй теоремы отделимости. \begin{theorem}\label{sepf2} Пусть $A$ --- непустое замкнутое выпуклое подмножество $\mathbb R^d$ и $\wx\notin A$. Тогда множества $A$ и $\wx$ строго отделимы. \end{theorem} \begin{proof} Пусть $x_0\in A$. Положим $$A_0=\{\,x\in A:|x-\wx|\le|x_0-\wx|\,\}.$$ Функция $f(x)=|x-\wx|$ является непрерывной на ограниченном замкнутом множестве $A_0$ и, следовательно, по теореме Вейерштрасса достигает своего минимума в некоторой точке $\wwa$. Тем самым $\wwa$ --- ближайшая точка к $\wx$ из множества $A_0$, а значит, и из множества $A$. Положим $x^*=(\wwa-\wx)^T$ и рассмотрим гиперплоскость $x^*\cdot x=x^*\cdot\wwa$. Докажем, что эта гиперплоскость отделяет $\wx$ от $A$. Имеем $$x^*\cdot\wx=x^*\cdot(\wx-\wwa+\wwa)=-|x^*|^2+x^*\cdot\wwa0,\quad k=1,\ldots,d+1.$$ Пусть $e_1,\ldots,e_d$ --- стандартный базис в $\mathbb R^d$. Так как $a_2,\ldots,a_{d+1}$ --- линейно независимы, векторы стандартного базиса можно представить в виде $$e_j=\sum_{k=2}^{d+1}\alpha_{jk}a_k,\quad j=1,\ldots,d.$$ Выберем $\varepsilon>0$ достаточно малым так, чтобы $$\lambda_k-\varepsilon\sum_{j=1}^d|\alpha_{jk}|>0,\quad k=2,\ldots,d+1,$$ и $$\sum_{k=2}^{d+1}\biggl(\lambda_k+\varepsilon\sum_{j=1}^d|\alpha_{jk}|\biggr)<1.$$ Пусть $x$ --- произвольный вектор из $B_\varepsilon(0)$. Тогда его можно записать в виде $$x=\sum_{j=1}^dx_je_j=\sum_{j=1}^dx_j\sum_{k=2}^{d+1}\alpha_{jk}a_k= \sum_{k=2}^{d+1}\sum_{j=1}^dx_j\alpha_{jk}a_k,$$ где $|x_j|<\varepsilon$. Таким образом, $$x_0+x=\sum_{k=2}^{d+1}\biggl(\lambda_k+\sum_{j=1}^dx_j\alpha_{jk}\biggr)a_k= \sum_{k=2}^{d+1}\gamma_ka_k.$$ В силу выбора $\varepsilon$, имеем $$\gamma_k>0,\quad k=2,\ldots,d+1,\quad\sum_{k=2}^{d+1}\gamma_k<1.$$ Тем самым точка $x_0$ является внутренней точкой симплекса. \end{proof} \section[Относительная внутренность. Первая теорема отделимости]{Относительная внутренность. Первая теорема отделимости в конечномерном случае} Если рассмотреть отрезок на плоскости, то все его точки не являются внутренними, хотя ясно, что точки, отличные от концевых, обладают некоторыми свойствами, присущими внутренним точкам. Это наблюдение приводит к следующему понятию. Пусть $X$ --- линейное нормированное пространство и $A\subset X$. Точка $x\in A$ называется {\it относительно внутренней точкой множества\/} $A$, если существует $\varepsilon>0$ такое, что $B_\varepsilon(x)\cap\aff A\subset A$. Множество всех относительно внутренних точек $A$ называется {\it относительной внутренностью\/} $A$ и обозначается $\ri A$. \begin{proposition}\label{Prri} Пусть $A\subset\mathbb R^d$ --- непустое выпуклое множество. Тогда \begin{enumerate} \item[a)] $\ri A\ne\emptyset$; \item[b)] если $x_1\in\ri A$, а $x_2\in\cl A$, то все точки интервала $(x_1,x_2)$ принадлежат $\ri A$; \item[c)] $\ri A$ и $\cl A$ --- выпуклые множества и $\cl\ri A=\cl A$. \end{enumerate} \end{proposition} \begin{proof} a). Предположим сначала, что $\dim A=d$. Тогда утверждение непосредственно вытекает из предложения~\ref{Psim}. Если $\dim A=d_10$. Тогда \begin{multline*} y+B_\varepsilon(0)=(1-\alpha)x_1+\alpha x_2+B_\varepsilon(0)\subset(1-\alpha)x_1+\alpha(A+B_\varepsilon(0))+B_\varepsilon(0)\\ =(1-\alpha)(x_1+B_\gamma(0))+\alpha A, \end{multline*} где $\gamma=\varepsilon(1+\alpha)/(1-\alpha)$. В силу того, что $x_1\in\intt A$ для достаточно малых $\varepsilon>0$ \ $x_1+B_\gamma(0)\subset A$. Поэтому $$y+B_\varepsilon(0)\subset(1-\alpha)A+\alpha A=A.$$ c). Будем снова предполагать, что $\aff A=\mathbb R^d$. Выпуклость $\ri A$ непосредственно следует из b). Докажем выпуклость $\cl A$. Пусть $x_1,x_2\in\cl A$, а $x=(1-\alpha)x_1+\alpha x_2$. Для любого $\varepsilon>0$ $$(x_j+B_\varepsilon(0))\cap A\ne\emptyset,\quad j=1,2.$$ Пусть $\wx_j\in (x_j+B_\varepsilon(0))\cap A$, $j=1,2$. Положим $\wx=(1-\alpha)\wx_1+\alpha \wx_2$. Тогда $\wx\in A$. Кроме того, $$\wx\in(1-\alpha)(x_1+B_\varepsilon(0))+\alpha(x_1+B_\varepsilon(0))=x+B_\varepsilon(0).$$ Тем самым в любой окрестности точки $x$ есть точки из $A$. Следовательно, $x\in\cl A$. Включение $\cl\ri A\subset\cl A$ очевидно. Пусть $x\in\cl A$. Из a) следует, что существует $x_1\in\ri A$. Из b) вытекает, что $(x_1,x)\in\ri A$. Следовательно, $x\in\cl\ri A$. \end{proof} \begin{theorem}\label{FTOd} Пусть $A,B\subset\mathbb R^d$ --- непустые выпуклые множества и $\ri A\cap B=\emptyset$. Тогда $A$ и $B$ отделимы. \end{theorem} \begin{proof} Положим $C=\ri A-B$. Так как $\ri A$ --- выпуклое множество (предложение~\ref{Prri}, c)), то $C$ --- выпуклое множество и $0\notin C$. Предположим $0\notin\cl C$. Из предложения~\ref{Prri} (c)) вытекает, что $\cl C$ тоже выпуклое множество. Тогда по теореме~\ref{sepf2} существует вектор $x'\in(\mathbb R^d)'$ такой, что $x'\cdot x<0$ для всех $x\in\cl C$. Пусть теперь $0\in\cl C$. Возьмем произвольный вектор $x\in\ri C$ ($\ri C\ne\emptyset$ в силу предложения~\ref{Prri}, a)). Тогда для любого $\lambda>0$ вектор $-\lambda x\notin\cl C$. Действительно, в противном случае из предложения \ref{Prri} (b)) вытекало бы, что $$0=\frac\lambda{\lambda+1}x+\frac1{\lambda+1}(-\lambda x)\in\ri C\subset C.$$ Тем самым существует последовательность векторов $x_k\notin\cl C$ такая, что $x_k\to0$ при $k\to\infty$. По второй теореме отделимости эти векторы можно строго отделить от $\cl C$. Следовательно, существуют $x_k'\in(\mathbb R^d)'$, $x_k'\ne0$, $k\in\mathbb N$, такие, что \begin{equation}\label{sepx} x_k'\cdot x