Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf

386 ГЛ. XVI. МЕТОД СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ

Таким образом, условие останова будет таким. Про­ цесс останавливается, если:

на очередном шаге gh+1 = О или

на очередном шаге оказывается, что

(zk+ii AZk+i) = 0.

В первом случае алгоритм, естественно, приводит в точку максимума. Во втором случае направление zh+1 будет направлением неограниченного возрастания функ­ ции F (х). В самом деле, на прямой

X = x h + Xzk+1

при (zh+1, A zk+1) = 0 функция F (х) имеет вид

X2

F(x) = F (xk) — -j- (zk+1, Azk+1) + (g*+1, z*+i)> =

= F (xk) + %(gft+1, gfe+i),

причем

возрастает неограниченно. Можно показать, что при этом из всех направлений, по которым функция бесконечно возрастает, она растет быстрее всего в направлении zh+1.

Нам остается убедиться, что останов произойдет не более чем через к шагов, где к — ранг матрицы А . В самом

(при выводе этих соотношений положительно-определен- ность не использовалась).

Отсюда следует, что векторы zt (1 1 та) образуют ■4-ортогоналышй базис, а градиент gm в точке хт орто­

388 гл . XVI. МЕТОД СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ

(эллипс), проходящая через х0, Іх — касательная к эллип­ су в точке х0, g1 — градиент функции F (х) в точке хй. Очевидно, что градиент gx нормален к линии уровня, т. е. перпендикулярен касательной Іѵ

Точка хх определяется как точка максимума функции F (х) на прямой г, проходящей через х 0 в направлении градиента gx. В точке хх эта прямая касается некоторой линии уровня. Поэтому градиент g2в точке хх перпендикулярен вектору gx и, сле­ довательно, прямая 12, про­ ходящая через хх в направ­ лении g2, параллельна Іѵ Далее, точка х2 находится как точка максимума F (х)

на прямой 12, где она ка­ сается эллипса А 2. Оче­ видно, что подобным сжа­

Рис. 28. тием можно перевести од­ новременно прямую Іхи эллипс А х в прямую 12и эллипс А 2. При этом точка х0перей­

дет в х2. Но при подобном сжатии к центру точка х0переме­ щается по прямой, проходящей через центр эллипсов. Поэтому прямая (х 0, х2) проходит через центр эллипсов, т. е. точку максимума функции на плоскости. Таким об­ разом, приходим к следующему способу:

1) из произвольной точки х 0 провести прямую г в на­ правлении градиента функции gx в точке х 0;

симума на этой прямой. Найденная точка есть точка, до­ ставляющая максимум функции на всей плоскости.

Вернемся теперь к задаче о нахождении максимума F (х) в п-мерном пространстве Е п. В соответствии со ска­ занным выше, процесс, описанный в § 1, может быть при­ веден к следующему виду.

А. Начальный шаг.

1) В произвольной точке х 0 пространства Е п находит­ ся градиент gx функции F (х);

§ 3. МЕТОД П А РАЛЛЕЛЬН Ы Х КАСАТЕЛЬНЫ Х (ПАРТАН) 389

2) на прямой X = х 0 + Xgt ищется точка хъ достав­ ляющая максимум функции F (х).

Б. Общий шаг. Пусть уже найдены точки х0, хъ . . .,

ипараллельной направлению gk+1, т. е. на плоскости

ж= хк_! + Ях (xk — х к^ ) -f K2gh+1,

ищется точка х к+1, доставляющая условный максимум функции F (х).

В. Останов алгоритма. Процесс прекращается, когда

X = Яй-і + Ях (xk — х к^ ) + K2gk+i

(Ях и Я2 — параметры) и, начиная с точки х = х к_ъ будем действовать по методу «партан». Прежде всего необходимо найти в точке х к_г условный градиент функции F (х) на плоскости A h. Известно, что условный градиент на ги­ перпространстве А есть проекция полного градиента на это гиперпространство. Таким образом, нам нужно спроек­ тировать вектор gh = V F (xk^1) на плоскость А к. Но в соответствии с (16.2) и (16.3) вектор gk ортогонален gk+i, а векторы (хк — ^ ц ) и gk+1 ортогональны между со­ бой. Поэтому проекция gk на плоскость Afe коллинеарна вектору (xk — xh. t).

Прямая, проходящая через точку х к_г в направлении условного градиента на плоскости, имеет, таким образом вид

Xх к—1 ф- Я (х к

аточка максимума на этой прямой есть х к, так как эта прямая принадлежит пространству Е к и х к доставляет

максимум F (х) на всем Е к.

Итак, оказывается, что первый шаг двумерного «партана» фактически уже выполнен и точка хг этого алгорит­ ма совпадает с х к.