1391

121

Пояснений требуют лишь формулы построения ортонормированных

векторов B j .

Так, в соответствии с процедурой ортогонализации Грамма – Шмидта, если известен набор векторов A1 , A2 , , An , то новая система

ортонормальных векторов B j строится как линейная комбинация этих векторов:

B1 A1 ,

B2 A2 21 A1 ,

j 1

B j A j ji Ai . i 1

Первый вектор новой системы берется, согласно (11.78), совпадающим

с первым вектором старой системы B1 A1 .

Следующие вектора определены как линейная комбинация предыдущих векторов старой системы. Для определения коэффициента 21

второго уравнения образуем произведение ( B2 )t B1 , в результате имеем

( B2 )t B1 ( A2 21 A1 )t B1 0 .

Отсюда получаем

21 [( A2 )t B1 ] /[( A1 )t B1 ] [( A2 )t B1 ] /[( B1 )t B1 ] .

В результате второй вектор новой системы запишется

B2 A2 [( A2 )t B1 ] /[( B1 )t B1 ] A1 ,

или учитывая, что A1 B1 и выражение для нормы вектора, можем записать

122

Производя аналогичные операции с последующими уравнениями,

получаем следующее обобщенное выражение

i 1

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

Алгоритм Розенброка с линейным поиском по направлению.

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

Начальный этап. Пусть 0 – скаляр, используемый в условии остановки. Выбираем в качестве S1 , S 2 , , S n исходные направления поиска, обычно это столбцы единичной матрицы. Задаѐмся начальным значением X 1

перейти к шагу 3.

Шаг 3. Построить новое множество линейно независимых и ортонормированных направлений в соответствии с (11.78). Обозначить

новые направления через S1 , S 2 , , S n и вернуться к шагу 3.

Как видно из приведенного алгоритма, при его реализации необходимо запоминать текущие направления и значения оптимальных шагов одномерных поисков, из которых в соответствии с первой частью выражений (11.78), строятся предварительные вектора новых направлений, ортогонализуемые затем с помощью процедуры Грамма - Шмидта.

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

124

заменяется на j . Так как 0 , то неудача приводит к сдвигу в обратном направлении вдоль j - го вектора на следующей реализации шага 1. Отметим

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

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

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

где матрица G , подразумевается единичной. Это дает основание воспользоваться для выбора сопряженных направлений известной процедурой Грамма - Шмидта для ортогонализации пространства векторов,

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

125

10

k

F k S k Ki , k 1 S i 1 ,

i 1

(11.82)

где 1 k n 1 .

Так как первое направление поиска определено, второе направление находится из обобщѐнного условия ортогональности (11.81)

( F1 )t G S 0 ( S1 K10 S 0 )t G S 0 0 .

Коэффициент K10 можно рассчитать из выражения

K10 [( F1 )t G S 0 ] / [( S 0 )t G S 0 ] ,

если известна матрица G .

Подставив найденный коэффициент во второе уравнение системы (11.82), определяем первое направление за исходным направлением

S1 F1 [( F1 )t G S 0 )] / [( S 0 )t G S 0 ] S 0 .

Из последующих уравнений (11.82) определим коэффициенты Kij , путѐм

последовательного умножения на предыдущие выделенные направления и используя обобщѐнное условие ортогональности

где j 0 ,1, , i 1 .

Соответственно, новое сопряжѐнное направление определиться из выражения

S i F i [( F i )t G S 0 )] / [( S 0 )t G S 0 ] S 0

(11.84)

[( F i )t G S i 1 ] / [( S i 1 )t G S i 1 ] S i 1 .

Таким образом, для вычисления нового сопряженного направления

поиска необходимо уметь вычислять вектор градиента в текущей точке F i и матрицу Гессе G .

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

Учитывая условие ортогональности направления поиска и сопряженности градиента (11.48), а также тот факт, что в окрестности минимума градиенты в соседних точках минимума практически ортогональны, т.е. следующее

