6.2. СОПРЯЖЕННЫЕ НАПРАВЛЕНИЯ

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

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

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

Сопряженные направления. Для данной симметричной матрицы порядка направления называются сопряженными (или, более точно, -сопряженными), если

и

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

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

описывает -мерное подпространство при произвольном изменении чисел Рассмотрим теперь точку где являются заданными:

В этом случае при произвольном изменении получаем -мерное (линейное) многообразие.

-мерное многообразие представляет собой сдвиг -мерного подпространства. В приведенном уравнении указывает величину сдвига подпространства от начала координат. Отметим, что многообразие может быть подпространством, если или если входит в подпространство, натянутое на Но если не входит в

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

Резюмируя, можно сказать, что любая точка сопряженных направлений порождают -мерное многообразие и любое -мерное многообразие совпадает с

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

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

Доказательство. Согласно сказанному выше любая точка в -мерном многообразии быть представлена в виде с соответствующими у. Поэтому мы должны выбрать так, чтобы максимизировать

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

Следует обратить внимание также на то, что (результирующее значение не зависит от других членов,

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

Сопряженные направления максимизируют квадратичную функцию. Основное применение теоремы (6.1) — это случай При этом так как -мерное многообразие совпадает с максимум на может быть определен не более чем за просмотров. Существование сопряженных направлений предлагается доказать в упр. 2. Позже мы покажем, как построить сопряженных направлений. Таким образом, сопряженные направления могут максимизировать квадратичную функцию самое большее за шагов. Здесь, конечно, под максимизацией квадратичной функции мы подразумеваем определение оптимальной точки либо выяснение того, что не ограничено сверху.

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

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

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