машинное обучение. А. М. Миронов Московский Государственный Университет Механикоматематический факультет Кафедра математической теории интеллектуальных систем Введение Книга
 Скачать 1.05 Mb.
|
|
𝑚𝑖𝑛 𝑥 𝑖 𝑚𝑎𝑥 − 𝑥 𝑖 𝑚𝑖𝑛 или ˜ 𝑥 𝑖 := 𝑥 𝑖 − 𝑥 𝑖 𝑎𝑣𝑒𝑟𝑎𝑔𝑒 𝑥 𝑖 𝑎𝑣𝑠𝑞𝑢𝑎𝑟𝑒 где 𝑥 𝑖 𝑎𝑣𝑒𝑟𝑎𝑔𝑒 – среднее значение, 𝑥 𝑖 𝑎𝑣𝑠𝑞𝑢𝑎𝑟𝑒 – среднеквадратическое от- клонение (= √ дисперсии), ∙ добавление между слоями МНС промежуточных слоев, реализу- ющих линейные преобразования: если 𝑢 и 𝑣 – вектора входов и выходов такого слоя, то реализуемое этим слоем преобразование имеет вид 𝑣 = 𝐴𝑢 + 𝑏, где 𝐴 и 𝑏 – матрица и вектор соответству- ющих размерностей, коэффициенты матрицы 𝐴 и вектора 𝑏 тоже обучаются, ∙ изменение структуры МНС: удаление части нейронов (dropout). 2.5 Метод опорных векторов В этом параграфе излагается наиболее популярный метод машинного обучения – метод опорных векторов (Support Vector Machines, SVM), который был создан в 70-е годы прошлого века сотрудниками Института проблем управления АН СССР В. Н. Вапником и А. Я. Чер- воненкисом, и впервые опубликован в книге [8] (в которой он назван методом обобщенного портрета). Данный метод предназначен для решения задач классификации и регрессионного анализа. 2.5.1 Оптимальность аппроксимирующих функций В параграфе 2.2 рассматривалась задача нахождения по строго линейно разделимой выборке 𝑆 ⊆ R 𝑛 × {−1, 1} АФ 𝑎 𝑆 вида 𝑎 𝑆 (𝑥) = 𝑠𝑖𝑔𝑛 (︁ 𝑛 ∑︁ 𝑖=1 𝑥 𝑖 𝑤 𝑖 − 𝑤 0 )︁ такой, что 𝑄(𝑎 𝑆 ) = 0. Как было отмечено в этом параграфе, функция 𝑎 𝑆 данного вида обладает свойством 𝑄(𝑎 𝑆 ) = 0 тогда и только тогда, когда гиперплоскость 𝑃 , определяемая уравнением 𝑛 ∑︀ 𝑖=1 𝑥 𝑖 𝑤 𝑖 − 𝑤 0 = 0, разделяет 33 множества 𝑆 + и 𝑆 − , т.е. 𝑆 + и 𝑆 − содержатся в разных полупростран- ствах, на которые 𝑃 делит R 𝑛 Можно доказать, что задача построения разделяющей гиперплоско- сти для строго линейно разделимой выборки 𝑆 имеет бесконечно много решений. Например, несколько различных решений данной задачи изоб- ражено на нижеследующем рисунке (в данном случае 𝑛 = 2): где кружочки обозначают элементы 𝑆 + , а квадратики - элементы 𝑆 − Встает вопрос о том, можно ли ввести какие-либо меры оптимально- сти решений данной задачи. В качестве одной из мер оптимальности функции 𝑎 𝑆 указанного выше вида можно рассматривать, например, расстояние 𝜌(𝑆 + ∪ 𝑆 − , 𝑃 ) (2.35) между 𝑆 + ∪ 𝑆 − и 𝑃 . Напомним, что ∀ 𝐴, 𝐵 ⊆ R 𝑛 расстояние 𝜌(𝐴, 𝐵) между 𝐴 и 𝐵 определяется как inf 𝑎∈𝐴,𝑏∈𝐵 ||𝑎 − 𝑏||. Назовем полосой, разделяющей 𝑆 + и 𝑆 − , и определяемой гипер- плоскостью 𝑃 , часть пространства R 𝑛 , заключенную между гиперплос- костями 𝑃 𝑆 + и 𝑃 𝑆 − , которые получаются параллельным переносом ги- перплоскости 𝑃 вдоль вектора нормали к ней ∙ по направлению к 𝑆 + на расстояние 𝜌(𝑃, 𝑆 + ), и ∙ по направлению к 𝑆 − на расстояние 𝜌(𝑃, 𝑆 − ), соответственно. Будем обозначать эту полосу записью [𝑃 𝑆 + , 𝑃 𝑆 − ]. Нетруд- но видеть, что во внутренней части полосы [𝑃 𝑆 + , 𝑃 𝑆 − ] точек из 𝑆 + и 𝑆 − нет. Расстояние 𝜌(𝑃 𝑆 + , 𝑃 𝑆 − ) назовем шириной полосы [𝑃 𝑆 + , 𝑃 𝑆 − ]. Можно доказать, что (2.35) достигает максимального значения, когда ширина 34 полосы [𝑃 𝑆 + , 𝑃 𝑆 − ] равна 𝜌(𝑆 + , 𝑆 − ), и 𝑃 находится посередине этой поло- сы. Назовем гиперплоскость 𝑃 , находящуюся посередине полосы [𝑃 𝑆 + , 𝑃 𝑆 − ] с шириной 𝜌(𝑆 + , 𝑆 − ), оптимальной гиперплоскостью, разделяющей выборку 𝑆. Ниже излагается метод построения такой гиперплоскости. Кроме того, ниже вводится еще одна мера оптимальности АФ 𝑎 𝑆 , и излагается алгоритм построения функции 𝑎 𝑆 , оптимальной относительно этой меры. 2.5.2 Построение оптимальной разделяющей гипер- плоскости для строго линейно разделимой вы- борки Описание задачи В этом пункте мы предполагаем, что задана строго линейно разделимая выборка 𝑆, и 𝑃 – какая-либо гиперплоскость, разделяющая 𝑆 + и 𝑆 − По определению, определенные выше гиперплоскости 𝑃 𝑆 + и 𝑃 𝑆 − па- раллельны, поэтому можно считать, что их уравнения различаются лишь в свободном члене и имеют вид ⟨𝑥, 𝑣⟩ − 𝑎 = 0, ⟨𝑥, 𝑣⟩ − 𝑏 = 0, где 𝑣 ∈ R 𝑛 , 𝑎, 𝑏 ∈ R, 𝑎 ̸= 𝑏. (2.36) ∀ 𝜆 ∈ R ∖ {0} уравнения ⟨𝑥, 𝜆𝑣⟩ − 𝜆𝑎 = 0, ⟨𝑥, 𝜆𝑣⟩ − 𝜆𝑏 = 0 (2.37) равносильны соответствующим уравнениям в (2.36), т.е. определяют те же самые гиперплоскости 𝑃 𝑆 + и 𝑃 𝑆 − . Нетрудно видеть, что если в каче- стве 𝜆 взять число 2 𝑎−𝑏 , то уравнения (2.37) будут равносильны соответ- ствующим уравнениям ⟨𝑥, 𝑤⟩ − 𝑤 0 = 1, ⟨𝑥, 𝑤⟩ − 𝑤 0 = −1, (2.38) где 𝑤 = 𝜆𝑣, 𝑤 0 = 𝑎+𝑏 𝑎−𝑏 . Таким образом, можно считать, что ∙ гиперплоскости 𝑃 𝑆 + и 𝑃 𝑆 − определяются уравнениями (2.38), и ∙ точки из 𝑆 + и 𝑆 − находятся в непересекающихся полупростран- ствах, определяемых 𝑃 𝑆 + и 𝑃 𝑆 − , т.е. удовлетворяют соотношениям ⟨𝑥, 𝑤⟩ − 𝑤 0 ≥ 1 и ⟨𝑥, 𝑤⟩ − 𝑤 0 ≤ −1 соответственно. 35 Вычислим ширину 𝜌 полосы [𝑃 𝑆 + , 𝑃 𝑆 − ]. Выберем на 𝑃 𝑆 + и 𝑃 𝑆 − точки 𝑥 + и 𝑥 − соответственно. Пусть 𝑥 ⊥ – основание перпендикуляра, опущенного из точки 𝑥 + на гиперплоскость 𝑃 𝑆 − Искомая ширина 𝜌 равна длине катета [𝑥 + , 𝑥 ⊥ ] прямоугольного тре- угольника с вершинами в точках 𝑥 + , 𝑥 − , 𝑥 ⊥ : 𝑆 + 𝑆 − 𝑥 + 𝑥 − 𝑥 ⊥ s s s Эту длину можно вычислить как произведение ∙ длины гипотенузы [𝑥 + , 𝑥 − ], т.е. ||𝑥 + − 𝑥 − ||, и ∙ косинуса угла 𝜙 = \ 𝑥 − 𝑥 + 𝑥 ⊥ , который выражается через скалярное произведение: cos 𝜙 = ⟨𝑥 + −𝑥 − ,𝑥 + −𝑥 ⊥ ⟩ ||𝑥 + −𝑥 − || ||𝑥 + −𝑥 ⊥ || , т.е. 𝜌 = ⟨𝑥 + −𝑥 − ,𝑥 + −𝑥 ⊥ ⟩ ||𝑥 + −𝑥 ⊥ || . Поскольку вектор 𝑥 + − 𝑥 ⊥ ортогонален к 𝑃 , то он имеет вид 𝜇𝑤 для некоторого числа 𝜇, поэтому 𝜌 = ⟨𝑥 + − 𝑥 − , 𝜇𝑤⟩ ||𝜇𝑤|| = 𝜇 |𝜇| ⟨𝑥 + − 𝑥 − , 𝑤⟩ ||𝑤|| = 𝜎 ⟨𝑥 + − 𝑥 − , 𝑤⟩ ||𝑤|| , (2.39) где 𝜎 = 1 или −1. Поскольку 𝑥 + ∈ 𝑃 𝑆 + и 𝑥 − ∈ 𝑃 𝑆 − , то ⟨𝑥 + , 𝑤⟩ − 𝑤 0 = 1, ⟨𝑥 − , 𝑤⟩ − 𝑤 0 = −1, откуда следует, что ⟨𝑥 + − 𝑥 − , 𝑤⟩ = ⟨𝑥 + , 𝑤⟩ − ⟨𝑥 − , 𝑤⟩ = (𝑤 0 + 1) − (𝑤 0 − 1) = 2, (2.40) Из (2.39) и (2.40) следует, что 𝜎 = 1, и 𝜌 = 2 ||𝑤|| Таким образом, задача поиска оптимальной разделяющей гиперплос- кости для 𝑆, т.е. такой гиперплоскости 𝑃 , которая определяет полосу [𝑆 + 𝑃 , 𝑆 − 𝑃 ] максимальной ширины, сводится к следующей задаче: найти та- кие 𝑤 ∈ R 𝑛 и 𝑤 0 ∈ R, чтобы ∙ значение ||𝑤|| было минимально возможным, и 36 ∙ были выполнены условия {︂ ∀ 𝑥 ∈ 𝑆 + ⟨𝑥, 𝑤⟩ − 𝑤 0 ≥ 1, ∀ 𝑥 ∈ 𝑆 − ⟨𝑥, 𝑤⟩ − 𝑤 0 ≤ −1, которые можно переписать в виде ∀ 𝑥 ∈ 𝑋 𝑆 𝑦 𝑥 (⟨𝑥, 𝑤⟩ − 𝑤 0 ) − 1 ≥ 0 (2.41) где 𝑋 𝑆 def = {𝑥 ∈ R 𝑛 | (𝑥, 𝑦 𝑥 ) ∈ 𝑆}. Если решение (𝑤, 𝑤 0 ) этой задачи найдено, то оптимальная разделя- ющая гиперплоскость 𝑃 определяется уравнением ⟨𝑥, 𝑤⟩ − 𝑤 0 = 0. Заметим, что решение данной задачи совпадает с решением задачи ||𝑤|| 2 2 → min (2.42) при условиях (2.41). Таким образом, мы свели задачу построения опти- мальной разделяющей гиперплоскости для строго линейно разделимой выборки к оптимизационной задаче (2.42) при условиях (2.41). Метод решения оптимизационной задачи В этом пункте мы рассмотрим подход к решению общей оптимизацион- ной задачи, частным случаем которой является оптимизационная задача (2.42) при условиях (2.41). Данная общая задача имеет следующий вид: заданы ∙ функция 𝑓 : R 𝑛 → R (называемая целевой функцией), которая является выпуклой, т.е. ∀ 𝑥, 𝑥 ′ ∈ R 𝑛 , ∀ 𝛼 ∈ [0, 1] 𝑓 (𝛼𝑥 + (1 − 𝛼)𝑥 ′ ) ≤ 𝛼𝑓 (𝑥) + (1 − 𝛼)𝑓 (𝑥 ′ ), ∙ множество условий вида 𝑔 1 (𝑥) ≤ 0, . . . , 𝑔 𝑚 (𝑥) ≤ 0, где 𝑔 1 , . . . , 𝑔 𝑚 – выпуклые функции вида R 𝑛 → R. Обозначим записью 𝐷 𝑔 1 ,...,𝑔 𝑚 множество 𝐷 𝑔 1 ,...,𝑔 𝑚 def = {𝑥 ∈ R 𝑛 | ∀ 𝑖 = 1, . . . , 𝑚 𝑔 𝑖 (𝑥) ≤ 0}. (2.43) Требуется найти аргумент ˆ 𝑥 ∈ 𝐷 𝑔 1 ,...,𝑔 𝑚 , на котором достигается мини- мальное значение функции 𝑓 , в предположении что минимальность рас- сматривается относительно множества 𝐷 𝑔 1 ,...,𝑔 𝑚 , т.е. требуется, чтобы 𝑓 (ˆ 𝑥) = min 𝑥∈𝐷 𝑔1,...,𝑔𝑚 𝑓 (𝑥). 37 Данную задачу можно решать с помощью теоремы Каруша-Куна- Таккера, которую называют основной теоремой выпуклой нелинейной оптимизации. Ниже мы приводим частный случай этой теоремы. Теорема 3 (W.Karush, 1942, H.Kuhn and A.Tucker, 1951). Пусть заданы выпуклые функции 𝑓 , 𝑔 1 , . . . , 𝑔 𝑚 вида R 𝑛 → R, причем ∃ 𝑥 ∈ R 𝑛 : ∀ 𝑖 = 1, . . . , 𝑚 𝑔 𝑖 (𝑥) < 0. (2.44) Обозначим символом 𝐿 функцию (называемую функцией Лагранжа) 𝐿 = 𝑓 (𝑥) + 𝑚 ∑︁ 𝑖=1 𝜆 𝑖 𝑔 𝑖 (𝑥), (2.45) где 𝜆 1 , . . . , 𝜆 𝑚 – переменные, называемые множителями Лагранжа. ∀ ˆ 𝑥 ∈ 𝐷 𝑔 1 ,...,𝑔 𝑚 следующие утверждения эквивалентны: 𝑓 (ˆ 𝑥) = min 𝑥∈𝐷 𝑔1,...,𝑔𝑚 𝑓 (𝑥), (2.46) ∃ ˆ 𝜆 1 , . . . , ˆ 𝜆 𝑚 ∈ R : ⎧ ⎪ ⎨ ⎪ ⎩ ∀ 𝑖 = 1 . . . , 𝑚 ˆ 𝜆 𝑖 ≥ 0, ∀ 𝑖 = 1 . . . , 𝑚 ˆ 𝜆 𝑖 𝑔 𝑖 (ˆ 𝑥) = 0, 𝐿(ˆ 𝑥, ˆ 𝜆 1 . . . , ˆ 𝜆 𝑚 ) = min 𝑥∈R 𝑛 𝐿(𝑥, ˆ 𝜆 1 . . . , ˆ 𝜆 𝑚 ). (2.47) Если функции 𝑓, 𝑔 1 , . . . , 𝑔 𝑚 дифференцируемые, то функция Лагран- жа 𝐿 тоже будет дифференцируемой, и этом случае третье соотношение в (2.47) равносильно соотношению ∀ 𝑖 = 1, . . . , 𝑛 𝜕𝐿 𝜕𝑥 𝑖 (ˆ 𝑥, ˆ 𝜆 1 , . . . , ˆ 𝜆 𝑚 ) = 0. (2.48) Доказательство. Сначала докажем, что если для точки ˆ 𝑥 ∈ 𝐷 𝑔 1 ,...,𝑔 𝑚 верно утверждение (2.47), то для нее будет верно утверждение (2.46). Т.к. ∀ 𝑖 = 1, . . . , 𝑚, ∀ 𝑥 ∈ 𝐷 𝑔 1 ,...,𝑔 𝑚 ˆ 𝜆 𝑖 𝑔 𝑖 (𝑥) ≤ 0, то ∀ 𝑥 ∈ 𝐷 𝑔 1 ,...,𝑔 𝑚 𝐿(𝑥, ˆ 𝜆 1 , . . . , ˆ 𝜆 𝑚 ) = 𝑓 (𝑥) + 𝑚 ∑︁ 𝑖=1 ˆ 𝜆 𝑖 𝑔 𝑖 (𝑥) ≤ 𝑓 (𝑥). (2.49) Из второго соотношения в (2.47) следует, что 𝐿(ˆ 𝑥, ˆ 𝜆 1 , . . . , ˆ 𝜆 𝑚 ) = 𝑓 (ˆ 𝑥) + 𝑚 ∑︁ 𝑖=1 ˆ 𝜆 𝑖 𝑔 𝑖 (ˆ 𝑥) = 𝑓 (ˆ 𝑥) + 𝑚 ∑︁ 𝑖=1 0 = 𝑓 (ˆ 𝑥). (2.50) 38 Из третьего соотношения в (2.47) следует, что ∀ 𝑥 ∈ R 𝑛 𝐿(ˆ 𝑥, ˆ 𝜆 1 , . . . , ˆ 𝜆 𝑚 ) ≤ 𝐿(𝑥, ˆ 𝜆 1 , . . . , ˆ 𝜆 𝑚 ). (2.51) Из (2.49) (2.50) и (2.51) следует, что для ˆ 𝑥 верно (2.46): ∀ 𝑥 ∈ 𝐷 𝑔 1 ,...,𝑔 𝑚 𝑓 (ˆ 𝑥) = 𝐿(ˆ 𝑥, ˆ 𝜆 1 , . . . , ˆ 𝜆 𝑚 ) ≤ 𝐿(𝑥, ˆ 𝜆 1 , . . . , ˆ 𝜆 𝑚 ) ≤ 𝑓 (𝑥). Теперь докажем, что если для точки ˆ 𝑥 ∈ 𝐷 𝑔 1 ,...,𝑔 𝑚 верно утверждение (2.46), то для нее будет верно утверждение (2.47). Обозначим символом Λ множество всех векторов (𝜆 0 , . . . , 𝜆 𝑚 ) ∈ R 𝑚+1 , каждый из которых удовлетворяет следующему условию: ∃ 𝑥 ∈ R 𝑛 : {︂ 𝜆 0 > 𝑓 (𝑥) − 𝑓 (ˆ 𝑥), ∀ 𝑖 = 1, . . . , 𝑚 𝜆 𝑖 ≥ 𝑔 𝑖 (𝑥). Очевидно что множество Λ непусто. Нулевой вектор ¯ 0 = (0, . . . , 0) не входит в Λ, т.к. иначе ∃ 𝑥 ∈ R 𝑛 : {︂ 0 > 𝑓 (𝑥) − 𝑓 (ˆ 𝑥) (⇒ 𝑓 (𝑥) < 𝑓 (ˆ 𝑥)), ∀ 𝑖 = 1, . . . , 𝑚 0 ≥ 𝑔 𝑖 (𝑥) (⇒ 𝑥 ∈ 𝐷 𝑔 1 ,...,𝑔 𝑚 ), т.е. min 𝑥∈𝐷 𝑔1,...,𝑔𝑚 𝑓 (𝑥) < 𝑓 (ˆ 𝑥), что противоречит предположению (2.46). Докажем, что множество Λ выпукло, т.е. ∀ 𝜆, 𝜆 ′ ∈ Λ, ∀ 𝛼 ∈ [0, 1] 𝜆 (𝛼) def = 𝛼𝜆 + (1 − 𝛼)𝜆 ′ ∈ Λ. (2.52) Действительно, если 𝜆 и 𝜆 ′ имеют вид (𝜆 0 , . . . , 𝜆 𝑚 ) и (𝜆 ′ 0 , . . . , 𝜆 ′ 𝑚 ) соответ- ственно, и вектора 𝑥, 𝑥 ′ таковы, что 𝜆 0 > 𝑓 (𝑥) − 𝑓 (ˆ 𝑥), ∀ 𝑖 = 1, . . . , 𝑚 𝜆 𝑖 ≥ 𝑔 𝑖 (𝑥) 𝜆 ′ 0 > 𝑓 (𝑥 ′ ) − 𝑓 (ˆ 𝑥), ∀ 𝑖 = 1, . . . , 𝑚 𝜆 ′ 𝑖 ≥ 𝑔 𝑖 (𝑥 ′ ) то нетрудно проверить (используя выпуклость 𝑓 , 𝑔 1 , . . ., 𝑔 𝑚 ), что вектор 𝑥 (𝛼) def = 𝛼𝑥 + (1 − 𝛼)𝑥 ′ обладает свойством {︃ 𝜆 (𝛼) 0 > 𝑓 (𝑥 (𝛼) ) − 𝑓 (ˆ 𝑥), ∀ 𝑖 = 1, . . . , 𝑚 𝜆 (𝛼) 𝑖 ≥ 𝑔 𝑖 (𝑥 (𝛼) ). (2.53) Распишем (2.53) во всех деталях: ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ 𝜆 (𝛼) 0 = 𝛼𝜆 0 + (1 − 𝛼)𝜆 ′ 0 > > 𝛼𝑓 (𝑥) − 𝛼𝑓 (ˆ 𝑥) + (1 − 𝛼)𝑓 (𝑥 ′ ) − (1 − 𝛼)𝑓 (ˆ 𝑥) ≥ ≥ 𝑓 (𝛼𝑥 + (1 − 𝛼)𝑥 ′ ) − 𝑓 (ˆ 𝑥) = 𝑓 (𝑥 (𝛼) ) − 𝑓 (ˆ 𝑥), ∀ 𝑖 = 1, . . . , 𝑚 𝜆 (𝛼) 𝑖 = 𝛼𝜆 𝑖 + (1 − 𝛼)𝜆 ′ 𝑖 ≥ ≥ 𝛼𝑔 𝑖 (𝑥) + (1 − 𝛼)𝑔 𝑖 (𝑥 ′ ) ≥ 𝑔 𝑖 (𝛼𝑥 + (1 − 𝛼)𝑥 ′ ) = 𝑔 𝑖 (𝑥 (𝛼) ). Таким образом, (2.52) верно. 39 Лемма об отделимости. Множество Λ обладает свойством отделимости: ∃ 𝜆 * ∈ R 𝑚+1 : 𝜆 * ̸= ¯ 0, ∀ 𝜆 ∈ Λ ⟨𝜆 * , 𝜆⟩ ≥ 0 (2.54) (т.е. Λ содержится в одном из полупространств, на которые де- лит пространство R 𝑚+1 гиперплоскость, определяемая уравнением ⟨𝜆 * , 𝑥⟩ = 0). Доказательство. Если размерность 𝐿𝑖𝑛(Λ) линейной оболочки множества Λ (т.е. ми- нимального линейного подпространства пространства R 𝑚+1 , содер- жащего Λ) меньше чем 𝑚 + 1, то в качестве искомого вектора 𝜆 * можно взять любой ненулевой вектор из ортогонального дополне- ния 𝐿𝑖𝑛(Λ). В этом случае (2.54) верно по причине того, что ∀ 𝜆 ∈ Λ ⟨𝜆 * , 𝜆⟩ = 0. Пусть размерность 𝐿𝑖𝑛(Λ) равна 𝑚 + 1. В этом случае Λ содержит линейно независимое множество из 𝑚 + 1 векторов. Обозначим век- торы, входящие в это множество, записями 𝑣 1 , . . . , 𝑣 𝑚+1 Определим ⃗ Λ def = {𝜉𝜆 | 𝜉 > 0, 𝜆 ∈ Λ}. Отметим, что Λ ⊆ ⃗ Λ, и ¯ 0 ̸∈ ⃗ Λ. Множество ⃗ Λ выпуклое, т.к. ∀ 𝜉, 𝜉 ′ > 0, ∀ 𝜆, 𝜆 ′ ∈ ⃗ Λ, ∀ 𝛼 ∈ [0, 1] 𝛼(𝜉𝜆) + (1 − 𝛼)(𝜉 ′ 𝜆 ′ ) ∈ ⃗ Λ. (2.55) Действительно, вектор в (2.55) равен 𝜉 ′′ 𝜆 ′′ , где ∙ 𝜉 ′′ = 𝛼𝜉 + (1 − 𝛼)𝜉 ′ > 0, и ∙ 𝜆 ′′ = 𝛼𝜉 𝜉 ′′ 𝜆 + (1−𝛼)𝜉 ′ 𝜉 ′′ 𝜆 ′ ∈ [𝜆, 𝜆 ′ ], поэтому 𝜆 ′′ ∈ Λ. Докажем, что 𝑣 = 𝑚+1 ∑︀ 𝑖=1 𝑣 𝑖 – внутренняя точка ⃗ Λ, т.е. ∃ 𝜀 > 0: 𝜀–окре- стность 𝑈 𝜀 𝑣 def = {𝑣 ′ ∈ R 𝑚+1 | ||𝑣 ′ − 𝑣|| < 𝜀} вектора 𝑣 лежит в ⃗ Λ. Обозначим символом 𝑉 множество, состоящее из всех векторов ви- да 𝑚+1 ∑︀ 𝑖=1 𝛼 𝑖 𝑣 𝑖 , где ∀ 𝑖 = 1, . . . , 𝑚 |𝛼 𝑖 | ≤ 1 2 . Для каждого вектора 𝑥 из единичной сферы 𝑆 def = {𝑥 ∈ R 𝑚+1 | ||𝑥|| = 1} обозначим записью 𝜀 𝑥 максимальное число, такое, что 𝜀 𝑥 𝑥 ∈ 𝑉 (такое число существует, т.к. множество 𝑉 является ограниченным). Поскольку единичная 40 сфера в R 𝑚+1 – компакт, то непрерывная функция 𝑥 ↦→ 𝜀 𝑥 на 𝑆 достигает наименьшего значения 𝜀 > 0 на некотором элементе 𝑆. Итак, ∀ 𝑥 ∈ 𝑆 𝜀𝑥 ∈ 𝑉 , откуда следует, что 𝑈 𝜀 ¯ 0 ⊆ 𝑉 , поэтому 𝑈 𝜀 𝑣 = 𝑣 + 𝑈 𝜀 ¯ 0 ⊆ 𝑣 + 𝑉 = { 𝑚+1 ∑︀ 𝑖=1 𝛼 𝑖 𝑣 𝑖 | 1 2 ≤ 𝛼 𝑖 ≤ 3 2 } ⊆ ⃗ Λ. Следовательно, каждый элемент 𝑈 𝜀 −𝑣 = −𝑣+𝑈 𝜀 ¯ 0 не лежит в ⃗ Λ (иначе некоторый отрезок из ⃗ Λ с концами в 𝑈 𝜀 −𝑣 и 𝑈 𝜀 𝑣 содержал бы ¯ 0). Обозначим записью ⃗ Λ 𝑐 замыкание множества ⃗ Λ, т.е. множество, получаемое добавлением к ⃗ Λ всех его предельных точек. Нетрудно доказать, что замыкание любого выпуклого множества является выпуклым множеством. В частности, множество ⃗ Λ 𝑐 выпукло. Поскольку 𝑈 𝜀 −𝑣 ∩ ⃗ Λ = ∅, то −𝑣 не является предельной точкой мно- жества ⃗ Λ, поэтому −𝑣 ̸∈ ⃗ Λ 𝑐 Определим 𝑢 0 как такой вектор, из ⃗ Λ 𝑐 , что 𝜌(−𝑣, 𝑢 0 ) = min{𝜌(−𝑣, 𝑢) | 𝑢 ∈ ⃗ Λ 𝑐 }. где 𝜌 – евклидово расстояние между векторами. Такой вектор су- ществует. Действительно, обозначим ∙ символом 𝑅 расстояние от −𝑣 до какого-либо элемента ⃗ Λ 𝑐 , и ∙ записью 𝐵 𝑅 −𝑣 замкнутый шар с центром в −𝑣 радиуса 𝑅. Поскольку множество 𝐵 𝑅 −𝑣 замкнуто и ограничено, то непустое мно- жество ⃗ Λ 𝑐 ∩ 𝐵 𝑅 −𝑣 тоже замкнуто и ограничено, т.е. оно компактно. Нетрудно видеть, что min{𝜌(−𝑣, 𝑢) | 𝑢 ∈ ⃗ Λ 𝑐 } = min{𝜌(−𝑣, 𝑢) | 𝑢 ∈ ⃗ Λ 𝑐 ∩ 𝐵 𝑅 −𝑣 }. Существование точки 𝑢 0 , на которой функция 𝑢 ↦→ 𝜌(−𝑣, 𝑢) на компактном множестве ⃗ Λ 𝑐 ∩ 𝐵 𝑅 −𝑣 принимает наименьшее значение, обосновывается теми же методами, которыми обосновывается ана- логичное утверждение в теореме из параграфа 2.1. Также аналогичными методами обосновывается следующее утвер- ждение: гиперплоскость 𝑃 , проходящая через точку 𝑢 0 и ортого- нальная отрезку [−𝑣, 𝑢 0 ], делит пространство R 𝑚+1 на два полу- пространства, одно из которых (обозначим его 𝑍) имеет вид 41 𝑍 = {𝑥 ∈ R 𝑚+1 | 𝑥 = 𝑢 0 или \ −𝑣𝑢 0 𝑥 ≥ 𝜋 2 } и ⃗ Λ 𝑐 ⊆ 𝑍. Докажем, что ¯ 0 ∈ 𝑃 . Пусть ¯ 0 ̸∈ 𝑃 . Тогда ¯ 0 ̸= 𝑢 0 ∈ 𝑃 . Т.к. ¯ 0 ∈ ⃗ Λ 𝑐 (¯ 0 – предельная точка ⃗ Λ), то \ −𝑣𝑢 0 ¯ 0 ≥ 𝜋 2 . Поскольку 𝑢 1 def = 2𝑢 0 ∈ ⃗ Λ 𝑐 , то \ −𝑣𝑢 0 𝑢 1 ≥ 𝜋 2 . Однако углы (−𝑣𝑢 0 ¯ 0) и (−𝑣𝑢 0 𝑢 1 ) являются смежными, сумма их величин равна 𝜋, что возможно только если \ |