126

направление поиска совпадает с направлением градиента в предыдущей точке, видим, что практически отличными от нуля будут коэффициенты Kij ,

при j i 1

что полностью соответствует полученному ранее соотношению (11.51), с учѐтом знаков коэффициентов в (11.47) и (11.82). Используя (11.82) и (11.87), перепишем соотношение (11.84) в виде

которое для определения нового направления не требует вычисления матрицы Гессе.

Обобщим изложенный материал, представив общий алгоритм, метода сопряжѐнных градиентов.

1.Полагаем k 0 и выбираем точку начального приближения X 0 , полагая S 0 F( X 0 ).

2.Вычислим F( X k ) и F( X k ) при k 0 .

3.Определяем направление поиска

S k F( X k ) [( F k )t F k ] /[( F k 1 )t F k 1 ] S k 1

и нормируем вектор направления поиска к единичной длине S k S k / S k .

X k 1 X k X k .

127

положим k k 1 и перейдем к шагу 2.

Применение соотношений (11.87) и (11.88) для не квадратичной функции, обеспечивает линейную сходимость, до тех пор, пока направление поиска не начнет периодически повторятся.

Рассмотренный алгоритм прост для реализации и требует умеренный объем оперативной памяти, необходимо запоминать только предыдущее направление поиска и предыдущий градиент. Этот алгоритм часто используют для задач, имеющих большое число переменных. В литературе данный метод известен под названием метода сопряженного градиента Флетчера и Ривса. Известны и другие версии метода сопряжѐнного градиента с лучшей сходимостью, но требующие несколько большей памяти. При этом модификации подвергается формула определения направлений поиска (11.87) и изменяется последовательность шагов алгоритма.

Вариант алгоритма, использующий соотношения (11.83) и (11.84), практически не используется из-за необходимости вычисления матрицы Гессе G .

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

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

Исходным моментом обоснования метода является разложение целевой функции F( X ) в ряд Тейлора с удержанием первых трех членов ряда и

записи его в виде

128

В данном методе матрица H ( X k ) является аппроксимацией обратной матрицы Гессе ( G k ) 1 и часто называется матрицей направлений. Для

аппроксимации обратной матрицы Гессе используются различные соотношения, не требующие вычисления вторых частных производных F( X ) и обращения матрицы.

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

Отметим, что для квадратичной функции F( X ) матрицы G и H постоянны,

поэтому (11.96) можно рассматривать как систему, используемую для оценки H( X ) , при известных значениях F( X ) , F( X ) и X . Для решения этой

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

В довольно большой группе методов G 1 ( X k 1 ) аппроксимируется с

помощью векторов градиента и приращений, полученных на предыдущем шаге

где H k – искомая матрица, а - масштабный множитель, константа, обычно равная единице. Выбор H k , по существу, определяет метод переменной

129

где Y и Z – произвольные векторы размерности n . Если при 1 / 1

то это соответствует, так называемому, алгоритму в модификации Бройдена. При этом (11.100) перепишется в виде

H k ( X k H k Qk ) ( X k H k Qk )t /[( X k H k Qk )t Qk ] .

что и соответствует описываемому алгоритму Дэвидсона-Флетчера-Пауэла. Допустимы и другие подстановки векторов, на которых мы не будем

останавливаться. Если шаги X k определяются последовательно путѐм минимизации F( X ) в направлении S k , то все методы, с помощью которых

вычисляют симметрическую матрицу H k 1 , удовлетворяющую (11.98), для квадратичной функции дают взаимно сопряжѐнные направления.

Метод Дэвидона-Флетчера-Пауэла попадает в общий класс квазиньютоновских процедур, в которых направления поиска задаются в

виде H k F k , т.е. совпадают с направлением градиента, отклонѐнным в результате умножения на H k . На следующем шаге, матрица направлений

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

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

130

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

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