Книга представляет собой введение в основные понятия, методы и ал

Построение оптимальной разделяющей гипер- плоскости для строго линейно разделимой вы- борки

Описание задачи

В этом пункте мы предполагаем, что задана строго линейно разделимая выборка 𝑆, и 𝑃 – какая-либо гиперплоскость, разделяющая 𝑆⁺ и 𝑆⁻.
По определению, определенные выше гиперплоскости 𝑃_𝑆⁺ и 𝑃_𝑆⁻ па-
раллельны, поэтому можно считать, что их уравнения различаются лишь в свободном члене и имеют вид
⟨, ⟩ − 𝑎 = 0, ⟨, ⟩ − 𝑏 = 0, где ∈ R, 𝑎, 𝑏 ∈ R, 𝑎 ̸= 𝑏. (2.36)
∀ 𝜆 ∈ R ∖ {0} уравнения
⟨, 𝜆⟩ − 𝜆𝑎 = 0, ⟨, 𝜆⟩ − 𝜆𝑏 = 0 (2.37)

−

𝑎 𝑏
равносильны соответствующим уравнениям в (2.36), т.е. определяют те же самые гиперплоскости 𝑃_𝑆⁺ и 𝑃_𝑆⁻ . Нетрудно видеть, что если в каче- стве 𝜆 взять число ² , то уравнения (2.37) будут равносильны соответ- ствующим уравнениям
⟨, ⟩ − ₀ = 1, ⟨, ⟩ − ₀ = −1, (2.38) где = 𝜆, ₀ = ^𝑎+𝑏 . Таким образом, можно считать, что
𝑎−𝑏

• 
  гиперплоскости 𝑃_𝑆⁺ и 𝑃_𝑆⁻ определяются уравнениями (2.38), и
  
• 
  точки из 𝑆⁺ и 𝑆⁻ находятся в непересекающихся полупростран- ствах, определяемых 𝑃_𝑆⁺ и 𝑃_𝑆⁻ , т.е. удовлетворяют соотношениям
  

⟨, ⟩ − ₀ ≥ 1 и ⟨, ⟩ − ₀ ≤ −1
соответственно.
Вычислим ширину 𝜌 полосы [𝑃_𝑆⁺ , 𝑃_𝑆⁻ ].
Выберем на 𝑃_𝑆⁺ и 𝑃_𝑆⁻ точки ⁺ и ⁻ соответственно. Пусть ^⊥ – основание перпендикуляра, опущенного из точки ⁺ на гиперплоскость
𝑃_𝑆⁻ .
Искомая ширина 𝜌 равна длине катета [⁺, ^⊥] прямоугольного тре- угольника с вершинами в точках ⁺, ⁻, ^⊥:
_𝑆+ _𝑆−
+

Эту длину можно вычислить как произведение

• 
  длины гипотенузы [⁺, ⁻], т.е. |⁺ − ⁻ |, и
  

∙
косинуса угла 𝜙 = ^{−^+⊥}, который выражается через скалярное произведение: cos 𝜙 = ^⟨+⁻−^,+⁻⊥^⟩ ,
|⁺−⁻ | |⁺−^⊥ |
т.е. 𝜌 = ^⟨+⁻−^,+⁻⊥^⟩ . Поскольку вектор ⁺ − ^⊥ ортогонален к 𝑃 , то он

имеет вид
+ ⊥
𝜇 для некоторого числа 𝜇
, поэтому

𝜌 =

⟨⁺ − ⁻, 𝜇⟩
|𝜇 |
𝜇
=
|𝜇|
⟨⁺ − ⁻, ⟩
| |

= 𝜎

⟨⁺ − ⁻, ⟩
| |
, (2.39)

где 𝜎 = 1 или −1. Поскольку ⁺ ∈ 𝑃_𝑆⁺ и ⁻ ∈ 𝑃_𝑆⁻ , то
⟨⁺, ⟩ − ₀ = 1, ⟨⁻, ⟩ − ₀ = −1,
откуда следует, что

