§ 4. Двойственная задача

В этом параграфе будет рассмотрена частная задача квадратичного программирования, решение которой эквивалентно построению обобщенного портрета.

Введем пространство параметров ,  и рассмотрим в нем функцию

,

где вектор  есть

.

Будем искать максимум этой функции в положительном квадранте , .

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

Итак, рассмотрим точку максимума ,  функции  в положительном квадранте.

Необходимыми и достаточными условиями максимума функции  в точке ,  являются условия:

Выпишем эти условия, обозначив

,

получим

                       (14.13)

Условия (14.13) могут быть переписаны в виде неравенств (14.3)

,

и равенств (14.12)

,

.

Согласно утверждению теоремы 14.6, эти условия однозначно определяют обобщенный портрет .

Таким образом, связь между обобщенным портретом и максимумом функции  в положительном квадранте устанавливает следующая теорема.

Теорема 14.7. Для того чтобы функция  была ограничена сверху в положительном квадранте, необходимо и достаточно, чтобы  имело допустимое значение. При допустимом  точка , в которой достигается условный максимум  в положительном квадранте, задает обобщенный портрет соотношением

.

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

Теорема 14.8. При допустимом  максимум функции  в положительном квадранте равен половине квадрата модуля обобщенного портрета .

Доказательство. Действительно, по теореме 14.7

,

поэтому

и, вспоминая, что отличны от нуля лишь коэффициенты при крайних векторах  и , имеем

.

Таким образом,

.

Теорема доказана.

Из теоремы 14.8 вытекает важное для конструирования алгоритмов построения разделяющих гиперплоскостей следствие.

Следствие. В случае, когда среди крайних векторов обобщенного портрета  встречаются векторы обоих классов, справедливо соотношение

    (, ),                      (14.14)

причем равенство достигается при , .

Здесь  есть расстояние между проекциями классов  и  на направление обобщенного портрета. Действительно, в силу теоремы 14.8

.

Далее, по условию

,

.

Поэтому

.

Отсюда, учитывая, что

,

получаем (14.14).

Это следствие используется для конструирования критерия неделения. В самом деле, будем считать, что два множества  и  не могут быть разделены с допустимым «зазором» с помощью обобщенного портрета , , если соответствующая величина  меньше заданной константы .

Тогда существование такой точки , , что

,              (14.15)

и будет означать, что множества неразделимы с заданным зазором с помощью обобщенного портрета .

Итак, согласно теоремам 14.7 и 14.8, максимум  в положительном квадранте определяет обобщенный портрет, а, согласно следствию, тот факт, что при  максимум еще не достигнут, означает, что множества неразделимы с зазором, большим, чем .

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

Оказывается, что и другие методы построения разделяющей гиперплоскости в определенном смысле реализуют различные алгоритмы поиска максимума функции  в положительном квадранте. Это обстоятельство дает возможность сравнивать их между собой: тот алгоритм построения разделяющей гиперплоскости эффективнее, в основе которого лежит более эффективная процедура максимизации функции .