§ 6. Градиентные методы построения разделяющей гиперплоскости (вычисление обобщенного портрета)

В предыдущем параграфе мы рассмотрели различные модификации метода Гаусса – Зайделя. Известно, что, вообще говоря, метод Гаусса – Зайделя является малоэффективным средством поиска максимума квадратичной формы. Поэтому хотелось бы использовать для построения разделяющей гиперплоскости более эффективные модификации методов поиска максимума квадратичной формы.

В настоящее время наиболее эффективным методом максимизации квадратичной формы считается метод сопряженных направлений. Особенность метода состоит в том, что с его помощью гарантируется достижение точного максимума за  шагов ( – размерность квадратичной формы). Подробно остановимся на методе сопряженных градиентов в главе XVI, а в этом параграфе рассмотрим модификации этого метода для поиска максимума квадратичной формы в положительном квадранте.

Рассмотрим метод сопряженных градиентов для поиска максимума квадратичной функции ; здесь  – положительно определенная матрица. Согласно этому методу поиск максимума функции начинается в произвольной точке . Первый шаг делается в направлении градиента функции в этой точке. Обозначим градиент функции в точке  через , направление движения из точки  через . Таким образом,

.

Шаг делается в направлении  до достижения максимума по этому направлению. Согласно формуле (16.26) главы XVI точка , доставляющая этот максимум, задается выражением

,

где  – матрица квадратичной формы функции . Затем последовательно находятся точки . В общем случае направление движения из точки  определяется (16.25) вектором

,             (14.17)

где  и  – соответственно градиенты функции  в точках  и , a  – направление движения из точки .

Движение по направлению  ведется до достижения условного максимума. Точка , доставляющая этот максимум, находится (16.26) из выражения

.                  (14.18)

Формулы (14.17) и (14.18) задают, таким образом, алгоритм поиска максимума квадратичной функции . Как уже указывалось, этот метод гарантирует отыскание максимума за  шагов.

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

Рассмотрим следующую модификацию метода сопряженных градиентов:

1) Поиск максимума функции  в области  начинается с точки . При этом движение в соответствии с формулами (14.17) и (14.18) происходит лишь до тех пор, пока точка  находится внутри области . Если траектория движения не выводит за ограничения, то не более чем за  шагов максимум будет найден.

2) Если же на некотором шаге  оказывается, что точка, в которой достигается условный максимум по направлению, лежит за пределами ограничений, то величина шага должна быть сокращена. Нетрудно убедиться, что при этом максимально допустимая величина шага определяется формулой

,             (14.19)

где минимум берется лишь по тем координатам , для которых . При этом для всех  оказывается

,

но по крайней мере для одной координаты  окажется, что , т. е. движение происходит до выхода на ограничение.

Итак, в этом случае

.

3) Если на некотором шаге  траектория выводит на ограничение, т. е. величину шага приходится уменьшать по формуле (14.19), то некоторые координаты  обратятся в нуль. Дальнейший поиск максимума ведется в положительном квадранте координатного подпространства  размерности , задаваемого уравнениями

.

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

4) Так продолжается до тех пор, пока в положительном квадранте некоторого координатного подпространства  не будет найден условный максимум функции. Пусть он достигается в точке . Если при этом выполняются условия:

, если ,

, если         ,

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

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

Рассмотрим еще одну модификацию метода сопряженных градиентов.

Определим следующую функцию :

.

Вектор  есть условный градиент функции  на множестве  (см. формулу (П. 8) приложения). Будем теперь совершать восхождение к максимуму, используя (14.17), (14.18), (14.19), где  заменено на условный градиент . Движение начинается из произвольной точки положительного квадранта и происходит до момента нарушения ограничения в точке . Тогда снова начинается восхождение по методу сопряженных градиентов из точки  и т. д. Поиск максимума заканчивается, когда выполнятся неравенства

.

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

Применим вторую модификацию метода сопряженных градиентов к задаче нахождения обобщенного портрета. Максимизируемая функция  имеет вид

.

Квадратичная часть этой функции есть

.

Обозначим составляющие условного градиента через

где положено . Обозначим составляющие вектора , задающего направление движения на -м шаге, через , .

При вычислении величины шага по формуле (14.18) необходимо вычислять величину , т. е. значение квадратичной функции  при подстановке в нее вектора . В нашем случае

,

где обозначено

.

Таким образом, заменяя формулы (14.17), (14.18) и (14.19) в соответствии с введенными обозначениями, приходим к следующему алгоритму.

Находится условный градиент в точке :

,

Определяется направление движения:

,

,

где

.

Далее вычисляется

.

Новое значение  и  находится по формулам

,

.

Здесь  – величина шага, определяемая из условия достижения максимума по направлению или выхода на ограничение:

,

где

,

Наконец,

.

Первый шаг  отличается от общего лишь тем, что значения ,  задаются следующим образом

,

.

Критерий останова:  и  или .

В главе XV будет подробно рассмотрена структура алгоритма построения обобщенного портрета на основе метода сопряженных градиентов в первой модификации.