§ 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, максимум в положительном квадранте определяет обобщенный портрет, а, согласно следствию, тот факт, что при максимум еще не достигнут, означает, что множества неразделимы с зазором, большим, чем . Таким образом, проблема построения обобщенного портрета свелась к поиску максимума функции в положительном квадранте или оценке снизу величины максимума этой функции. Оказывается, что и другие методы построения разделяющей гиперплоскости в определенном смысле реализуют различные алгоритмы поиска максимума функции в положительном квадранте. Это обстоятельство дает возможность сравнивать их между собой: тот алгоритм построения разделяющей гиперплоскости эффективнее, в основе которого лежит более эффективная процедура максимизации функции .
|