| |



⟨⁺ − ⁻, ⟩ = ⟨⁺, ⟩ − ⟨⁻, ⟩ = (₀ + 1) − (₀ − 1) = 2, (2.40) Из (2.39) и (2.40) следует, что 𝜎 = 1, и 𝜌 = ² .
Таким образом, задача поиска оптимальной разделяющей гиперплос-
кости для 𝑆, т.е. такой гиперплоскости 𝑃 , которая определяет полосу
[𝑆⁺, 𝑆⁻] максимальной ширины, сводится к следующей задаче: найти та-
𝑃 𝑃
кие ∈ R и ₀ ∈ R, чтобы

• 
  значение | | было минимально возможным, и
  

• 
  были выполнены условия можно переписать в виде
  

∀ ∈ 𝑆⁺ ⟨, ⟩ − ₀ ≥ 1, _{которые}

{︂
∀ ∈ 𝑆⁻ ⟨, ⟩ − ₀ ≤ −1,

=
∀ ∈ 𝑋_𝑆 (⟨, ⟩ − ₀) − 1 ≥ 0 (2.41) где 𝑋_𝑆 ^def { ∈ R | (, ) ∈ 𝑆}.

⟨ ⟩ −
Если решение (, ₀) этой задачи найдено, то оптимальная разделя- ющая гиперплоскость 𝑃 определяется уравнением , ₀ = 0.
Заметим, что решение данной задачи совпадает с решением задачи

| |
2
₂ → min (2.42)
при условиях (2.41). Таким образом, мы свели задачу построения опти- мальной разделяющей гиперплоскости для строго линейно разделимой выборки к оптимизационной задаче (2.42) при условиях (2.41).

Метод решения оптимизационной задачи

В этом пункте мы рассмотрим подход к решению общей оптимизацион- ной задачи, частным случаем которой является оптимизационная задача (2.42) при условиях (2.41).
Данная общая задача имеет следующий вид: заданы

• 
  →
  

функция 𝑓 : R R (называемая целевой функцией), которая является выпуклой, т.е.
∀ , ^′ ∈ R, ∀ 𝛼 ∈ [0, 1] 𝑓 (𝛼 + (1 − 𝛼)^′) ≤ 𝛼𝑓 () + (1 − 𝛼)𝑓 (^′),

• 
  множество условий вида 𝑔₁() ≤ 0, . . . , 𝑔() ≤ 0, где 𝑔₁, . . . , 𝑔 – выпуклые функции вида R → R.
  

Обозначим записью 𝐷_{𝑔1,...,𝑔} множество

{ ∈



def
^𝐷𝑔₁,...,𝑔 ^{= R}
| ∀ = 1, . . . , 𝑔() ≤ 0}. (2.43)

Требуется найти аргумент ˆ ∈ 𝐷_{𝑔1,...,𝑔} , на котором достигается мини-

мальное значение функции 𝑓 , в предположении что минимальность рас- сматривается относительно множества 𝐷_{𝑔1,...,𝑔} , т.е. требуется, чтобы

𝑓 (ˆ) = min
^∈𝐷𝑔₁,...,𝑔
𝑓 ().

Данную задачу можно решать с помощью теоремы Каруша-Куна- Таккера, которую называют основной теоремой выпуклой нелинейной оптимизации. Ниже мы приводим частный случай этой теоремы.

Теорема 3 (W.Karush, 1942, H.Kuhn and A.Tucker, 1951). Пусть заданы выпуклые функции 𝑓 , 𝑔₁, . . . , 𝑔 вида R → R, причем

∃ ∈ R : ∀ = 1, . . . , 𝑔() < 0. (2.44) Обозначим символом 𝐿 функцию (называемую функцией Лагранжа)

∑︁

𝐿 = 𝑓 () + 𝜆𝑔(), (2.45)

=1
где 𝜆₁, . . . , 𝜆 – переменные, называемые множителями Лагранжа.
∀ ˆ ∈ 𝐷_{𝑔1,...,𝑔} следующие утверждения эквивалентны:

𝑓 (ˆ) = min
^∈𝐷𝑔₁,...,𝑔
𝑓 (), (2.46)

∃ 𝜆^ˆ₁, . . . , 𝜆^ˆ ∈ R :
∀ = 1 . . . ,

⎪_⎩
∀ = 1 . . . ,
𝜆^ˆ ≥ 0,
𝜆^ˆ𝑔(ˆ) = 0,

(2.47)

𝐿(ˆ, 𝜆^ˆ₁ . . . , 𝜆^ˆ) = min 𝐿(, 𝜆^ˆ₁ . . . , 𝜆^ˆ).
∈R
Если функции 𝑓, 𝑔₁, . . . , 𝑔 дифференцируемые, то функция Лагран- жа 𝐿 тоже будет дифференцируемой, и этом случае третье соотношение в (2.47) равносильно соотношению

∀

1
= 1, . . . , ^𝜕𝐿 (ˆ, 𝜆^ˆ
𝜕
, . . . , 𝜆^ˆ
) = 0. (2.48)

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

∈
Сначала докажем, что если для точки ˆ 𝐷_{𝑔1,...,𝑔} верно утверждение (2.47), то для нее будет верно утверждение (2.46).
Т.к. ∀ = 1, . . . , , ∀ ∈ 𝐷_{𝑔1,...,𝑔} 𝜆^ˆ𝑔() ≤ 0, то

∑︁

∀ ∈ 𝐷_{𝑔1,...,𝑔} 𝐿(, 𝜆^ˆ₁, . . . , 𝜆^ˆ) = 𝑓 () + 𝜆^ˆ𝑔() ≤ 𝑓 (). (2.49)

=1

Из второго соотношения в (2.47) следует, что

𝐿(ˆ, 𝜆^ˆ₁, . . . , 𝜆^ˆ) = 𝑓 (ˆ) + ∑︁ 𝜆^ˆ𝑔(ˆ) = 𝑓 (ˆ) + ∑︁ 0 = 𝑓 (ˆ). (2.50)

Из третьего соотношения в (2.47) следует, что
∀ ∈ R 𝐿(ˆ, 𝜆^ˆ₁, . . . , 𝜆^ˆ) ≤ 𝐿(, 𝜆^ˆ₁, . . . , 𝜆^ˆ). (2.51) Из (2.49) (2.50) и (2.51) следует, что для ˆ верно (2.46):
∀ ∈ 𝐷_{𝑔1,...,𝑔} 𝑓 (ˆ) = 𝐿(ˆ, 𝜆^ˆ₁, . . . , 𝜆^ˆ) ≤ 𝐿(, 𝜆^ˆ₁, . . . , 𝜆^ˆ) ≤ 𝑓 ().

∈
Теперь докажем, что если для точки ˆ 𝐷_{𝑔1,...,𝑔} верно утверждение (2.46), то для нее будет верно утверждение (2.47).

{︂
Обозначим символом Λ множество всех векторов (𝜆₀, . . . , 𝜆) ∈ R⁺¹, каждый из которых удовлетворяет следующему условию: ∃ ∈ R:
𝜆₀ > 𝑓 () − 𝑓 (ˆ),
∀ = 1, . . . , 𝜆 ≥ 𝑔().
Очевидно что множество Λ непусто.

{︂
Нулевой вектор ^¯0 = (0, . . . , 0) не входит в Λ, т.к. иначе ∃ ∈ R:
0 > 𝑓 () − 𝑓 (ˆ) (⇒ 𝑓 () < 𝑓 (ˆ)),
∀ = 1, . . . , 0 ≥ 𝑔() (⇒ ∈ 𝐷_{𝑔1,...,𝑔} ),

т.е. min
^∈𝐷𝑔₁,...,𝑔
𝑓 () < 𝑓 (ˆ), что противоречит предположению (2.46).

_𝜆(𝛼) def
Докажем, что множество Λ выпукло, т.е. ∀ 𝜆, 𝜆^′ ∈ Λ, ∀ 𝛼 ∈ [0, 1]
= 𝛼𝜆 + (1 − 𝛼)𝜆^′ ∈ Λ. (2.52)
Действительно, если 𝜆 и 𝜆^′ имеют вид (𝜆₀, . . . , 𝜆) и (𝜆^′₀, . . . , 𝜆^′) соответ- ственно, и вектора , ^′ таковы, что
𝜆₀ > 𝑓 () − 𝑓 (ˆ), ∀ = 1, . . . , 𝜆 ≥ 𝑔()
𝜆^′₀ > 𝑓 (^′) − 𝑓 (ˆ), ∀ = 1, . . . , 𝜆^′ ≥ 𝑔(^′)
то нетрудно проверить (используя выпуклость 𝑓 , 𝑔₁, . . ., 𝑔), что вектор

=
^{(𝛼) def} 𝛼 + (1 − 𝛼)^′ обладает свойством

0

(2.53)
{︃ 𝜆^(𝛼) > 𝑓 (^(𝛼)) − 𝑓 (ˆ),

∀ = 1, . . . , 𝜆 ≥ 𝑔(^(𝛼)).
Распишем (2.53) во всех деталях:
_⎪^⎧ 𝜆^(𝛼) = 𝛼𝜆₀ + (1 − 𝛼)𝜆^′ >
0 0

⎨

> 𝛼𝑓 () − 𝛼𝑓 (ˆ) + (1 − 𝛼)𝑓 ( ) − (1 − 𝛼)𝑓 (ˆ) ≥
≥ 𝑓 (𝛼 + (1 − 𝛼)^′) − 𝑓 (ˆ) = 𝑓 (^(𝛼)) − 𝑓 (ˆ),

_⎪ ∀ = 1, . . . , 𝜆^(𝛼) = 𝛼𝜆 + (1 − 𝛼)𝜆^′ ≥
_⎪ ′

≥ 𝛼𝑔() + (1 − 𝛼)𝑔( ) ≥ 𝑔(𝛼 + (1 − 𝛼) ) = 𝑔(
Таким образом, (2.52) верно.

).
_{⎩ ′}
′ (𝛼)

Лемма об отделимости.

Множество Λ обладает свойством отделимости: ∃ 𝜆^* ∈ R⁺¹:
𝜆^* ̸= ^¯0, ∀ 𝜆 ∈ Λ ⟨𝜆^*, 𝜆⟩ ≥ 0 (2.54)
(т.е. Λ содержится в одном из полупространств, на которые де- лит пространство R⁺¹ гиперплоскость, определяемая уравнением
⟨𝜆^*, ⟩ = 0).

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

Если размерность 𝐿(Λ) линейной оболочки множества Λ (т.е. ми- нимального линейного подпространства пространства R⁺¹, содер- жащего Λ) меньше чем + 1, то в качестве искомого вектора 𝜆^* можно взять любой ненулевой вектор из ортогонального дополне- ния 𝐿(Λ). В этом случае (2.54) верно по причине того, что
∀ 𝜆 ∈ Λ ⟨𝜆^*, 𝜆⟩ = 0.
Пусть размерность 𝐿(Λ) равна + 1. В этом случае Λ содержит линейно независимое множество из +1 векторов. Обозначим век- торы, входящие в это множество, записями ₁, . . . , ₊₁.

Λ =
Определим ^{⃗ def} {𝜉𝜆 | 𝜉 > 0, 𝜆 ∈ Λ}. Отметим, что Λ ⊆ Λ^⃗ , и ^¯0 ̸∈ Λ^⃗ .
Множество Λ^⃗ выпуклое, т.к. ∀ 𝜉, 𝜉^′ > 0, ∀ 𝜆, 𝜆^′ ∈ Λ^⃗ , ∀ 𝛼 ∈ [0, 1]
𝛼(𝜉𝜆) + (1 − 𝛼)(𝜉^′𝜆^′) ∈ Λ^⃗ . (2.55)

Действительно, вектор в (2.55) равен 𝜉^′′𝜆^′′, где

• 
  𝜉^′′ = 𝛼𝜉 + (1 − 𝛼)𝜉^′ > 0, и
  
• 
  𝜆^′′ = ^𝛼𝜉 𝜆 + ^{(1−𝛼)𝜉}′ 𝜆^′ ∈ [𝜆, 𝜆^′], поэтому 𝜆^′′ ∈ Λ.
  

_𝜉′′

Докажем, что

_𝜉′′



∑︀
+1
=
=1

– внутренняя точка Λ^⃗ , т.е.

∃ 𝜀 > 0:

𝜀–окре-

=
стность 𝑈 ^{𝜀 def} {^′ ∈ R⁺¹ | |^′ − | < 𝜀} вектора лежит в Λ^⃗ .
Обозначим символом 𝑉 множество, состоящее из всех векторов ви-

∑︀

2
_да +1
=1
𝛼
, где
∀ = 1, . . . , |𝛼| ≤
¹ . Для каждого вектора из

=

∈

{ ∈ | | | }
единичной сферы 𝑆 ^def R⁺¹ = 1 обозначим записью 𝜀 максимальное число, такое, что 𝜀 𝑉 (такое число существует, т.к. множество 𝑉 является ограниченным). Поскольку единичная

↦→
сфера в R⁺¹ – компакт, то непрерывная функция 𝜀 на 𝑆
достигает наименьшего значения 𝜀 > 0 на некотором элементе 𝑆.

0
Итак, ∀ ∈ 𝑆 𝜀 ∈ 𝑉 , откуда следует, что 𝑈_¯^𝜀 ⊆ 𝑉 , поэтому

𝜀 𝜀

_∑︀+1 _{1 3 ⃗}

−

0

𝑈 = + 𝑈_¯0 ⊆ + 𝑉 = {

𝛼 | ₂ ≤ 𝛼 ≤ ₂ } ⊆ Λ.
Следовательно, каждый элемент 𝑈 ^𝜀 = −+𝑈_¯^𝜀 не лежит в Λ^⃗ (иначе

−



некоторый отрезок из Λ^⃗ с концами в 𝑈 ^𝜀
и 𝑈 ^𝜀 содержал бы ^¯0).

Обозначим записью Λ^{⃗ 𝑐} замыкание множества Λ^⃗ , т.е. множество,
получаемое добавлением к Λ^⃗ всех его предельных точек. Нетрудно
доказать, что замыкание любого выпуклого множества является выпуклым множеством. В частности, множество Λ^{⃗ 𝑐} выпукло.

−
Поскольку 𝑈 ^𝜀 ∩ Λ^⃗ = ∅, то − не является предельной точкой мно-
жества Λ^⃗ , поэтому − ̸∈ Λ^{⃗ 𝑐}.
Определим ₀ как такой вектор, из Λ^{⃗ 𝑐}, что
𝜌(−, ₀) = min{𝜌(−, ) | ∈ Λ^{⃗ 𝑐}}.
где 𝜌 – евклидово расстояние между векторами. Такой вектор су- ществует. Действительно, обозначим

• 
  символом 𝑅 расстояние от − до какого-либо элемента Λ^{⃗ 𝑐}, и
  
• 
  
  −
  записью 𝐵^𝑅 замкнутый шар с центром в − радиуса 𝑅.
  

−
Поскольку множество 𝐵^𝑅 замкнуто и ограничено, то непустое мно-

−
жество Λ^{⃗ 𝑐} ∩ 𝐵^𝑅 тоже замкнуто и ограничено, т.е. оно компактно.
Нетрудно видеть, что

−
min{𝜌(−, ) | ∈ Λ^{⃗ 𝑐}} = min{𝜌(−, ) | ∈ Λ^{⃗ 𝑐} ∩ 𝐵^𝑅 }.
Существование точки ₀, на которой функция ↦→ 𝜌(−, ) на

−
компактном множестве Λ^{⃗ 𝑐} ∩ 𝐵^𝑅 принимает наименьшее значение,
обосновывается теми же методами, которыми обосновывается ана- логичное утверждение в теореме из параграфа 2.1.

−
Также аналогичными методами обосновывается следующее утвер- ждение: гиперплоскость 𝑃 , проходящая через точку ₀ и ортого- нальная отрезку [ , ₀], делит пространство R⁺¹ на два полу- пространства, одно из которых (обозначим его 𝐿) имеет вид

2
𝐿 = { ∈ R⁺¹ | = ₀ или −^{^}₀ ≥ ^𝜋 }
и Λ^{⃗ 𝑐} ⊆ 𝐿.
Докажем, что ^¯0 ∈ 𝑃 . Пусть ^¯0 ̸∈ 𝑃 . Тогда ^¯0 ≠ ₀ ∈ 𝑃 . Т.к. ^¯0 ∈ Λ^{⃗ 𝑐} (0^¯

2

= 2
– предельная точка Λ^⃗ ), то −^{^}₀^¯0 ≥ ^𝜋 . Поскольку ₁ ^def ₀ ∈ Λ^{⃗ 𝑐}, то

2

2
−^{^}₀₁ ≥ ^𝜋 . Однако углы (−₀0^¯) и (−₀₁) являются смежными, сумма их величин равна 𝜋, что возможно только если −^{^}₀^¯0 = ^𝜋 ,
поэтому ^¯0 ∈ 𝑃 .

— − −
Вектор, определяемый отрезком [ , ₀], т.е. ₀ ( ) = ₀ + , ортогонален 𝑃 и принадлежит 𝐿, поэтому
𝐿 = { ∈ R⁺¹ | ⟨₀ + , ⟩ ≥ 0}
и в качестве искомого вектора 𝜆^* можно взять ₀ + .
Продолжим доказательство теоремы Каруша-Куна-Таккера.
Пусть вектор 𝜆^*, обладающий свойством (2.54), имеет вид (𝜆^*₀, . . . , 𝜆^*).
1. Докажем, что ∀ = 0, . . . , 𝜆^* ≥ 0. Поскольку Λ содержит вектора
𝜆⁽⁰⁾ = (1, 0, . . . , 0) и 𝜆⁽⁾ = (𝜀, 0 . . . , 0, 1, 0, . . . , 0) (∀ = 1, . . . , )
где 𝜀 > 0, и единица в 𝜆⁽⁾ стоит в позиции номер (мы считаем, что первая позиция в 𝜆⁽⁾ имеет номер 0), то из (2.54) следует, что
⟨𝜆^*, 𝜆⁽⁰⁾⟩ = 𝜆^*₀ ≥ 0
∀ = 1, . . . , ⟨𝜆^*, 𝜆⁽⁾⟩ = 𝜆^*₀𝜀 + 𝜆^* ≥ 0
откуда, ввиду произвольности 𝜀, заключаем, что 𝜆^* ≥ 0.

2. 
   Докажем, что
   

∀ ∈ {1, . . . , } 𝜆^* 𝑔(ˆ) = 0. (2.56)
Т.к. ∀ 𝜀 > 0 множество Λ содержит вектор

𝜆
def
= (𝜀, 0, . . . , 0, 𝑔(ˆ), 0, . . . , 0),
то из (2.54) следует, что ⟨𝜆^*, 𝜆⟩ = 𝜆₀^*𝜀 + 𝜆^*𝑔(ˆ) ≥ 0, откуда, ввиду произвольности 𝜀, заключаем, что 𝜆^*𝑔(ˆ) ≥ 0.
Таким образом, либо 𝜆^*𝑔(ˆ) = 0, либо 𝜆^* 𝑔(ˆ) > 0. Однако если бы было верно неравенство 𝜆^*𝑔(ˆ) > 0, то, учитывая доказанное в предыдущем пункте неравенство 𝜆^* ≥ 0, заключаем, что 𝑔(ˆ) > 0, что противоречит условию 𝑔(ˆ) ≤ 0.

2. 
   Докажем, что ∀ ∈ R
   

𝜆^*₀𝑓 (ˆ) + ∑︁ 𝜆^* 𝑔(ˆ) ≤ 𝜆₀^*𝑓 () + ∑︁ 𝜆^* 𝑔(). (2.57)

Из (2.56) следует, что левая часть (2.57) равна 𝜆^*₀𝑓 (ˆ). Т.к. ∀ 𝜀 > 0 множество Λ содержит вектор

_𝜆 def
= (𝑓 () − 𝑓 (ˆ) + 𝜀, 𝑔₁(), . . . , 𝑔()),
то из (2.54) следует, что

∑︁

⟨𝜆^*, 𝜆⟩ = 𝜆₀^*(𝑓 () − 𝑓 (ˆ) + 𝜀) + 𝜆^*𝑔() ≥ 0,

=1
откуда, ввиду произвольности 𝜀, следует (2.57).

2. 
   Докажем, что 𝜆^*₀ 0.
   

Если 𝜆^*₀ = 0, то из 𝜆^* ̸= ^¯0 следует, что ∃ ∈ {1, . . . , } : 𝜆^* > 0.

∈
По предположению, для некоторого R выполнено условие (2.44). Для этого верно также (2.57), однако в данном случае левая часть (2.57) равна 0, а правая часть (2.57) меньше 0, что невозможно.

Искомые значения 𝜆^ˆ
, . . . , 𝜆^ˆ определяются как ^𝜆*¹ , . . . , ^𝜆* .

1 _𝜆^*_{0 𝜆}^*₀
Истинность каждого из трех соотношений в (2.47) следует из соот-
ветствующих пунктов изложенного выше рассуждения.
Докажем, что если функции 𝑓, 𝑔₁, . . . , 𝑔 дифференцируемые, то тре- тье соотношение в (2.47) равносильно соотношению (2.48), т.е.
𝐿(ˆ, 𝜆^ˆ) = min 𝐿(, 𝜆^ˆ) ⇔ ∀ = 1, . . . , ^𝜕𝐿 (ˆ, 𝜆^ˆ) = 0, (2.58)

∈R
где 𝜆^ˆ = (𝜆^ˆ₁ . . . , 𝜆^ˆ).
𝜕

⇒
Импликация « » в (2.58) верна потому, что ее правая часть является необходимым условием минимума дифференцируемой функции.
Обоснуем импликацию «⇐» в (2.58). Из выпуклости 𝑓, 𝑔₁, . . . , 𝑔 и неотрицательности 𝜆^ˆ₁, . . ., 𝜆^ˆ следует выпуклость функции ↦→ 𝐿(, 𝜆^ˆ):
∀ , ^′ ∈ R, ∀ 𝛼 ∈ [0, 1] 𝐿(𝛼 + (1 − 𝛼)^′, 𝜆^ˆ) =

= 𝑓 (𝛼 + (1 − 𝛼) ) +

𝜆𝑔(𝛼 + (1 − 𝛼) ) ≤

≤ 𝛼𝑓 () + (1 − 𝛼)𝑓 ( ) +

𝜆(𝛼𝑔() + (1 − 𝛼)𝑔( )) =

=1

′ ^∑︀ _ˆ ′
′ ^∑︀ _ˆ ′

= 𝛼𝐿(, 𝜆^ˆ) + (1 − 𝛼)𝐿(^′, 𝜆^ˆ),

откуда на основании такого же рассуждения, которое приведено в конце пункта 2.3.2, следует, что значение аргумента ˆ, удовлетворяющее пра- вой части (2.58), является глобальным минимумом этой функции.