Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 167
Скачиваний: 4
§ 2. МЕТОД .СОПРЯЖЕННЫХ ГРАДИЕНТОВ |
381 |
3) находится точка x k+1, доставляющая условный мак симум F (X) на прямой
X = x h + l z h+1.
В. Останов алгоритма. Процесс обрывается в тот мо мент, когда градиент gk+1 обратится в нуль, т. е. достига ется максимум F (х) на всем пространстве Е п.
При абсолютно точном вычислении алгоритм должен привести к максимуму не более чем за п шагов, так как при
этом точки х 0, . . |
., x h, вычисляемые методом сопряжен |
ных градиентов, |
совпадают с точками х0, . . ., х к, полу |
чающимися в процессе, описанном в предыдущем пункте: как было показано, этот процесс выводит на абсоютный максимум не более чем за п шагов.
В реальных условиях, при ограниченной точности вы числений, процесс поиска максимума следует остановить не при точном обращении в нуль градиента, а в тот момент, когда градиент станет достаточно мал. При этом на самом деле может потребоваться более п шагов. Более подробно эти вопросы будут рассмотрены ниже.
Чтобы придать алгоритму более «конструктивную» форму, найдем формулу, определяющую точку максимума
квадратичной формы на прямой х = х* + Kz. |
|
Подставляя уравнение прямой в выражение функции |
|
F (х), получим |
(z*Az) + х (z>s (**))+ F (**)> |
F и = |
|
где g (X*) — градиент F (х) в точке х*. Максимизируя по
Я, |
получим |
|
|
|
Л |
(z, g (ж*)) |
|
|
Лопт ~ |
(*, Az) |
|
и |
соответственно |
|
|
|
|
(z, ё (ж*)) |
( 16. 16) |
|
|
(z, Az) |
|
|
Таким образом, вычисление в пункте 3) |
алгоритма мо |
|
жет быть осуществлено по формуле |
|
||
^fc+i — xk
(ZK+1) Azh+i)
382гл . XVI. МЕТОД СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ
2.Более известна модификация метода, при которой для вычисления очередного направления zfe+1 используют ся векторы gh+l и zk вместо gk+1 и ук.
Рассмотрим систему векторов zv . . ., zk,. . ., коллинеарных соответственно векторам уѵ . . ., yk (т. е. zk = $кУк при некоторых действительных 6к Ф 0). Для векторов zt и Zj сохраняется условие А-ортогональности
(zu Azj) = |
0 |
при і Ф j. |
(16.17) |
Кроме того, из (16.11) следует, что |
|
||
(Zfc+i, Agi) = 0 |
при і < к. |
(16.18) |
|
Наконец, остается в силе соотношение типа (16.9) |
|
||
к |
|
|
|
Zfc+1 = 2 |
cizi + bgk+1- |
(15.19) |
|
i=l |
|
|
|
Умножая правую и левую части (16.19) |
на A zt и учиты |
||||
вая (16.17) и (16.18), получим при і<С.к |
|
||||
|
Ci (Zu Azt) = |
0, |
|
||
откуда Ci = |
0 при і <С к. При і = |
к получим |
|||
0 = |
(zfc+1, Azt) = |
ch (zfc |
A zh) + X (gh+1, A z h), |
||
откуда |
|
|
|
|
|
|
= » ■ |
( « » |
« * . ) . |
(16.20) |
|
Соотношение (16.20) определяет zft+1 с точностью до произ вольного множителя через gk+1 и zk. При выводе (16.20) использовались лишь соотношения (16.17), (16.18), (16.19). Поэтому процесс построения векторов zh может рассмат риваться как процесс А -ортогонализации векторов gk.
Полагая в (16.20) %= 1 и zt — gt, получим конкрет ную систему векторов zk, коллинеарных yh. Каждый век тор zh задает направление прямой, исходящей из х к+1, на которой лежит х к. Алгоритм, таким образом, примет сле дующий вид (модификация II).
А. Начальный шаг, такой же как и в модификации I.
Б. |
Пусть уже найдены точка х к и направление zk. |
1) |
Находится градиент gk+1 функции F (х) в точке х к; |
|
§ 2. |
МЕТОД СОПРЯЖЕННЫХ |
ГРАДИЕНТОВ |
383 |
||
2) |
полагается |
|
|
|
|
|
где |
|
zh+l — |
Sh+1 + a h+lzh, |
|
||
|
ай+і —-teft+i,'1**) . |
(16.21) |
||||
|
|
|||||
|
|
|
||||
|
|
|
|
ih, АЧ) |
’ |
|
3) |
находится тонка |
хк+1, доставляющая условный мак |
||||
симум F (X) |
на прямой |
|
|
|
||
|
|
X — Хк -f- h Z x + i |
|
|||
по формуле |
|
|
(gk+i> *k+i) |
|
||
|
|
„ |
I |
(16.22) |
||
|
|
х к+1 = x k ~ T |
~ --------- л і |
Г z k+l- |
||
|
|
|
|
(zk+i> Azkvi) |
|
|
Формулы (16.21) и (16.22) могут быть преобразованы. Так, полагая
Y <*к, zk)
имеем из (16.22) |
|
|
|
Vk = ( x h — x h - 1) = |
TfeZfe. |
|
|
откуда получаем, применяя (16.12), |
|
|
|
(gm, 4zft) = Y~tek+i, Ayk) = |
------^ |
(16.23) |
|
С другой стороны, поскольку |
|
|
|
(gh, Vk-1) = |
(gh, Zft-x) = °. |
|
|
из (16.21) имеем |
|
|
|
( g h , z h) — ( g h ( g h + a hz h - l ) ) = gk |
|
||
и, таким образом, |
I «k I2 |
|
|
Tä= |
|
(16.24) |
|
(zb Azk>
Наконец, из (16.21), (16.23) и (16.24) получаем
— (?k+i> Azk> 1 |2 _ lgfc+i| (zk,Azk) T*(z* , U k l 2
384 ГЛ. XVI. МЕТОД СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ
Таким образом, формулы (16.21) и (16.22) могут быть за писаны в виде
zh+1 — Sh+1 ~Ь a Ä+lzÄ>
где
|
I &к+1I |
(16.25) |
|
|
“ ІМ 1 ’ |
||
и |
|
||
хки — xk “Ь |
1&к+і |2 |
(16.26) |
|
(2/г+і) ^ гй+і) Z/г+ъ |
|||
|
Совпадение результатов действия по формулам (16.21)
и (16.22), с одной стороны, и (16.25), (16.26), с другой,
может служить критерием правильности вычислений.
3. Метод сопряженных градиентов может быть приме нен и для максимизации функций F (х), не являющихся квадратичными. Известно, однако, что вблизи максимума достаточно гладкие функции, как правило, хорошо аппрок симируются квадратичной функцией, например, с по мощью разложения в ряд Тейлора. При этом обычно пред полагается, что коэффициенты аппроксимирующей квад ратичной функции неизвестны, но для любой точки мож но найти градиент g (х ) функции F (х ).
При этом пункт 1) алгоритма может быть выполнен без изменений, пункт 2) должен выполняться по формуле (16.25), поскольку в эту формулу не входит явно матрица А , а пункт 3), нахождение условного максимума на пря мой, может быть выполнен одним из известных способов, например, методом Фибоначчи. Применение метода со пряженных градиентов дает обычно значительно более быструю сходимость к максимуму по сравнению с метода ми наискорейшего спуска, Гаусса — Зайделя и др.
4. Что будет, если применить метод сопряженных гра диентов для максимизации квадратичной формы с поло жительно полуопределенной формой (х , А х )?
Если квадратичная форма (х , А х ) положительно полуопределена, то, как известно из линейной алгебры, в со ответствующей системе координат функция F (х) примет вид
П
F (х) = — сіхі + 2 bixi + d,
І—1
